A Lower Bound on the Density of Sphere Packings via Graph Theory

2004/02/09 by Michael Krivelevich, Krivelevich, Michael, Simon Litsyn +3 · 3 citations
Mathematics · #05C90 #11H31 (Secondary) #52C17 (Primary) 05C69 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:05C69 #msc:05C90 #msc:11H31 #msc:52C17

paper · pdf · doi:10.48550/arxiv.math/0402132

6 pages, 2 postscript figures

arxiv created 2004/02/09 · arxiv updated 2009/12/01

Abstract

Using graph-theoretic methods we give a new proof that for all sufficiently large n, there exist sphere packings in \Rⁿ of density at least cn2^-n, exceeding the classical Minkowski bound by a factor linear in n. This matches up to a constant the best known lower bounds on the density of sphere packings due to Rogers, Davenport-Rogers, and Ball. The suggested method makes it possible to describe the points of such a packing with complexity exp(nlog n), which is significantly lower than in the other approaches.

Cited by

• Probabilistic combinatorics at exponentially small scales
• The entrywise calculus and dimension-free positivity preservers, with an Appendix on sphere packings
• The Eigenvalue Method in Coding Theory

Related

• A new lower bound for sphere packing
• How densely can spheres be packed with moderate effort in high dimensions?
• Lower bounds for sphere packing in arbitrary norms
• Sphere packing bounds via rescaling
• New Conjectural Lower Bounds on the Optimal Density of Sphere Packings