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/

[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