Geodesic
The chromatic number of the space $(\mathbb R^n, l_1)$
Sbornik. Mathematics, Tome 209 (2018) no. 10, pp. 1445-1462 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The chromatic number of the space $(\mathbb R^n)$ with the $l_1$ metric $\| x\|=\sum_{i=1}^n{|x_i|}$ with $k$ forbidden distances is studied. It is defined as the minimum number of colours needed to colour all points in the space in such a way that no two points lying at a forbidden distance from each other in the $l_1$ metric have the same colour. The asymptotic growth of the chromatic numbers as $n\to\infty$ is estimated. The instrument of study is the linear algebra method, which reduces the problem of estimating chromatic numbers to another convex extremum problem. A numerical solution of this problem makes it possible to derive sharp estimates for the constants present in the bases of the lower asymptotic estimates for the chromatic numbers of multidimensional real spaces with several forbidden distances. The estimates obtained are optimal within the framework of the method proposed. Bibliography: 27 titles.
Keywords: chromatic number, linear algebra method, convex problem. 
@article{SM_2018_209_10_a1,
     author = {E. S. Gorskaya and I. M. Mitricheva},
     title = {The chromatic number of the space $(\mathbb R^n, l_1)$},
     journal = {Sbornik. Mathematics},
     pages = {1445--1462},
     year = {2018},
     volume = {209},
     number = {10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2018_209_10_a1/}
}
TY  - JOUR
AU  - E. S. Gorskaya
AU  - I. M. Mitricheva
TI  - The chromatic number of the space $(\mathbb R^n, l_1)$
JO  - Sbornik. Mathematics
PY  - 2018
SP  - 1445
EP  - 1462
VL  - 209
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/SM_2018_209_10_a1/
LA  - en
ID  - SM_2018_209_10_a1
ER  - 
%0 Journal Article
%A E. S. Gorskaya
%A I. M. Mitricheva
%T The chromatic number of the space $(\mathbb R^n, l_1)$
%J Sbornik. Mathematics
%D 2018
%P 1445-1462
%V 209
%N 10
%U http://geodesic.mathdoc.fr/item/SM_2018_209_10_a1/
%G en
%F SM_2018_209_10_a1
E. S. Gorskaya; I. M. Mitricheva. The chromatic number of the space $(\mathbb R^n, l_1)$. Sbornik. Mathematics, Tome 209 (2018) no. 10, pp. 1445-1462. http://geodesic.mathdoc.fr/item/SM_2018_209_10_a1/

[1] H. Hadwiger, “Ungelöste Probleme No 40”, Elemente der Math., 16 (1961), 103–104

[2] P. Erdös, “Some unsolved problems”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 6 (1961), 221–254 | MR | Zbl

[3] P. Erdös, “On some problems of elementary and combinatorial geometry”, Ann. Mat. Pura Appl. (4), 103 (1975), 99–108 | DOI | MR | Zbl

[4] M. Gardner, “Mathematical games”, Sci. Amer., 203 (1960), 172–180 | DOI

[5] L. Moser, W. Moser, “Solution to problem $10$”, Canad. Math. Bull., 4 (1961), 187–189

[6] A. Yu. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosv., ser. 3, 8, MTsNMO, M., 2004, 186–221

[7] M. Benda, M. Perles, “Colorings of metric spaces”, Geombinatorics, 9:3 (2000), 113–126 | MR | Zbl

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

[9] D. E. Raiskii, “Realization of all distances in a decomposition of the space $R^n$ into $n+1$ parts”, Math. Notes, 7:3 (1970), 194–196 | DOI | MR | Zbl

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

[11] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

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

[13] A. M. Raigorodskii, “The chromatic number of a space with the metric $l_q$”, Russian Math. Surveys, 59:5 (2004), 973–975 | DOI | DOI | MR | Zbl

[14] E. S. Gorskaya, I. M. Mitricheva, V. Yu. Protasov, A. M. Raigorodskii, “Estimating the chromatic numbers of Euclidean space by convex minimization methods”, Sb. Math., 200:6 (2009), 783–801 | DOI | DOI | MR | Zbl

[15] A. M. Raigorodskii, “O khromaticheskikh chislakh metricheskikh prostranstv”, Chebyshevskii sb., 5:1(9) (2004), 165–173 | MR | Zbl

[16] Z. Füredi, Jeong-Hyun Kang, “Distance graph on $ {\mathbb Z}^n $ with $ \ell_1 $-norm”, Theoret. Comput. Sci., 319:1-3 (2004), 357–366 | DOI | MR | Zbl

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

[18] 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 | DOI | MR | Zbl

[19] F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, MA–Menlo Park, CA–London, 1969, ix+274 pp. | MR | MR | Zbl | Zbl

[20] N. G. de Bruijn, 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), 371–373 | MR | Zbl

[21] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., Wiley-Interscience [John Wiley Sons], New York, 2000, xviii+301 pp. | DOI | MR | Zbl

[22] L. Babai, P. Frankl, Linear algebra methods in combinatorics, Part 1, Preliminary version 2, Department of Computer Science, Univ. of Chicago, 1992

[23] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007, 138 pp. | Zbl

[24] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl

[25] Y. Nesterov, A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Stud. Appl. Math., 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994, x+405 pp. | DOI | MR | Zbl

[26] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge Univ. Press, Cambridge, 2004, xiv+716 pp. | DOI | MR | Zbl

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