×

The density of sets avoiding distance 1 in Euclidean space. (English) Zbl 1327.52032

The paper improves on the upper bound for the upper density of sets avoiding two points at unit distance apart in Euclidean spaces, both asymptotically, and numerically for dimensions between 4 and 24. The results depend on the study of an analogue of Lovász’ \(\vartheta\) function for the (infinite) unit distance graph and on some finite subgraphs of the unit distance graph. As a consequence, improved lower bounds are obtained for the measurable chromatic number of the Euclidean space for dimensions between 4 and 24.

MSC:

52C10 Erdős problems and related topics of discrete geometry
90C05 Linear programming
90C27 Combinatorial optimization
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards Applied Mathematics Series, vol. 55. (1964); Reprint: Dover Publications, Mineola NY (1972) · Zbl 0171.38503
[2] Ahlswede, R., Khachatrian, L.: The complete intersection theorem for systems of finite sets. Eur. J. Comb. 18, 125-136 (1997) · Zbl 0869.05066
[3] Andrews, G.E., Askey, R., Roy, R.: Special Functions. Cambridge University Press, Cambridge (1999) · Zbl 0920.33001
[4] Arias de Reyna, J., Toulisse, J.: The \[n\] n-th prime asymptotically. J. Théor. nombres Bordx. 25, 521-555 (2013) · Zbl 1298.11093
[5] Bachoc, C., Nebe, G., de Oliveira Filho, F.M., Vallentin, F.: Lower bounds for measurable chromatic numbers. Geom. Funct. Anal. 19, 645-661 (2009) · Zbl 1214.05022
[6] Bachoc, C., Decorte, E., de Oliveira Filho, F.M., Vallentin, F.: Spectral bounds for the independence ratio and the chromatic number of an operator. Israel J. Math. 202, 227-254 (2014) · Zbl 1302.05047
[7] Barvinok, A.: A Course in Convexity, GSM 54. American Mathematical Society, Providence, RI (2002) · Zbl 1014.52001
[8] Berkelaar, M., Eikland, K., Notebaert, P.: An Open Source (Mixed-Integer) Linear Programming System. lpsolve 5.5.2.0, Licence terms: GNU LGPL. http://lpsolve.sourceforge.net/ · Zbl 0869.05066
[9] de Klerk, E., Pasechnik, D.V.: A note on the stability number of an orthogonality graph. Eur. J. Comb. 28(7), 1971-1979 (2007) · Zbl 1125.05053
[10] de Laat, D., Vallentin, F.: A semidefinite programming hierarchy for packing problems in discrete geometry. Math. Program. Ser. B http://arxiv.org/abs/1311.3789 (2013) · Zbl 1328.90102
[11] de Oliveira Filho, F.M.: New bounds for geometric packings and colorings via harmonic analysis and optimization. Doctoral Thesis, University of Amsterdam. http://www.ime.usp.br/ fmario/pubs.html (2009)
[12] Decorte, E., de Laat, D., Vallentin, F.: Fourier analysis on finite groups and the Lovász theta-number of Cayley graphs. Exp. Math. 23, 146-152 (2014) · Zbl 1296.05120
[13] Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Repts Suppl. 10, 1-97 (1973) · Zbl 1075.05606
[14] Delsarte, P.: Hahn polynomials, discrete harmonics and \[t\] t-designs. SIAM J. Appl. Math. 34(1), 157-166 (1978) · Zbl 0533.05009
[15] Folland, G.B.: A Course in Abstract Harmonic Analysis. CRC Press, LLC, Boca Raton (1995) · Zbl 0857.43001
[16] Frankl, P., Wilson, R.M.: Intersection theorems with geometric consequences. Combinatorica 1, 357-368 (1981) · Zbl 0498.05048
[17] Larman, D.G., Rogers, C.A.: The realization of distances within sets in Euclidean space. Mathematika 19, 1-24 (1972) · Zbl 0246.05020
[18] Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim. 12, 756-769 (2002) · Zbl 1007.90046
[19] Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28, 470-496 (2003) · Zbl 1082.90084
[20] Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1-7 (1979) · Zbl 0395.94021
[21] McEliece, R.J., Rodemich, E.R., Rumsey, H., Welch, L.: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitie. IEEE Trans. Inf. Theory 23, 157-166 (1977) · Zbl 0361.94016
[22] de Oliveira Filho, F.M., Vallentin, F.: Fourier analysis, linear programming, and densities of distance avoiding sets in \[{\mathbb{R}}^nRn\]. J. Eur. Math. Soc. 12, 1417-1428 (2010) · Zbl 1205.90196
[23] Raigorodskii, A.M.: On the chromatic number of a space. Uspekhi Mat. Nauk 55 147-148 (2001); English translation in Russian Math. Surv. 55, 351-352 (2000) · Zbl 0966.05029
[24] Rudin, W.: Fourier Analysis on Groups. Wiley, New York (1962) · Zbl 0107.09603
[25] Rudin, W.: Real and Complex Analysis, 3rd edn. McGraw-Hill, New York (1987) · Zbl 0925.00005
[26] Schrijver, A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25(4), 425-429 (1979) · Zbl 0444.94009
[27] Schrijver, A.: New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inf. Theory 51, 2859-2866 (2005) · Zbl 1298.94152
[28] Soicher, LH; Beineke, LW (ed.); Wilson, RJ (ed.), Computing with graphs and groups, 250-266 (2004), Cambridge · Zbl 1067.05036
[29] Stein, W.A., et al.: Sage Mathematics Software (Version 4.7). The Sage Development Team http://www.sagemath.org (2011) · Zbl 1302.05047
[30] Székely, L.A., Wormald, N.C.: Bounds on the measurable chromatic number of \[{\mathbb{R}}^nRn\]. Discrete Math. 75, 343-372 (1989) · Zbl 0683.05021
[31] Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3-a Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545-581 (1999) · Zbl 0997.90060
[32] Watson, G.N.: A Treatise on the Theory of Bessel Functions. Cambridge University Press, Cambridge (1966) · Zbl 0174.36202
[33] Yamashita, M.; Fujisawa, K.; Fukuda, M.; Kobayashi, K.; Nakta, K.; Nakata, M.; Anjos, MF (ed.); Lasserre, JB (ed.), Latest developments in the SDPA family for solving large-scale SDPs, 687-714 (2012), New York · Zbl 1334.90119
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.