Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I may have misunderstood your definition, but it seems to me that the first property implies that there is a unique path between any two vertices. If that is the case, then X is a tree, extremal vertices appear to be leaves in the tree, and the second property seems to imply that the graph is just a path. –  mhum Nov 1 '11 at 17:50
    
I don't think so, because $\Gamma$ might be a proper subset of $\mathcal C$. Think, for instance, at the unit ball: $\mathcal C$ is the set of continuous paths and so you have many ways to connect to points, but you choose just one: the segment line. Well, basically, what I am asking, is the existence of a choice of paths such that blablabla. –  Valerio Capraro Nov 1 '11 at 18:12
    
Ah, okay. In that case, would that imply that the union of all paths in $\Gamma$ forms a tree inside of $X$? Maybe I am still confused? –  mhum Nov 1 '11 at 18:40
    
Maybe this is true, but I am not sure. –  Valerio Capraro Nov 1 '11 at 20:11
1  
I am mistaken. It turns out not to be the case that $\Gamma$ forms a tree. Consider $X$ to be a triangle with $\Gamma$ equal to the three edges. –  mhum Nov 1 '11 at 21:52
show 7 more comments

2 Answers 2

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.

share|improve this answer
    
This is a definition that makes sense also for subsets, since every graph is convex in itself according to this definition. I am looking for some property of the graph. Anyway, thanks for pointing out that there is a standard definition of a convex set in a graph. –  Valerio Capraro Nov 3 '11 at 17:52
    
To be precise there exist much more types of convexity of vertex sets in graphs. One can talk about geodesic convexity, monophonic convexity, "all-path" convexity, "induced-path" convexity and generally about convexities induced by different path transit functions. –  Sergiy Kozerenko Sep 10 '13 at 13:13
add comment

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

share|improve this answer
    
I have very little time. In a rush: (ii) OK, that's actually what I want; (i) NO, it's not empty. You're right that condition (i) is not very clear.. –  Valerio Capraro Nov 3 '11 at 21:09
    
I have modified the third property. I don't understand your third comment: let $X$ be the unit ball in $\mathbb R^n$, $\mathcal C$ is the set of all lines inside $X$, than $[x,y]$ is the intersection among all lines (=elements of $\Gamma$) passing through $x$ and $y$. –  Valerio Capraro Nov 4 '11 at 9:31
    
In case if there exist several lines of $\mathcal C$ passing via $x$ and $y$, then your definition may imply that $[x,y]=\{ x,y\}$ and this probably is not what you want. This will happen if you take geodesics (shortest paths) of a graph as the set $\mathcal C$: then for all pairs $x,y$ which are connected by several shortest paths, the segment $[x,y]$ will consit of two connected components, in particular it can coincide with $x,y$. For example, in the square grid with this set of lines, $[x,y]=\{ x,y\}$ for all pairs $x,y$ not lying on a common vertical or horizontal line. –  vc-dim Nov 4 '11 at 12:48
    
In the case of connected graphs, the set $\mathcal C$ is exactly the set of all geodesics, but notice that I require that $\Gamma$ is closed under intersection, so the $[x,y]$ cannot reduce to just the points $x$ and $y$ (unless they are adjacent). –  Valerio Capraro Nov 4 '11 at 13:53
    
What "$\Gamma$ is closed under intersections" means? If we consider your first condition, then in my reading it means that the intersection of two lines (i.e., paths from $\Gamma$) passing via $x$ and $y$ is a line from $\Gamma$ passing via $x$ and $y$. If this is so, then as I understand, your first condition and the definition of $\Gamma$ is equivalent to saying that for each pair of vertices $x,y$, there is a unique path $P(x,y)$ included in $\Gamma$ (as a line)so that if a path $P(x',y')$ passes via $x$ and $y$, then the portion of $P(x',y')$ between $x$ and $y$ coincides with $P(x,y).$ –  vc-dim Nov 4 '11 at 15:03
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.