Complete positivity and distance-avoiding sets
arXiv:1804.09099 · doi:10.1007/s10107-020-01562-6
Abstract
We introduce the cone of completely-positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.
arXiv comment57 pages; final version published at Math. Program
References in corpus (14)
- New upper bounds on sphere packings I
- The sphere packing problem in dimension 24
- The sphere packing problem in dimension 8
- New upper bounds for kissing numbers from semidefinite programming
- Improved sphere packing lower bounds from Hurwitz lattices
- Upper bounds for packings of spheres of several radii
- On the Turing model complexity of interior point methods for semidefinite programming
- Fourier analysis, linear programming, and densities of distance avoiding sets in R^n
- A semidefinite programming hierarchy for packing problems in discrete geometry
- Lower bounds for measurable chromatic numbers
- Better bounds for planar sets avoiding unit distances
- A copositive formulation for the stability number of infinite graphs
- A quantitative version of Steinhaus' theorem for compact, connected, rank-one symmetric spaces
- A counterexample to a conjecture of Larman and Rogers on sets avoiding distance 1
Cited by in corpus (6)
- Density estimates of 1-avoiding sets via higher order correlations
- The density of planar sets avoiding unit distances
- Positive semidefinite approximations to the cone of copositive kernels
- A recursive Lovász theta number for simplex-avoiding sets
- On the support of a non-autocorrelated function on a hyperbolic surface
- On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension