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

  • $\begingroup$ Are $n$ in $S^n$ and in the diameter the same? $\endgroup$ Dec 9 '10 at 6:12
  • $\begingroup$ No. thanks for the comment - I'll correct it in editing $\endgroup$ Dec 9 '10 at 6:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.