9
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Nov 1, 2011 at 17:50
  • $\begingroup$ 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. $\endgroup$
    – Valerio Capraro
    Commented Nov 1, 2011 at 18:12
  • $\begingroup$ 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? $\endgroup$
    – mhum
    Commented Nov 1, 2011 at 18:40
  • $\begingroup$ Maybe this is true, but I am not sure. $\endgroup$
    – Valerio Capraro
    Commented Nov 1, 2011 at 20:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Nov 1, 2011 at 21:52

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Valerio Capraro
    Commented Nov 3, 2011 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – Sergiy Kozerenko
    Commented Sep 10, 2013 at 13:13
  • $\begingroup$ This exact definition is also used in the theory of near polygons: en.wikipedia.org/wiki/Near_polygon. One of the most basic/important structural result for near polygons is about existence of "quads", which are basically convex subsets isomorphic to generalized quadrangles: en.wikipedia.org/wiki/Generalized_quadrangle, roughly under the condition that every two points at distance 2 from each other have more than one common neighbours. $\endgroup$
    – Anurag
    Commented May 5, 2016 at 15:05
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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.. $\endgroup$
    – Valerio Capraro
    Commented Nov 3, 2011 at 21:09
  • $\begingroup$ 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$. $\endgroup$
    – Valerio Capraro
    Commented Nov 4, 2011 at 9:31
  • $\begingroup$ 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. $\endgroup$
    – vc-dim
    Commented Nov 4, 2011 at 12:48
  • $\begingroup$ 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). $\endgroup$
    – Valerio Capraro
    Commented Nov 4, 2011 at 13:53
  • $\begingroup$ 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).$ $\endgroup$
    – vc-dim
    Commented Nov 4, 2011 at 15:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .