User jamie j. taylor - MathOverflow

What is the largest possible thirteenth kissing sphere?

2012-04-21T14:05:04Z

It is well-known that it is impossible to arrange 13 spheres of unit radius all tangent to another unit sphere without their interiors intersecting. This was apparently the subject of disagreement between Isaac Newton ("impossible") and David Gregory ("possible"). The cause of the dispute was, in part, that there seems to be a lot of room left over after 12 spheres.

How close of a call is it, so to speak? What is the largest possible $r$ so that it is possible to arrange 12 spheres of unit radius and a 13th sphere of radius $r$ all tangent to another unit sphere, without intersections? What does the optimal configuration look like?

Answer by Jamie J. Taylor for Can Morley's theorem be generalized?

2012-04-21T22:24:26Z

Please forgive me if you are aware of this result (as it is linked from the Wikipedia page, albeit in another context), but there is a paper by Richard K. Guy called "The lighthouse theorem, Morley & Malfatti—a budget of paradoxes" in the American Mathematical Monthly. The eponymous theorem could be considered a generalization of Morley's theorem:

Lighthouse Theorem. Two sets of $n$ lines at equal angular distances, one set through each of the points $B$, $C$, intersect in $n^2$ points that are the vertices of $n$ regular $n$-gons.

Naturally, it is not clear how this would qualify as a generalization, but the connecting observation is the following:

The Morley Miracle. The nine edges of the equilateral triangles of the Lighthouse Theorem for $n=3$ are the Morley lines of a triangle.

Properly, the Lighthouse Theorem should be enlarged to include enough observations to make this connection. For example, the $n^2$ lines of the $n$ regular $n$-gons form $n$ families of $\binom{n}{2}$ parallel lines; if $n$ is odd, then the $n$-gons are homothetic. Moreover, there is an angle duplication result that establishes the presence of the trisectors.

From Guy's point of view, the particularly pleasant appearance of Morley's theorem is due to the fact that $\binom{n}{2} = n$ for $n=3$. For comparison, the case $n=2$ is even simpler and may be regarded as the statement that the altitudes of a triangle concur. (The $n$ $n$-gons are an orthocentric system.) The case $n=4$ gives some properties of Malfatti circles. For all of these interpretations, Guy wrestles with the "paradox" that you recover theorems about a triangle even though you don't start with any triangles.

Again, my apologies if you're aware of all of this. I imagine you may be, in which case I justify my answer as simply too long for a comment!

Answer by Jamie J. Taylor for Crossing number of the Grötzsch graph

2012-04-21T13:07:26Z

The crossing number of the Grötzsch graph is 5.

Crossing numbers are believed to be difficult to compute in general. (The corresponding decision problem is NP-hard.) However, for small graphs and small crossing numbers, it is possible to find an optimal planar drawing. For example, see Markus Chimani's thesis "Computing Crossing Numbers" for more information.

The Open Graph Drawing Framework (OGDF) can compute crossing numbers. After compiling the program on the linked page and entering the Grötzsch graph, my computer computed that the optimal planar drawing has 5 crossings. Let me emphasize that this technique is exact, not heuristic.

Comment by Jamie J. Taylor

2012-04-21T15:46:42Z

@Pietro Majer: yes, that is in fact a good variant! I would be interested in an answer to either version, but hopefully I can get an answer to both!