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/