Complete positivity and distance-avoiding sets
- PDF / 760,564 Bytes
- 72 Pages / 439.37 x 666.142 pts Page_size
- 112 Downloads / 202 Views
Series A
Complete positivity and distance-avoiding sets Evan DeCorte1 · Fernando Mário de Oliveira Filho2 · Frank Vallentin3 Received: 11 March 2019 / Accepted: 1 September 2020 © The Author(s) 2020
Abstract We introduce the cone of completely positive functions, a subset of the cone of positivetype 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. Keywords Hadwiger-Nelson problem · Chromatic number of Euclidean space · Semidefinite programming · Copositive programming · Harmonic analysis Mathematics Subject Classification 46N10 · 52C10 · 51K99 · 90C22 · 90C34
Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Locally independent graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The first author was supported by CRM Applied Math Laboratory and NSERC Discovery Grant 2015-0674. Part of this research was carried out while the second author was at the Institute of Mathematics and Statistics of the University of São Paulo; the second author was partially supported by the São Paulo State Science Foundation (FAPESP) under Grant 2013/03447-6. The third author was partially supported by the SFB/TRR 191 “Symplectic Structures in Geometry, Algebra and Dynamics”, funded by the DFG.
B
Fernando Mário de Oliveira Filho [email protected] Evan DeCorte [email protected] Frank Vallentin [email protected]
1
Mathematics and Statistics, McGill University, 805 Sherbrooke W., Montreal, QC H3A 0B9, Canada
2
Delft Institute of Applied Mathematics, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE Delft, The Netherlands
3
Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50931 Köln, Germany
123
E. DeCorte et al. 3 A conic programming formulation for the independence number . . . . . . . . . . . . 4 The completely positive and the copositive cones on compact spaces . . . . . . . . . 5 When is the completely positive formulation exact? . . . . . . . . . . . . . . . . . . 6 Distance graphs on the Euclidean space . . . . . . . . . . . . . . . . . . . . . . . . . 7 The Boolean-quadratic cone and polytope . . . . . . . . . . . . . . . . . . . . . . . . 8 Better upper bounds for the independence number of graphs on the sphere . . . . . . 9 Better upper bounds for the independence density of unit-distance graphs . . . . . . . 10 Sets avoiding many distances in Rn and the computability of the independence density References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
1 Introduction The two prototypical geometrical problems considered in this paper are
Data Loading...
