Sphere packings. VI: Tame graphs and linear programs (Q735001)

This paper is the sixth and final in the series of papers devoted to the proof of the Kepler's conjecture, all in Discrete Comput. Geom. 36, No. 1. This famous conjecture, open since 1611, asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In the second paper of this series a compact topological space of decomposition stars was defined, and a continuous scoring function on this space was introduced. Moreover, Kepler's conjecture was related to a certain conjecture about location of global maxima of this scoring function. The two conjectured global maxima of the scoring function (corresponding to decomposition stars of the face-centered cubic and hexagonal-close packings) were shown to be local maxima in the third paper of this series. In the current paper the set of all points in the space of decomposition stars at which the scoring function assumes the conjectured maximal value is considered. A certain planar graph is then associated to each such point, and it is proved that each such graph is isomorphic to a \textit{tame} graph. Now there are only finitely many isomorphism classes of tame graphs, and the linear programming methods are used to eliminate all possibilities except for the graphs corresponding to face-centered cubic, the hexagonal-close packings, and the pentahedral prisms decomposition stars. Since the pentahedral prisms were eliminated in the previous paper of this series, Kepler's conjecture follows. The results of this paper rely on long computer calculations.