A recursive Lovász theta number for simplex-avoiding sets

Castro-Silva, Davi; de Oliveira Filho, Fernando; Slot, Lucas; Vallentin, Frank

doi:10.1090/proc/15940

A recursive Lovász theta number for simplex-avoiding sets
HTML articles powered by AMS MathViewer

by Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot and Frank Vallentin PDF

Proc. Amer. Math. Soc. 150 (2022), 3307-3322 Request permission

Abstract:

We recursively extend the Lovász theta number to geometric hypergraphs on the unit sphere and on Euclidean space, obtaining an upper bound for the independence ratio of these hypergraphs. As an application we reprove a result in Euclidean Ramsey theory in the measurable setting, namely that every $k$-simplex is exponentially Ramsey, and we improve existing bounds for the base of the exponential.

References

George E. Andrews, Richard Askey, and Ranjan Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR 1688958, DOI 10.1017/CBO9781107325937
Christine Bachoc, Evan DeCorte, Fernando Mário de Oliveira Filho, and Frank Vallentin, Spectral bounds for the independence ratio and the chromatic number of an operator, Israel J. Math. 202 (2014), no. 1, 227–254. MR 3265319, DOI 10.1007/s11856-014-1070-7
Christine Bachoc, Gabriele Nebe, Fernando Mário de Oliveira Filho, and Frank Vallentin, Lower bounds for measurable chromatic numbers, Geom. Funct. Anal. 19 (2009), no. 3, 645–661. MR 2563765, DOI 10.1007/s00039-009-0013-7
Christine Bachoc, Alberto Passuello, and Alain Thiery, The density of sets avoiding distance 1 in Euclidean space, Discrete Comput. Geom. 53 (2015), no. 4, 783–808. MR 3341578, DOI 10.1007/s00454-015-9668-z
N. G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A. 54 = Indagationes Math. 13 (1951), 369–373. MR 0046630
Henry Cohn and Noam Elkies, New upper bounds on sphere packings. I, Ann. of Math. (2) 157 (2003), no. 2, 689–714. MR 1973059, DOI 10.4007/annals.2003.157.689
Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach, Progression-free sets in $\Bbb Z^n_4$ are exponentially small, Ann. of Math. (2) 185 (2017), no. 1, 331–337. MR 3583357, DOI 10.4007/annals.2017.185.1.7
E. DeCorte, F.M. de Oliveira Filho, and F. Vallentin, Complete positivity and distance-avoiding sets, Mathematical Programming, Series A, 2020, p. 72, DOI: 10.1007/s10107-020-01562-6, arXiv:1804:09099.
P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
Árpád Elbert and Andrea Laforgia, Upper bounds for the zeros of ultraspherical polynomials, J. Approx. Theory 61 (1990), no. 1, 88–97. MR 1047150, DOI 10.1016/0021-9045(90)90025-L
Jordan S. Ellenberg and Dion Gijswijt, On large subsets of $\Bbb F^n_q$ with no three-term arithmetic progression, Ann. of Math. (2) 185 (2017), no. 1, 339–343. MR 3583358, DOI 10.4007/annals.2017.185.1.8
K. J. Falconer, The realization of distances in measurable subsets covering $\textbf {R}^{n}$, J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189. MR 629593, DOI 10.1016/0097-3165(81)90014-5
Peter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259–286. MR 871675, DOI 10.1090/S0002-9947-1987-0871675-6
P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
Michel X. Goemans, Semidefinite programming in combinatorial optimization, Math. Programming 79 (1997), no. 1-3, Ser. B, 143–161. Lectures on mathematical programming (ismp97) (Lausanne, 1997). MR 1464765, DOI 10.1016/S0025-5610(97)00051-8
Aubrey D. N. J. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28 (2018), no. 1, 18–31. MR 3820926
David de Laat, Fernando Mário de Oliveira Filho, and Frank Vallentin, Upper bounds for packings of spheres of several radii, Forum Math. Sigma 2 (2014), Paper No. e23, 42. MR 3264261, DOI 10.1017/fms.2014.24
L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, IT-25 (1979) 1–7.
R. J. McEliece, E. R. Rodemich, and H. C. Rumsey Jr., The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978), no. 3, 134–152. MR 505587
Eric Naslund, Monochromatic equilateral triangles in the unit distance graph, Bull. Lond. Math. Soc. 52 (2020), no. 4, 687–692. MR 4171395, DOI 10.1112/blms.12359
Fernando Mário de Oliveira Filho and Frank Vallentin, Computing upper bounds for the packing density of congruent copies of a convex body, New trends in intuitive geometry, Bolyai Soc. Math. Stud., vol. 27, János Bolyai Math. Soc., Budapest, 2018, pp. 155–188. MR 3889260
Fernando Mário de Oliveira Filho and Frank Vallentin, Fourier analysis, linear programming, and densities of distance avoiding sets in $\Bbb R^n$, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 6, 1417–1428. MR 2734347, DOI 10.4171/JEMS/236
Michael Reed and Barry Simon, Methods of modern mathematical physics. II. Fourier analysis, self-adjointness, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0493420
A. A. Sagdeev, An improved Frankl-Rödl theorem and some of its geometric consequences, Problemy Peredachi Informatsii 54 (2018), no. 2, 45–72 (Russian, with Russian summary); English transl., Probl. Inf. Transm. 54 (2018), no. 2, 139–164. MR 3845496, DOI 10.1134/s0032946018020047
A. A. Sagdeev, On a Frankl-Rödl theorem, Izv. Ross. Akad. Nauk Ser. Mat. 82 (2018), no. 6, 128–157 (Russian, with Russian summary); English transl., Izv. Math. 82 (2018), no. 6, 1196–1224. MR 3881768, DOI 10.4213/im8630
I. J. Schoenberg, Metric spaces and completely monotone functions, Ann. of Math. (2) 39 (1938), no. 4, 811–841. MR 1503439, DOI 10.2307/1968466
I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108. MR 5922, DOI 10.1215/S0012-7094-42-00908-6
Alexander Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979), no. 4, 425–429. MR 536232, DOI 10.1109/TIT.1979.1056072
Alexander Soifer, The mathematical coloring book, Springer, New York, 2009. Mathematics of coloring and the colorful life of its creators; With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. MR 2458293, DOI 10.1007/978-0-387-74642-5
Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
T. Tao, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, https://terrytao.wordpress.com, 2016.
J. G. Wendel, Note on the gamma function, Amer. Math. Monthly 55 (1948), 563–564. MR 29448, DOI 10.2307/2304460