Home » Discrete Geometry » The number of diameters

The number of diameters

One of my favourite little theorems in combinatorial geometry is the following:

Theorem 1. Let S be a set of n points of diameter d in the plane. Then the number of pairs in S at distance d is at most n.

The following two figures show how n diameter pairs can be attained:

Diameter graph I Diameter graph II

The first one is based on an equilateral triangle, with some dangling edges added, and the second is based on a regular star heptagon, also with dangling edges.

Let’s translate Theorem 1 into graph-theoretical terms. Define a graph by letting the vertices be the n points, and the edges the diameter pairs. Call this graph the diameter graph of the n points. Theorem 1 states that a diameter graph on n points has at most n edges. Its proof is not difficult; try it! [Hint: All standard proofs are based on the fact that any two diameters necessarily intersect.] I would now like to explore the history of this theorem. In particular, who proved it first?

Many papers and books, starting with a 1946 paper of Paul Erdős, credit Heinz Hopf from Zürich and E. Pannwitz from Berlin (1934) with this theorem, sometimes in combination with J. W. Sutherland from Cambridge (1935). However, when these old references are examined, no such theorem occurs. In fact, Hopf and Pannwitz posed the following problem in 1934:

Let a_0, a_1, \ldots, a_{n-1}, a_n=a_0 be n distinct points in the plane such that the distance conditions

a_{i}  a_{j} \leq 1

and

a_{i}  a_{i+1} = 1 (i= 0,\dots,n-1)

hold. Show that this is possible if n is odd and impossible if n is even and at least 4.

Two solutions were subsequently published in 1935: one by Sutherland and another by W. Fenchel (a well-known name in convexity). A list of other solvers appeared as well in the 1935 reference: A. E. Mayer (Vienna), H. Baer (Frankfurt), L. Ehrlich (Berlin), J. Fox (Brooklyn), R. Frucht (Triest), L. Goeritz (Rostock), F. Gruber (Vienna), J. Juilfs (Berlin), R. Lauffer (Graz), E. Linés Escardó (Madrid), P. Scherk (Göttingen), and W. Schulz (Berlin).

In graph-theoretical terms the problem asserts that:

Theorem 2. All cycles in a diameter graph in the plane are odd.

Does this imply Theorem 1? No. A graph without even cycles can have more edges than vertices (try to find some examples). However, it is well known that the upper bound for the number of edges is still linear: \lfloor\frac{3}{2}(n-1)\rfloor. [Hint: show that each block of at least three vertices in a graph with no even cycles consists of a single odd cycle.]

Thus Theorem 2 is unrelated to Theorem 1. However, both are easily deducible from the following statement, which is a characterisation of diameter graphs in the plane.
Theorem 3. Each connected component of a diameter graph in the plane is a path or a cycle that contains or is incident to every edge (i.e. a caterpillar with the head and tail possibly joined).

This can also be proved using the fact that any two edges intersect.

Back to Theorem 1. Who was the first to prove it? The oldest reference I can find is the 1946 paper of Erdős. So I would guess that he was the first to notice it, perhaps when he saw the problem of Hopf and Pannwitz and later recalled their problem incorrectly, thus giving them the credit. Who knows? The fact remains that the problem posed by Hopf and Pannwitz is about the nonexistence of even cycles, not about the maximum number of diameters.

References

  • P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250.
  • H. Hopf and E. Pannwitz, Aufgabe Nr. 167, Jahresbericht Deutsch. Math.-Verein. 43 (1934), p. 114.
  • J. W. Sutherland, Lösung der Aufgabe 167, Jahresbericht Deutsch. Math.-Verein. 45 (1935), 33- 35.

Acknowledgments

Thanks to Frank Bullock who helped me find the upper bound on the number of edges of a graph with no even cycles.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s