|
10
|
|
edited Nov 4 2011 at 9:29 |
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_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
|
|
|
|
|
9
|
|
edited Nov 3 2011 at 18:24 |
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
|
|
|
|
|
8
|
|
edited Nov 3 2011 at 11:25 |
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\subseteq\mathcal \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
|
|
|
|
7
|
|
edited Nov 3 2011 at 7:08 |
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
|
|
|
|
|
6
|
|
edited Nov 2 2011 at 15:23 |
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.
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. I don't know how
Fourth property. The set $Extr(V)$ has to write down the definition be connected as a subgraph of $V$; $V$ has to be contractible and $Extr(V)$ has to be non-contractible (contractibility shortlyis defined in Def. For the details, one can see 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.
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.).
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
|
|
|
|
|
5
|
|
edited Nov 2 2011 at 7:35 |
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.
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. I don't know how to write down the definition of contractibility shortly. I hope you can understand it intuitively. In case it will be a pleasure to explain some For the details, but only if required (they might be quite long)one can see http://arxiv.org/abs/1111.0268. For now I prefer to show it intuitivelyIntuitively, 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.
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.
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
|
|
|
|
|
4
|
|
edited Nov 2 2011 at 7:15 |
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.
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. I don't know how to write down the definition of contractibility shortly. I hope you can understand it intuitively. In case it will be a pleasure to explain some details, but only if required (they might be quite long). For now I prefer to show the notion of contractibility it intuitively: the square $[0,n]^2$ is contractible; the boundary of this square, for $n\geq3$, is not contractible, since there is a hole.
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.
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
|
|
|
|
|
3
|
|
edited Nov 1 2011 at 14:56 |
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 closed under intersection, I will denote by $[x,y]$ the intersection of them.
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. I don't know how to write down the definition of contractibility shortly. I hope you can understand it intuitively. In case it will be a pleasure to explain some details, but only if required (they might be quite long). For now I prefer to show the notion of contractibility intuitively: the square $[0,n]^2$ is contractible; the boundary of this square, for $n\geq3$, is not contractible, since there is a hole.
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.
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
|
|
|
|
|
2
|
|
edited Nov 1 2011 at 14:42 |
Does a notion of convex graph makes make sense?
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 $\gamma\in\Gamma$ passing through $x,y$ is closed under intersection, I will denote by $[x,y]$ the intersection of them.
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. I don't know how to write down the definition of contractibility shortly. I hope you can understand it intuitively. In case it will be a pleasure to explain some details, but only if required (they might be quite long). For now I prefer to show the notion of contractibility intuitively: the square $[0,n]^2$ is contractible; the boundary of this square, for $n\geq3$, is not contractible, since there is a hole.
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.
The point is that I am not able to find any example of such graphs! :) I can imagine that some huge discretization of the spheres 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
|
|
|
|
|
1
|
|
asked Nov 1 2011 at 14:36 |
Does a notion of convex graph makes sense?
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 $\gamma\in\Gamma$ passing through $x,y$ is closed under intersection, I will denote by $[x,y]$ the intersection of them.
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. I don't know how to write down the definition of contractibility shortly. I hope you can understand it intuitively. In case it will be a pleasure to explain some details, but only if required (they might be quite long). For now I prefer to show the notion of contractibility intuitively: the square $[0,n]^2$ is contractible; the boundary of this square, for $n\geq3$, is not contractible, since there is a hole.
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.
The point is that I am not able to find any example of such graphs! :) I can imagine that some huge discretization of the spheres 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
|
|
|
