Does a notion of convex graph make sense? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:53:16Z http://mathoverflow.net/feeds/question/79717 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense Does a notion of convex graph make sense? Valerio Capraro 2011-11-01T14:36:21Z 2011-11-04T09:29:11Z <p>Let $X=(V,E)$ be a finite connected graph. I would be interested in some notion of convexity.</p> <blockquote> <p><strong>General question:</strong> Is there a notion of convexity for finite connected graphs? How does it look like?</p> </blockquote> <p>As pointed out below by David Eppstein, there is a standard notion for a subsets of a graph to be convex. I am actually interested in something different: a notion of convexity for the graph itself.</p> <p>I want to share some thoughts, hoping that someone is interested. Taking inspiration from the unit ball in $\mathbb R^2$ and also from the properties that I would need, I am tempted to require the following properties:</p> <p>Let $\mathcal C$ be the set of paths inside $X$. I want to axiomatize a <em>convex structure</em>, saying that some of these paths are <em>lines</em>. So, a convex structure on $X$ should be a (possibly proper) subset $\Gamma$ of $\mathcal C$ such that</p> <p><strong>First Property.</strong> For all $x,y\in V$, $x\neq y$, the set of $\gamma\in\Gamma$ passing through $x,y$ is non-empty and closed under intersection, I will denote by $[x,y]$ the intersection of them. (Notice that I am not supposing that $[x,y]=[y,x]$ as a set of points).</p> <p>Before stating the other properties, I need to define what are the $\Gamma$-extremal points</p> <p><strong>Definition:</strong> $x_0\in V$ is called $\Gamma$-internal if for all $x\in V$, $x\neq x_0$, there is $y\in V$, with $y\neq x_0$, such that $[x,x_0]\subseteq[x,y]$. A vertex is called $\Gamma$-extremal if it is not $\Gamma$-internal. </p> <p>Now, let $Extr(V)$ be the set of extremal vertexes. I can state the remaining properties. Next property states that I can prolonge uniquely the line until hitting the boundary.</p> <p><strong>Second Property.</strong> For all $x,y\in V$, $x\neq y$, there exists a unique $l(x,y)\in Extr(V)$ such that $[x,y]\subseteq[x,l(x,y)]$</p> <p>Now, I want some version of continuity, for the points obtained prolonging line till hitting the boundary.</p> <p><strong>Third Property.</strong> If $x_1\sim x$ and $y_1\sim y$, then $l(x_1,y_1)$ and $l(x,y)$ are either adjacent or coincide, where $\sim$ stands for the usual adjacency relation.</p> <p>At this point, one can says <em>Well, take $l(x,y)$ to be constant!</em>. But I don't want this triviality. </p> <p><strong>Fourth property</strong>. The set $Extr(V)$ has to be connected as a subgraph of $V$; $V$ has to be contractible and $Extr(V)$ has to be non-contractible (contractibility is defined in Def. 17 in <a href="http://arxiv.org/abs/1111.0268" rel="nofollow">http://arxiv.org/abs/1111.0268</a>. Intuitively, keep in mind the following example: the square $[0,n]^2$ is contractible; the boundary of this square, for $n\geq3$, is not contractible, since there is a <em>hole</em>.).</p> <p>The point is that I am not able to find any example of such graphs! :) I can imagine that some huge discretization of the ball might play the game, but I am not quite sure. </p> <blockquote> <p><strong>More specific question:</strong> Does there exist some non trivial examples of such graphs?</p> </blockquote> <p>Thanks in advance,</p> <p>Valerio</p> http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense/79935#79935 Answer by David Eppstein for Does a notion of convex graph make sense? David Eppstein 2011-11-03T15:01:27Z 2011-11-03T15:01:27Z <p>I don't know that it's really what your asking for, but I believe there exists a standard definition of a convex set for finite graphs: a set $S$ of vertices is convex if, for every two vertices in $S$ and every shortest path between the two vertices, the other vertices in the shortest path also belong to $S$. This is used, for instance, in the theory of partial cubes, median graphs, and distance-hereditary graphs.</p> http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense/79961#79961 Answer by vc-dim for Does a notion of convex graph make sense? vc-dim 2011-11-03T19:06:13Z 2011-11-03T19:06:13Z <p>(i) If $[x,y]$ can be empty, then taking an $n\times n$ square in the square grid and the vertical and horizontal paths as the set of paths $\mathcal C$, all properties are satisfied except the second property for pairs $x,y$ on the boundary; to get all properties satisfied, instead of a square take the vertices of the grid in the lozenge $|x|+|y|\le n$. </p> <p>(ii) If you relax the third property by allowing that $l(x_1,y_1)$ and $l(x_2,y_2)$ either are adjacent or coincide'', then the 5-cycle with the set of shortest paths as $\mathcal C$ seems to satisfy all conditions. </p> <p>(iii) Condition (i) needs to be written in a more precise way: as I understand, $[x,y]$ is the (vertex-set) union of the portions between $x$ and $y$ of all paths of $\mathcal C$ passing via $x$ and $y$ (and not their intersection). </p> <p>(iv) Bibliography remarks: on a related topic (but not for graphs), see the paper R. Dhandapani, J. E. Goodman, A. Holmsen, R. Pollack, S. Smorodinsky, Convexity in Topological Affine Planes. Discrete &amp; Computational Geometry 38(2): 243-257 (2007). About abstract convexity, see the book Theory of convex structures by M. Van de Vel.</p>