A semidefinite programming hierarchy for packing problems in discrete geometry
arXiv:1311.3789 · doi:10.1007/s10107-014-0843-4
Abstract
Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre's semidefinite programming hierarchy. We generalize this approach to infinite graphs. For this we introduce topological packing graphs as an abstraction for infinite graphs coming from packing problems in discrete geometry. We show that our hierarchy converges to the independence number.
arXiv comment(v3) 25 pages, this revision fixes a problem in the proof of Lemma 5
References in corpus (9)
- Dense Packings of the Platonic and Archimedean Solids
- New upper bounds on sphere packings I
- New upper bounds for kissing numbers from semidefinite programming
- New upper bounds on sphere packings II
- Upper bounds for packings of spheres of several radii
- Invariant semidefinite programs
- Lower bounds for measurable chromatic numbers
- Three-point bounds for energy minimization
- Computing upper bounds for the packing density of congruent copies of a convex body
Cited by in corpus (12)
- Sphere Packing and Quantum Gravity
- A conceptual breakthrough in sphere packing
- -point semidefinite programming bounds for equiangular lines
- Complete positivity and distance-avoiding sets
- Moment methods in energy minimization: New bounds for Riesz minimal energy problems
- Mathematical optimization for packing problems
- Generalizations of Schoenberg's theorem on positive definite kernels
- Positive semidefinite approximations to the cone of copositive kernels
- Semidefinite programming bounds for error-correcting codes
- A semidefinite programming hierarchy for covering problems in discrete geometry
- Sphere packing bounds via rescaling
- Some old and new problems in combinatorial geometry I: Around Borsuk's problem