"minimal" embedding of bipartite graphs on a sphere

2010-12-09T05:01:37Z

Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):

Let (V,E) be a bipartite graph with the following property – the girth of the graph (i.e. the length of the shortest loop) is equal to the diameter of the graph times 2. i.e. if we denote the girth $2n$ then the diameter is $n$.

For such a graph and call an embedding of the graph into a sphere $S^m$ a function $f:V\rightarrow S^m$ Such that there is a constant $k$ such that if $v_1$ and $v_2$ are connected by an edge then $d(f(v_1),f(v_2))=k$ when $d$ is the spherical distance (i.e. the length of the shortest geodetic segment on the sphere which connects $f(v_1)$ and $f(v_2)$).

Is the following claim true: does $k< \frac{ \pi}{n}$ implies that $f(V)$ is contained in a hemisphere?

Note that the settings are important - for any graph the answer is clearly no: take a triangle and embed it in the obvious way in a circle - so the diameter of the graph is 1 but the length of the arc between two vertices is $\frac{2 \pi}{3} < \frac{ \pi}{1}$ and the vertices are not contained in any half circle.

(One can say that I'm looking for a spherical Jung type theorem for bipartite graphs).

Answer by Anton Petrunin for "minimal" embedding of bipartite graphs on a sphere

2012-09-24T23:00:28Z

Let $\Gamma$ be the metric space glued from segments of length $\pi/n$ along the rule described by your graph.

Note that $\Gamma$ is a 1-dimensional spherical building. Therefore your question can be reformulated the following way:

Let $\Gamma$ be a 1-dimensional spherical building and $f\colon \Gamma\to\mathbb S^n$ is a contracting map. Then the image $f(\Gamma)$ lies in a half-sphere.

"minimal" embedding of bipartite graphs on a sphere - MathOverflow

"minimal" embedding of bipartite graphs on a sphere

Answer by Anton Petrunin for "minimal" embedding of bipartite graphs on a sphere