Two nonoverlapping Euclidean balls are said to kiss if they touch.  An elementary geometrical problem can be posed: Given hyperspheres, each having the same diameter 1, how many hyperspheres can simultaneously kiss one central hypersphere?  The noncentral hyperspheres are allowed, but not required, to kiss (a.k.a, ball packing problem).

As posed, the problem seeks the maximal number of spheres K kissing a central sphere in a particular dimension.  The total number of spheres is N=K+1.  In one dimension the answer to this kissing problem is 2.  In two dimensions, 6.

The question was presented in three dimensions to Isaac Newton in the context of celestial mechanics, and became controversy with David Gregory on the campus of Cambridge University in 1694.  Newton correctly identified the kissing number as 12 while Gregory argued for 13.  Their dispute was finally resolved in 1953 by Schutte & van der Waerden.  In 2003, Oleg Musin tightened the upper bound on kissing number K in four dimensions from 25 to K=24 by refining a method by Philippe Delsarte from 1973 based on linear programming.

There are no proofs known for kissing number in higher dimension excepting dimensions eight and twenty four.

Translating this problem to an EDM graph realization is suggested by Pfender & Ziegler.  Imagine the centers of each sphere are connected by line segments.  Then the distance between centers must obey simple criteria:  Each sphere touching the central sphere has a line segment of length exactly 1 joining its center to the central sphere's center.  All spheres, excepting the central sphere, must have centers separated by a distance of at least 1.

From this perspective, the kissing problem can be posed as a semidefinite program.

Read more...