Geodesic
Distance Graphs with Large Chromatic Number and without Large Cliques
Matematičeskie zametki, Tome 87 (2010) no. 3, pp. 417-428.

Voir la notice de l'article provenant de la source Math-Net.Ru

The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach.
Keywords: distance graph, chromatic number, Stirling's formula, Euclidean space, probability space, random variable, expectation.
Mots-clés : clique 
@article{MZM_2010_87_3_a9,
     author = {A. M. Raigorodskii and O. I. Rubanov},
     title = {Distance {Graphs} with {Large} {Chromatic} {Number} and without {Large} {Cliques}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {417--428},
     publisher = {mathdoc},
     volume = {87},
     number = {3},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2010_87_3_a9/}
}
TY  - JOUR
AU  - A. M. Raigorodskii
AU  - O. I. Rubanov
TI  - Distance Graphs with Large Chromatic Number and without Large Cliques
JO  - Matematičeskie zametki
PY  - 2010
SP  - 417
EP  - 428
VL  - 87
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2010_87_3_a9/
LA  - ru
ID  - MZM_2010_87_3_a9
ER  - 
%0 Journal Article
%A A. M. Raigorodskii
%A O. I. Rubanov
%T Distance Graphs with Large Chromatic Number and without Large Cliques
%J Matematičeskie zametki
%D 2010
%P 417-428
%V 87
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2010_87_3_a9/
%G ru
%F MZM_2010_87_3_a9
A. M. Raigorodskii; O. I. Rubanov. Distance Graphs with Large Chromatic Number and without Large Cliques. Matematičeskie zametki, Tome 87 (2010) no. 3, pp. 417-428. http://geodesic.mathdoc.fr/item/MZM_2010_87_3_a9/

[1] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | MR | Zbl

[2] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosveschenie, 8, MTsNMO, M., 2004, 185–221

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

[4] A. M. Raigorodskii, Khromaticheskie chisla, MTsNMO, M., 2003

[5] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[6] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer-Verlag, New York, NY, 2005 | MR | Zbl

[7] F. Kharari, Teoriya grafov, Mir, M., 1973 | MR | Zbl

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

[9] 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:5 (1951), 371–373 | MR | Zbl

[10] O. Nechushtan, “On the space chromatic number”, Discrete Math., 256:1–2 (2002), 499–507 | DOI | MR | Zbl

[11] L. L. Ivanov, “Otsenka khromaticheskogo chisla prostranstva $\mathbb R^4$”, UMN, 61:5 (2006), 181–182 | MR | Zbl

[12] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (2000), 147–148 | MR | Zbl

[13] “Unsolved problems”, Congr. Numer., 15 (1976), 678–691 | MR

[14] N. Wormald, “A 4-chromatic graph with a special plane drawing”, J. Austral. Math. Soc. Ser. A, 28:1 (1979), 1–8 | DOI | MR | Zbl

[15] R. Hochberg, P. O'Donnel, “Some 4-chromatic unit-distance graphs without small cycles”, Geombinatorics, 5:4 (1996), 137–141 | MR | Zbl

[16] O. I. Rubanov, “Khromaticheskie chisla trekhmernykh grafov rasstoyanii, ne soderzhaschikh tetraedrov”, Matem. zametki, 82:5 (2007), 797–800 | MR | Zbl

[17] K. Prakhar, Raspredelenie prostykh chisel, Mir, M., 1967 | MR | Zbl

[18] N. Alon, Dzh. Spenser, Veroyatnostnyi metod, Binom. Laboratoriya znanii, M., 2007 | MR | Zbl

[19] A. M. Raigorodskii, Veroyatnost i algebra v kombinatorike, MTsNMO, Moskva, 2008