Complete positivity and distance-avoiding sets. (English) Zbl 1495.46060
Summary: 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.
MSC:
| 46N10 | Applications of functional analysis in optimization, convex analysis, mathematical programming, economics |
| 52C10 | Erdős problems and related topics of discrete geometry |
| 51K99 | Distance geometry |
| 90C22 | Semidefinite programming |
| 90C34 | Semi-infinite programming |
Keywords:
Hadwiger-Nelson problem; chromatic number of Euclidean space; semidefinite programming; copositive programming; harmonic analysisReferences:
| [1] | Bachoc, C.; Nebe, G.; de Oliveira Filho, FM; Vallentin, F., Lower bounds for measurable chromatic numbers, Geom. Funct. Anal., 19, 645-661 (2009) · Zbl 1214.05022 |
| [2] | Bachoc, C.; Passuello, A.; Thiery, A., The density of sets avoiding distance 1 in Euclidean space, Discrete Comput. Geom., 53, 783-808 (2015) · Zbl 1327.52032 |
| [3] | Barvinok, A., A Course in Convexity. Graduate Studies in Mathematics 54 (2002), Providence, RI: American Mathematical Society, Providence, RI · Zbl 1014.52001 |
| [4] | Bochner, S., Hilbert distances and positive definite functions, Ann. Math., 42, 647-656 (1941) · JFM 67.0691.02 |
| [5] | Bourgain, J., A Szemerédi type theorem for sets of positive density in \({\mathbb{R}}^k\), Isr. J. Math., 54, 307-316 (1986) · Zbl 0609.10043 |
| [6] | Bukh, B., Measurable sets with excluded distances, Geom. Funct. Anal., 18, 668-697 (2008) · Zbl 1169.52005 |
| [7] | Cohn, H.; Elkies, N., New upper bounds on sphere packings I, Ann. Math., 157, 689-714 (2003) · Zbl 1041.52011 |
| [8] | Cohn, H.; Kumar, A.; Miller, SD; Radchenko, D.; Viazovska, M., The sphere packing problem in dimension 24, Ann. Math., 185, 1017-1033 (2017) · Zbl 1370.52037 |
| [9] | de Klerk, E.; Pasechnik, DV, A linear programming reformulation of the standard quadratic optimization problem, J. Global Optim., 37, 75-84 (2007) · Zbl 1127.90051 |
| [10] | de Klerk, E.; Vallentin, F., On the Turing model complexity of interior point methods for semidefinite programming, SIAM J. Optim., 26, 1944-1961 (2016) · Zbl 1346.90661 |
| [11] | de Laat, D.; Vallentin, F., A semidefinite programming hierarchy for packing problems in discrete geometry, Math. Program. Ser. B, 151, 529-553 (2015) · Zbl 1328.90102 |
| [12] | de Oliveira Filho, FM; Vallentin, F., Fourier analysis, linear programming, and densities of distance-avoiding sets in \(\mathbb{R }^n\), J. Eur. Math. Soc., 12, 1417-1428 (2010) · Zbl 1205.90196 |
| [13] | de Oliveira Filho, FM; Vallentin, F., A quantitative version of Steinhaus’s theorem for compact, connected, rank-one symmetric spaces, Geom. Dedicata, 167, 295-307 (2013) · Zbl 1285.53042 |
| [14] | de Oliveira Filho, FM; Vallentin, F., A counterexample to a conjecture of Larman and Rogers on sets avoiding distance 1, Mathematika, 65, 785 (2019) · Zbl 1433.52019 |
| [15] | DeCorte, E.; Pikhurko, O., Spherical sets avoiding a prescribed set of angles, Int. Math. Res. Not., 20, 6095-6117 (2016) · Zbl 1404.28005 |
| [16] | Delsarte, P.; Goethals, JM; Seidel, JJ, Spherical codes and designs, Geom. Dedicata, 6, 363-388 (1977) · Zbl 0376.05015 |
| [17] | Deza, MM; Laurent, M., Geometry of Cuts and Metrics. Algorithms and Combinatorics 15 (1997), Berlin: Springer, Berlin · Zbl 0885.52001 |
| [18] | Dobre, C.; Dür, ME; Frerick, L.; Vallentin, F., A copositive formulation of the stability number of infinite graphs, Math. Program. Ser. A, 160, 65-83 (2016) · Zbl 1361.05091 |
| [19] | Falconer, KJ, The realization of distances in measurable subsets covering \({\mathbb{R}}^n\), J. Comb. Theory Ser. A, 31, 184-189 (1981) · Zbl 0469.05021 |
| [20] | Falconer, KJ; Marstrand, JM, Plane sets with positive density at infinity contain all large distances, Bull. Lond. Math. Soc., 18, 471-474 (1986) · Zbl 0599.28008 |
| [21] | Federer, H., Geometric Measure Theory. Die Grundlehren der mathematischen Wissenschaften (1969), New York: Springer, New York · Zbl 0176.00801 |
| [22] | Folland, GB, Real Analysis: Modern Techniques and Their Applications (1999), New York: Wiley, New York · Zbl 0924.28001 |
| [23] | Furstenberg, H.; Katznelson, Y.; Weiss, B.; Nešetřil, J.; Rödl, V., Ergodic theory and configurations in sets of positive density, Mathematics of Ramsey Theory, 184-198 (1990), Berlin: Springer, Berlin · Zbl 0738.28013 |
| [24] | Gaddum, JW, Linear inequalities and quadratic forms, Pac. J. Math., 8, 411-414 (1958) · Zbl 0086.01901 |
| [25] | Grötschel, M.; Lováász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics 2 (1988), Berlin: Springer, Berlin · Zbl 0634.05001 |
| [26] | Kalai, G.: Some old and new problems in combinatorial geometry I: around Borsuk’s problem. In: Surveys in combinatorics 2015, London Mathematical Society Lecture Note Series 424. Cambridge University Press, Cambridge, pp. 147-174 (2015) · Zbl 1361.51008 |
| [27] | Karp, RM; Miller, RE; Thatcher, JW, Reducibility among combinatorial problems, Complexity of Computer Computations (Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1972), 85-103 (1972), New York: Plenum Press, New York · Zbl 1467.68065 |
| [28] | Keleti, T.; Matolcsi, M.; de Oliveira Filho, FM; Ruzsa, IZ, Better bounds for planar sets avoiding unit distances, Discrete Comput. Geom., 55, 642-661 (2016) · Zbl 1335.05048 |
| [29] | Larman, DG; Rogers, CA, The realization of distances within sets in Euclidean space, Mathematika, 19, 1-24 (1972) · Zbl 0246.05020 |
| [30] | Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, IT-25, 1-7 (1979) · Zbl 0395.94021 |
| [31] | Lovász, L.; Szegedy, B., Limits of dense graph sequences, J. Comb. Theory Ser. B, 96, 933-957 (2006) · Zbl 1113.05092 |
| [32] | Mattila, P., Geometry of Sets and Measures in Euclidean Space: Fractals and Rectifiability, Cambridge Studies in Advanced Mathematics 44 (1995), Cambridge: Cambridge University Press, Cambridge · Zbl 0819.28004 |
| [33] | McEliece, RJ; Rodemich, ER; Rumsey, HC, The Lovász bound and some generalizations, J. Comb. Inf. Syst. Sci., 3, 134-152 (1978) · Zbl 0408.05031 |
| [34] | Milnor, J., Curvatures of left invariant metrics on Lee groups, Adv. Math., 21, 293-329 (1976) · Zbl 0341.53030 |
| [35] | Moser, WOJ, Problems, problems, problems, Discrete Appl. Math., 31, 201-225 (1991) · Zbl 0817.52002 |
| [36] | Motzkin, TS; Straus, EG, Maxima for graphs and a new proof of a theorem of Turán, Can. J. Math., 17, 533-540 (1965) · Zbl 0129.39902 |
| [37] | Padberg, M., The Boolean quadric polytope: some characteristics, facets and relatives, Math. Program. Ser. B, 45, 139-172 (1989) · Zbl 0675.90056 |
| [38] | Reed, M.; Simon, B., Methods of Modern Mathematical Physics II: Fourier Analysis, Self-adjointness (1975), New York: Academic Press, New York · Zbl 0308.47002 |
| [39] | Schoenberg, IJ, Metric spaces and completely monotone functions, Ann. Math., 39, 811-841 (1938) · JFM 64.0617.03 |
| [40] | Schoenberg, IJ, Positive definite functions on spheres, Duke Math. J., 9, 96-108 (1942) · Zbl 0063.06808 |
| [41] | Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inf. Theory, IT-25, 425-429 (1979) · Zbl 0444.94009 |
| [42] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2003), Berlin: Springer, Berlin · Zbl 1041.90001 |
| [43] | Simon, B., Convexity: An Analytic Viewpoint, Cambridge Tracts in Mathematics 187 (2011), Cambridge: Cambridge University Press, Cambridge · Zbl 1229.26003 |
| [44] | Szegö, G., Orthogonal Polynomials. American Mathematical Society Colloquium Publications Volume XXIII (1975), Providence: American Mathematical Society, Providence · Zbl 0305.42011 |
| [45] | Székely, LA; Halász, G.; Lovász, L.; Simonovits, M.; Sós, VT, Erdős on unit distances and the Szemerédi-Trotter theorems, Paul Erdős and His Mathematics II Bolyai Society Mathematical Studies 11, János Bolyai Mathematical Society, Budapest, 646-666 (2002), Berlin: Springer, Berlin · Zbl 1035.05037 |
| [46] | Viazovska, MS, The sphere packing problem in dimension 8, Ann. Math., 185, 991-1015 (2017) · Zbl 1373.52025 |
| [47] | Watson, GN, A Treatise on the Theory of Bessel Functions (1922), Cambridge: Cambridge University Press, Cambridge · JFM 48.0412.02 |
| [48] | Witsenhausen, HS, Spherical sets without orthogonal point pairs, Am. Math. Mon., 10, 1101-1102 (1974) · Zbl 0297.52010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
