Return to Question

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)\sim l(x,y)$, 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

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

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?

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)\sim l(x,y)$, 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

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)\sim l(x,y)$, 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

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?

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 $\Gamma\subseteq\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)\sim l(x,y)$, 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

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?

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)\sim l(x,y)$, 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