"minimal" embedding of bipartite graphs on a sphere - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:52:34Z http://mathoverflow.net/feeds/question/48712 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48712/minimal-embedding-of-bipartite-graphs-on-a-sphere "minimal" embedding of bipartite graphs on a sphere Izhar Oppenheim 2010-12-09T05:01:37Z 2012-09-27T23:05:49Z <p>Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):</p> <p>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$.</p> <p>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)$).</p> <p>Is the following claim true: does $k&lt; \frac{ \pi}{n}$ implies that $f(V)$ is contained in a hemisphere? </p> <p>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} &lt; \frac{ \pi}{1}$ and the vertices are not contained in any half circle.</p> <p>(One can say that I'm looking for a spherical Jung type theorem for bipartite graphs).</p> http://mathoverflow.net/questions/48712/minimal-embedding-of-bipartite-graphs-on-a-sphere/108010#108010 Answer by Anton Petrunin for "minimal" embedding of bipartite graphs on a sphere Anton Petrunin 2012-09-24T23:00:28Z 2012-09-27T23:05:49Z <p>Let $\Gamma$ be the metric space glued from segments of length $\pi/n$ along the rule described by your graph. </p> <p>Note that $\Gamma$ is a 1-dimensional spherical building. Therefore your question can be reformulated the following way:</p> <blockquote> <p>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.</p> </blockquote>