Sphere Packings, V. Pentahedral Prisms

This paper is the fifth in a series of papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In this paper we prove that decomposition stars associated with the plane graph of arrangements we term pentahedral prisms do not contravene. Recall that a contravening decomposition star is a potential counterexample to the Kepler conjecture. We use interval arithmetic methods to prove particular linear relations on components of any such contravening decomposition star. These relations are then combined to prove that no such contravening stars exist.     

Sphere Packings, II

An earlier paper describes a program to prove the Kepler conjecture on sphere packings. This paper carries out the second step of that program. A sphere packing leads to a decomposition of R ³ into polyhedra. The polyhedra are divided into two classes. The first class of polyhedra, called quasi-regular tetrahedra, have density at most that of a regular tetrahedron. The polyhedra in the remaining class have density at most that of a regular octahedron (about 0.7209). Received April 24, 1995, and in revised form April 11, 1996.     

Historical Overview of the Kepler Conjecture

This paper is the first in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. After some preliminary comments about the face-centered cubic and hexagonal close packings, the history of the Kepler problem is described, including a discussion of various published bounds on the density of sphere packings. There is also a general historical discussion of various proof strategies that have been tried with this problem.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

Bounds for Local Density of Sphere Packings and the Kepler Conjecture

This paper formalizes the local density inequality approach to getting upper bounds for sphere packing densities in R ⁿ . This approach was first suggested by L. Fejes Tóth in 1953 as a method to prove the Kepler conjecture that the densest packing of unit spheres in R ³ has density π/\sqrt 18 , which is attained by the ``cannonball packing.' Local density inequalities give upper bounds for the sphere packing density formulated as an optimization problem of a nonlinear function over a compact set in a finite-dimensional Euclidean space. The approaches of Fejes Tóth, of Hsiang, and of Hales to the Kepler conjecture are each based on (different) local density inequalities. Recently Hales, together with Ferguson, has presented extensive details carrying out a modified version of the Hales approach to prove the Kepler conjecture. We describe the particular local density inequality underlying the Hales and Ferguson approach to prove Kepler's conjecture and sketch some features of their proof. Received November 19, 1999, and in revised form April 17, 2001. Online publication December 17, 2001.     

Positive graphs

We study “positive” graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edgeweights may be negative). We conjecture that all positive graphs can be obtained by taking two copies of an arbitrary simple graph and gluing them together along an independent set of nodes. We prove the conjecture for various classes of graphs including all trees. We prove a number of properties of positive graphs, including the fact that they have a homomorphic image which has at least half the original number of nodes but in which every edge has an even number of pre-images. The results, combined with a computer program, imply that the conjecture is true for all but one graph up to 10 nodes.     

Sphere Packing, IV. Detailed Bounds

This paper is the fourth in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In a previous paper in this series, a continuous function f on a compact space was defined, certain points in the domain were conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture was established. The function f can be expressed as a sum of terms, indexed by regions on a unit sphere. In this paper detailed estimates of the terms corresponding to general regions are developed. These results form the technical heart of the proof of the Kepler conjecture, by giving detailed bounds on the function f. The results rely on long computer calculations.     

A Contribution to the Second Neighborhood Problem

Seymour’s Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We prove this conjecture for classes of oriented graphs whose missing graph is a comb, a complete graph minus two independent edges, or a cycle of length 5.     

The acircuitic directed star arboricity of subcubic graphs is at most four

A directed star forest is a forest all of whose components are stars with arcs emanating from the center to the leaves. The acircuitic directed star arboricity of an oriented graph G (that is a digraph with no opposite arcs) is the minimum number of arc-disjoint directed star forests whose union covers all arcs of G and such that the union of any two such forests is acircuitic. We show that every subcubic graph has acircuitic directed star arboricity at most four.     

A Formulation of the Kepler Conjecture

This paper is the second in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. The top level structure of the proof is described. A compact topological space is described. Each point of this space can be described as a finite cluster of balls with additional combinatorial markings. A continuous function on this compact space is defined. It is proved that the Kepler conjecture will follow if the value of this function is never greater than a given explicit constant.     

A Revision of the Proof of the Kepler Conjecture

The Kepler conjecture asserts that no packing of congruent balls in three-dimensional Euclidean space has density greater than that of the face-centered cubic packing. The original proof, announced in 1998 and published in 2006, is long and complex. The process of revision and review did not end with the publication of the proof. This article summarizes the current status of a long-term initiative to reorganize the original proof into a more transparent form and to provide a greater level of certification of the correctness of the computer code and other details of the proof. A final part of this article lists errata in the original proof of the Kepler conjecture.     

Compatible relations on Heyting chains

We give a sufficient condition for a finite algebra to admit only finitely many compatible relations (modulo a natural equivalence) and show that every finite Heyting chain satisfies this condition, thereby confirming a conjecture of Davey and Pitkethly.     

Sphere Packing, III. Extremal Cases

This paper is the third in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In the previous paper in this series, a continuous function f on a compact space was defined, certain points in the domain were conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture was established. This paper shows that those points are indeed local maxima. Various approximations to f are developed, that will be used in subsequent papers to bound the value of the function f. The function f can be expressed as a sum of terms, indexed by regions on a unit sphere. Detailed estimates of the terms corresponding to triangular and quadrilateral regions are developed.     

A quantitative program for Hadwiger’s covering conjecture

In 1957,Hadwiger made a conjecture that every n-dimensional convex body can be covered by 2n translates of its interior.Up to now,this conjecture is still open for all n 3.In 1933,Borsuk made a conjecture that every n-dimensional bounded set can be divided into n + 1 subsets of smaller diameters.Up to now,this conjecture is open for 4 n 297.In this article we encode the two conjectures into continuous functions defined on the spaces of convex bodies,propose a four-step program to attack them,and obtain some partial results.     

Sphere Packings, VI. Tame Graphs and Linear Programs

This paper is the sixth and final part in a series of papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In a previous paper in this series, a continuous function f on a compact space is defined, certain points in the domain are conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture is established. In this paper we consider the set of all points in the domain for which the value of f is at least the conjectured maximum. To each such point, we attach a planar graph. It is proved that each such graph must be isomorphic to a tame graph, of which there are only finitely many up to isomorphism. Linear programming methods are then used to eliminate all possibilities, except for three special cases treated in earlier papers: pentahedral prisms, the face-centered cubic packing, and the hexagonal-close packing. The results of this paper rely on long computer calculations.     

On the local-global conjecture for integral Apollonian gaskets

We prove that a set of density one satisfies the local-global conjecture for integral Apollonian gaskets. That is, for a fixed integral, primitive Apollonian gasket, almost every (in the sense of density) admissible (passing local obstructions) integer is the curvature of some circle in the gasket.     

Towards a proof of the 24-cell conjecture

This review paper is devoted to the problems of sphere packings in 4 dimensions. The main goal is to find reasonable approaches for solutions to problems related to densest sphere packings in 4-dimensional Euclidean space. We consider two long-standing open problems: the uniqueness of maximum kissing arrangements in 4 dimensions and the 24-cell conjecture. Note that a proof of the 24-cell conjecture also proves that the lattice packing D₄ is the densest sphere packing in 4 dimensions.     

On the convergence of circle packings to the Riemann map

Rodin and Sullivan (1987) proved Thurston’s conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby providing a refreshing geometric view of Riemann’s Mapping Theorem. We now present a new proof of the Rodin–Sullivan theorem. This proof is based on the argument principle, and has the following virtues. 1. It applies to more general packings. The Rodin–Sullivan paper deals with packings based on the hexagonal combinatorics. Later, quantitative estimates were found, which also worked for bounded valence packings. Here, the bounded valence assumption is unnecessary and irrelevant. 2. Our method is rather elementary, and accessible to non-experts. In particular, quasiconformal maps are not needed. Consequently, this gives an independent proof of Riemann’s Conformal Mapping Theorem. (The Rodin–Sullivan proof uses results that rely on Riemann’s Mapping Theorem.) 3. Our approach gives the convergence of the first and second derivatives, without significant additional difficulties. While previous work has established the convergence of the first two derivatives for bounded valence packings, now the bounded valence assumption is unnecessary. Oblatum 15-V-1995 & 13-XI-1995     

Guest Editors' Foreword

This issue of Discrete & Computational Geometry contains the detailed proof by T. Hales and S.P. Ferguson of the Kepler conjecture that the densest packing of three-dimensional Euclidean space by equal spheres is attained by "cannonball" packing. This is a landmark result. This conjecture, formulated by Kepler in 1611, was stated in Hilbert's formulation of his 18th problem [8]. The proof consists of mathematical arguments and a massive computer verification of many inequalities.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.