Lower bounds for measurable chromatic numbers. (English) Zbl 1214.05022
Summary: The Lovász theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces.
In particular we consider distance graphs on the unit sphere. There we transform the original infinite semidefinite program into an infinite linear program which then turns out to be an extremal question about Jacobi polynomials which we solve explicitly in the limit. As an application we derive new lower bounds for the measurable chromatic number of the Euclidean space in dimensions \(10,\dots,24\) and we give a new proof that it grows exponentially with the dimension.
In particular we consider distance graphs on the unit sphere. There we transform the original infinite semidefinite program into an infinite linear program which then turns out to be an extremal question about Jacobi polynomials which we solve explicitly in the limit. As an application we derive new lower bounds for the measurable chromatic number of the Euclidean space in dimensions \(10,\dots,24\) and we give a new proof that it grows exponentially with the dimension.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C12 | Distance in graphs |
| 90C22 | Semidefinite programming |
Keywords:
Lovász theta functionReferences:
| [1] | G.E. Andrews, R. Askey, R. Roy, Special Functions, Cambridge University Press, 1999. · Zbl 0920.33001 |
| [2] | Bachoc C.: Linear programming bounds for codes in Grassmannian spaces. IEEE Trans. Inf. Th. 52, 2111–2125 (2006) · Zbl 1282.94106 · doi:10.1109/TIT.2006.872973 |
| [3] | Bochner S.: Hilbert distances and positive definite functions. Ann. of Math. 42, 647–656 (1941) · JFM 67.0691.02 · doi:10.2307/1969252 |
| [4] | de Bruijn N.G., Erdos P.: A colour problem for infinite graphs and a problem in the theory of relations. Indagationes Math. 13, 369–373 (1951) · Zbl 0044.38203 |
| [5] | P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Suppl., 1973. · Zbl 1075.05606 |
| [6] | Delsarte P., Goethals J.M., Seidel J.J.: Spherical codes and designs. Geom. Dedicata 6, 363–388 (1977) · Zbl 0376.05015 · doi:10.1007/BF03187604 |
| [7] | Falconer K.J.: The realization of distances in measurable subsets covering \({\mathbb{R}^{n}}\) . J. Combin. Theory Ser. A 31, 187–189 (1981) · Zbl 0469.05021 · doi:10.1016/0097-3165(81)90014-5 |
| [8] | Frankl P., Rödl V.: Forbidden intersections. Trans. Amer. Math. Soc. 300, 259–286 (1987) · Zbl 0611.05002 · doi:10.1090/S0002-9947-1987-0871675-6 |
| [9] | Frankl P., Wilson R.M.: Intersection theorems with geometric consequences. Combinatorica 1, 357–368 (1981) · Zbl 0498.05048 · doi:10.1007/BF02579457 |
| [10] | Kabatiansky G.A., Levenshtein V.I.: Bounds for packings on a sphere and in space. Problems of Information Transmission 14, 1–17 (1978) |
| [11] | D.E. Knuth, The Sandwich Theorem, Electron. J. Combin. 1 (1994). · Zbl 0810.05065 |
| [12] | Larman D.G., Rogers C.A.: The realization of distances within sets in Euclidean space. Mathematika 19, 1–24 (1972) · Zbl 0246.05020 · doi:10.1112/S0025579300004903 |
| [13] | Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Th. 25, 1–7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985 |
| [14] | Lovász L.: Self-dual polytopes and the chromatic number of distance graphs on the sphere. Acta Sci. Math. 45, 317–323 (1983) · Zbl 0533.05029 |
| [15] | McEliece R.J., Rodemich E.R., Rumsey H.C. Jr.: The Lovász bound and some generalizations. J. Combin. Inf. System Sci. 3, 134–152 (1978) · Zbl 0408.05031 |
| [16] | F. de Oliveira Filho, F. Vallentin, Fourier analysis, linear programming, and densities of distance avoiding sets in \({\mathbb{R}^{n}}\) , J. Eur. Math. Soc., to appear. · Zbl 1205.90196 |
| [17] | Raigorodskii A.M.: On the chromatic number of a space. Uspekhi Mat. Nauk 55, 147–148 (2000) · Zbl 0966.05029 |
| [18] | Schoenberg I.J.: Positive definite functions on spheres. Duke Math. J. 9, 96–108 (1942) · Zbl 0063.06808 · doi:10.1215/S0012-7094-42-00908-6 |
| [19] | Schrijver A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Th. 25, 425–429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072 |
| [20] | G. Szegö, Orthogonal Polynomials, Volume XXIII, Colloqium Publications, American Mathematical Society, 1967. |
| [21] | L.A. Székely, Erdos on unit distances and the Szemerédi-Trotter theorems, in ”Paul Erdos and His Mathematics (G. Halász, L. Lovász, M. Simonovits, V.T. Sós, eds.), Springer, (2002), 649–666. |
| [22] | Székely L.A., Wormald N.C.: Bounds on the measurable chromatic number of \({\mathbb{R}^{n}}\) . Discrete Math. 75, 343–372 (1989) · Zbl 0683.05021 · doi:10.1016/0012-365X(89)90099-X |
| [23] | N.Ja. Vilenkin, A.U. Klimyk, Representation of Lie Groups and Special Functions, Vol. 2, Kluwer Academic Publishers, 1993. · Zbl 0809.22001 |
| [24] | G.N. Watson, A Treatise on the Theory of Bessel Function, Cambridge Mathematical Library, 1995. · Zbl 0849.33001 |
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.
