Complete positivity and distance-avoiding sets

DOI10.1007/S10107-020-01562-6zbMATH Open1495.46060arXiv1804.09099OpenAlexW3085001351MaRDI QIDQ2118086FDOQ2118086

Fernando Mário de Oliveira Filho, Evan DeCorte, Frank Vallentin

Publication date: 22 March 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1804.09099

Recommendations

• Measurable sets with excluded distances
• On the density of sets avoiding parallelohedron distance 1
• The density of sets avoiding distance 1 in Euclidean space
• Fourier analysis, linear programming, and densities of distance avoiding sets in \(\mathbb R^n\)
• Spherical sets avoiding a prescribed set of angles

zbMATH Keywords

semidefinite programmingharmonic analysischromatic number of Euclidean spacecopositive programmingHadwiger-Nelson problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Erd?s problems and related topics of discrete geometry (52C10) Semi-infinite programming (90C34) Distance geometry (51K99)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Geometric algorithms and combinatorial optimization
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• The realization of distances in measurable subsets covering \(R^ n\).
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The density of sets avoiding distance 1 in Euclidean space
• Positive definite functions on spheres
• Title not available (Why is that?)
• The realization of distances within sets in Euclidean space
• Geometry of cuts and metrics
• Fourier analysis, linear programming, and densities of distance avoiding sets in \(\mathbb R^n\)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• A Szemerédi type theorem for sets of positive density in \(\mathbb R^k\)
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Curvatures of left invariant metrics on Lie groups
• Better bounds for planar sets avoiding unit distances
• Title not available (Why is that?)
• Spherical codes and designs
• A comparison of the Delsarte and Lovász bounds
• Convexity
• New upper bounds on sphere packings. I
• The sphere packing problem in dimension \(24\)
• Lower bounds for measurable chromatic numbers
• A semidefinite programming hierarchy for packing problems in discrete geometry
• A copositive formulation for the stability number of infinite graphs
• Spherical Sets Avoiding a Prescribed Set of Angles
• Title not available (Why is that?)
• A quantitative version of Steinhaus' theorem for compact, connected, rank-one symmetric spaces
• Measurable sets with excluded distances
• Title not available (Why is that?)
• Linear inequalities and quadratic forms
• A linear programming reformulation of the standard quadratic optimization problem
• Plane Sets with Positive Density at Infinity Contain all Large Distances
• The sphere packing problem in dimension 8
• A COUNTEREXAMPLE TO A CONJECTURE OF LARMAN AND ROGERS ON SETS AVOIDING DISTANCE 1
• Problems, problems, problems
• Some old and new problems in combinatorial geometry I: around Borsuk's problem
• On the Turing model complexity of interior point methods for semidefinite programming
• Spherical Sets Without Orthogonal Point Pairs

Cited In (6)

• A recursive Lovász theta number for simplex-avoiding sets
• On the structure of sets with positive reach
• A COUNTEREXAMPLE TO A CONJECTURE OF LARMAN AND ROGERS ON SETS AVOIDING DISTANCE 1
• The density of planar sets avoiding unit distances
• Density estimates of 1-avoiding sets via higher order correlations
• A positive fraction mutually avoiding sets theorem

This page was built for publication: Complete positivity and distance-avoiding sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118086)