Geodesic
Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
Izvestiya. Mathematics , Tome 78 (2014) no. 1, pp. 59-89

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

We study distance graphs with exponentially large chromatic numbers and without $k$-cliques, that is, complete subgraphs of size $k$. Explicit constructions of such graphs use vectors in the integer lattice. For a large class of graphs we find a sharp threshold for containing a $k$-clique. This enables us to improve the lower bounds for the maximum of the chromatic numbers of such graphs. We give a new probabilistic approach to the construction of distance graphs without $k$-cliques, and this yields better lower bounds for the maximum of the chromatic numbers for large $k$.
Keywords: distance graph, chromatic number, clique number, Nelson problem. 
@article{IM2_2014_78_1_a3,
     author = {A. B. Kupavskii},
     title = {Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers},
     journal = {Izvestiya. Mathematics },
     pages = {59--89},
     publisher = {mathdoc},
     volume = {78},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2014_78_1_a3/}
}
TY  - JOUR
AU  - A. B. Kupavskii
TI  - Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
JO  - Izvestiya. Mathematics 
PY  - 2014
SP  - 59
EP  - 89
VL  - 78
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2014_78_1_a3/
LA  - en
ID  - IM2_2014_78_1_a3
ER  - 
%0 Journal Article
%A A. B. Kupavskii
%T Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
%J Izvestiya. Mathematics 
%D 2014
%P 59-89
%V 78
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2014_78_1_a3/
%G en
%F IM2_2014_78_1_a3
A. B. Kupavskii. Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers. Izvestiya. Mathematics , Tome 78 (2014) no. 1, pp. 59-89. http://geodesic.mathdoc.fr/item/IM2_2014_78_1_a3/