Does a notion of convex graph make sense? - MathOverflow

Does a notion of convex graph make sense?

2011-11-01T14:36:21Z

Let $X=(V,E)$ be a finite connected graph. I would be interested in some notion of convexity.

General question: Is there a notion of convexity for finite connected graphs? How does it look like?

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.

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:

Let $\mathcal C$ be the set of paths inside $X$. I want to axiomatize a convex structure, saying that some of these paths are lines. So, a convex structure on $X$ should be a (possibly proper) subset $\Gamma$ of $\mathcal C$ such that

First Property. 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).

Before stating the other properties, I need to define what are the $\Gamma$-extremal points

Definition: $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.

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.

Second Property. 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)]$

Now, I want some version of continuity, for the points obtained prolonging line till hitting the boundary.

Third Property. 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.

At this point, one can says Well, take $l(x,y)$ to be constant!. But I don't want this triviality.

Fourth property. 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 http://arxiv.org/abs/1111.0268. 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 hole.).

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.

More specific question: Does there exist some non trivial examples of such graphs?

Thanks in advance,

Valerio

Answer by David Eppstein for Does a notion of convex graph make sense?

2011-11-03T15:01:27Z

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.

Answer by vc-dim for Does a notion of convex graph make sense?

2011-11-03T19:06:13Z

(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$.

(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.

(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).

(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 & Computational Geometry 38(2): 243-257 (2007). About abstract convexity, see the book Theory of convex structures by M. Van de Vel.