Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Are $n$ in $S^n$ and in the diameter the same? –  Sergei Ivanov Dec 9 '10 at 6:12
    
No. thanks for the comment - I'll correct it in editing –  Izhar Oppenheim Dec 9 '10 at 6:14

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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