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. 
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/
@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},
     year = {2014},
     volume = {78},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/IM2_2014_78_1_a3/
%G en
%F IM2_2014_78_1_a3

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

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

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

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

[5] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics (Budapest, Hungary, 1999), v. II, Bolyai Soc. Math. Stud., 11, Springer-Verlag, Berlin, 2002, 649–666 | MR | Zbl

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

[7] R. Radoičić, G. Tóth, “Note on the chromatic number of the space”, Discrete and computational geometry, Algorithms Combin., 25, Springer-Verlag, Berlin, 2003, 696–698 | MR | Zbl

[8] K. Cantwell, “Finite Euclidean Ramsey theory”, J. Combin. Theory Ser. A, 73:2 (1996), 273–285 | MR | Zbl

[9] J. Cibulka, “On the chromatic number of real and rational spaces”, Geombinatorics, 18:2 (2008), 53–65 | 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] A. B. Kupavskii, A. M. Raigorodskii, “On the chromatic number of $\mathbb R^9$”, J. Math. Sci., 163:6 (2009), 720–731 | DOI | MR

[12] A. B. Kupavskii, “Lifting of a bound for the chromatic number of $\mathbb{R}^n$ to higher dimensions”, Dokl. Math., 80:3 (2009), 833–836 | DOI | MR | Zbl

[13] A. B. Kupavskii, “On the colouring of spheres embedded in $\mathbb R^n$”, Sb. Math., 202:6 (2011), 859–886 | DOI | DOI | MR | Zbl

[14] P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38 | DOI | MR | Zbl

[15] P. Erdős, “Unsolved problems”, Congres Numerantium XV, Utilitas Math., Winnipeg, 1976 | MR

[16] P. O'Donnell, “Arbitrary girth, 4-chromatic unit distance graphs in the plane. I. Graph embedding”, Geombinatorics, 9:3 (2000), 145–150 | MR | Zbl

[17] P. O'Donnell, “Arbitrary girth, 4-chromatic unit distance graphs in the plane. II. Graph embedding”, Geombinatorics, 9:4 (2000), 180–193 | MR | Zbl

[18] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508–538 | DOI | DOI | Zbl

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

[20] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, I, II, North-Holland, Amsterdam–New York–Oxford, 1977 | MR | MR | Zbl | Zbl

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

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

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