Geodesic
Chromatic numbers of real and rational spaces with real or rational forbidden distances
Sbornik. Mathematics, Tome 199 (2008) no. 4, pp. 579-612 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Several important aspects of the Nelson-Erdős-Hadwiger classical problem of combinatorial geometry are considered. In particular, new lower bounds are obtained for the chromatic numbers of the spaces $\mathbb{R}^n$ and $\mathbb{Q}^n$ with two, three or four forbidden distances. Bibliography: 28 titles. 
@article{SM_2008_199_4_a5,
     author = {A. M. Raigorodskii and I. M. Shitova},
     title = {Chromatic numbers of real and rational spaces with real or rational forbidden distances},
     journal = {Sbornik. Mathematics},
     pages = {579--612},
     year = {2008},
     volume = {199},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2008_199_4_a5/}
}
TY  - JOUR
AU  - A. M. Raigorodskii
AU  - I. M. Shitova
TI  - Chromatic numbers of real and rational spaces with real or rational forbidden distances
JO  - Sbornik. Mathematics
PY  - 2008
SP  - 579
EP  - 612
VL  - 199
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2008_199_4_a5/
LA  - en
ID  - SM_2008_199_4_a5
ER  - 
%0 Journal Article
%A A. M. Raigorodskii
%A I. M. Shitova
%T Chromatic numbers of real and rational spaces with real or rational forbidden distances
%J Sbornik. Mathematics
%D 2008
%P 579-612
%V 199
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2008_199_4_a5/
%G en
%F SM_2008_199_4_a5
A. M. Raigorodskii; I. M. Shitova. Chromatic numbers of real and rational spaces with real or rational forbidden distances. Sbornik. Mathematics, Tome 199 (2008) no. 4, pp. 579-612. http://geodesic.mathdoc.fr/item/SM_2008_199_4_a5/

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

[2] 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

[3] H. Hadwiger, “Ungelöste Probleme”, Elem. Math., 16 (1961), 103–104 | MR | Zbl

[4] 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-Verlag, Berlin; János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

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

[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] A. M. Raigorodskii, “The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs”, Dokl. Math., 68:2 (2003), 216–220 | MR | Zbl

[9] A. M. Raigorodskii, “The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs”, Sb. Math., 196:1 (2005), 115–146 | DOI | MR | Zbl

[10] A. M. Raigorodskii, “On lower bounds for Borsuk and Hadwiger numbers”, Russian Math. Surveys, 59:3 (2004), 585–586 | DOI | MR | Zbl

[11] A. M. Raigorodskii, “On the Borsuk and Erdős–Hadwiger numbers”, Math. Notes, 79:5–6 (2006), 854–863 | DOI | MR | Zbl

[12] A. M. Raigorodskii, “Khromaticheskie chisla distantsionnykh grafov”, Chebyshëvskii sbornik, 6:3(15) (2005), 159–170 | MR

[13] A. M. Raigorodskii, “Some problems in combinatorial geometry, and the linear algebra method in combinatorics”, Chebyshëvskii sbornik, 7:3 (2006), 168–189 | MR

[14] 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

[15] A. M. Raigorodskii, “On the chromatic number of a space with two forbidden distances”, Dokl. Math., 73:3 (2006), 417–420 | DOI | MR

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

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

[18] F. Harary, Graph theory, Addison-Wesley, Reading, MA–Menlo Park, CA–London, 1969 | MR | MR | Zbl | Zbl

[19] 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

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

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

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

[23] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

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

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

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

[27] A. M. Raigorodskii, “O khromaticheskikh chislakh metricheskikh prostranstv”, Chebyshëvskii sbornik, 5:1(9) (2004), 165–173 | MR

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