Estimating the chromatic numbers of Euclidean space by convex minimization methods

E. S. Gorskaya   ; I. M. Mitricheva (Shitova)   ; V. Yu. Protasov   ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 200 (2009) no. 6, pp. 783-801

Résumé

The chromatic numbers of the Euclidean space ${\mathbb R}^n$ with $k$ forbidden distances are investigated (that is, the minimum numbers of colours necessary to colour all points in ${\mathbb R}^n$ so that no two points of the same colour lie at a forbidden distance from each other). Estimates for the growth exponents of the chromatic numbers as $n\to\infty$ are obtained. The so-called linear algebra method which has been developed is used for this. It reduces the problem of estimating the chromatic numbers to an extremal problem. To solve this latter problem a fundamentally new approach is used, which is based on the theory of convex extremal problems and convex analysis. This allows the required estimates to be found for any $k$. For $k\le20$ these estimates are found explicitly; they are the best possible ones in the framework of the method mentioned above. Bibliography: 18 titles.

Détail

Keywords: chromatic number, distance graph, convex optimization.

Bibliographie

[1] A. M. Raigorodskii, “Borsuk's problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | DOI | MR | Zbl

[2] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, Moskva, 2007

[3] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics. II (Budapest, Hungary, 1999), Bolyai Soc. Math. Stud., 11, Springer-Veerlag, Berlin; Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[4] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer-Verlag, New York, 2005 | MR | Zbl

[5] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosveschenie, 2004, no. 8, 186–221

[6] A. M. Raigorodskii, “On the chromatic number of a space”, Russian Math. Surveys, 55:2 (2000), 351–352 | DOI | MR | Zbl

[7] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | MR | Zbl

[8] I. M. Shitova, “On the chromatic number of a space with several forbidden distances”, Dokl. Math., 75:2 (2007), 228–230 | DOI | MR | Zbl

[9] A. M. Raigorodskii, I. M. Shitova, “Chromatic numbers of real and rational spaces with real or rational forbidden distances”, Sb. Math., 199:4 (2008), 579–612 | DOI | MR | Zbl

[10] N. G. Moshchevitin, A. M. Raigorodskii, “Colorings of the space $\mathbb R^n$ with several forbidden distances”, Math. Notes, 81:5–6 (2007), 656–664 | DOI | MR | Zbl

[11] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wet., Proc., Ser. A, 54:5 (1951), 371–373 | Zbl

[12] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 2000 | MR | Zbl

[13] K. Prachar, Primzahlverteilung, Grundlehren Math. Wiss., 91, Springer-Verlag, Berlin–Göttingen–Heidelberg, 1957 | MR | MR | Zbl | Zbl

[14] G. G. Magaril-Il'yaev, V. M. Tikhomirov, Convex analysis: theory and applications, Transl. Math. Monogr., 222, Amer. Math. Soc., Providence, RI, 2003 | MR | Zbl

[15] V. Yu. Protasov, “Algorithms for approximate calculation of the minimum of a convex function from its values”, Math. Notes, 59:1 (1996), 69–74 | DOI | MR | Zbl

[16] Y. Nesterov, A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Stud. Appl. Math., 13, SIAM, Philadelphia, PA, 1994 | MR | Zbl

[17] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge Univ. Press, Cambridge, 2004 | MR | Zbl

[18] E, C. Titchmarsh, The theory of functions, Oxford Univ. Press, Oxford, 1939 | MR | Zbl | Zbl