Geodesic
Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
Sbornik. Mathematics, Tome 204 (2013) no. 4, pp. 508-538 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

It is established that there exist sequences of distance graphs $G_n\subset\mathbb R^n$, with chromatic numbers which grow exponentially, but, at the same time, without cliques or cycles of a given size. Bibliography: 42 titles.
Keywords: distance graph, random graph, chromatic number, cycle.
Mots-clés : clique 
@article{SM_2013_204_4_a2,
     author = {E. E. Demekhin and A. M. Raigorodskii and O. I. Rubanov},
     title = {Distance graphs having large chromatic numbers and containing no cliques or cycles of a~given size},
     journal = {Sbornik. Mathematics},
     pages = {508--538},
     year = {2013},
     volume = {204},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2013_204_4_a2/}
}
TY  - JOUR
AU  - E. E. Demekhin
AU  - A. M. Raigorodskii
AU  - O. I. Rubanov
TI  - Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
JO  - Sbornik. Mathematics
PY  - 2013
SP  - 508
EP  - 538
VL  - 204
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2013_204_4_a2/
LA  - en
ID  - SM_2013_204_4_a2
ER  - 
%0 Journal Article
%A E. E. Demekhin
%A A. M. Raigorodskii
%A O. I. Rubanov
%T Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size
%J Sbornik. Mathematics
%D 2013
%P 508-538
%V 204
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2013_204_4_a2/
%G en
%F SM_2013_204_4_a2
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. Sbornik. Mathematics, Tome 204 (2013) no. 4, pp. 508-538. http://geodesic.mathdoc.fr/item/SM_2013_204_4_a2/

[1] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wet., Proc., Ser. A, 54:5 (1951), 371–373 | Zbl

[2] L. Moser, W. Moser, “Solution to problem 10”, Canad. Math. Bull., 4 (1961), 187–189

[3] H. Hadwiger, “Ungelöste Probleme No. 40”, Elem. Math., 16 (1961), 103–104 | MR | Zbl

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

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

[6] D. Coulson, “A 15-colouring of 3-space omitting distance one”, Discrete Math., 256:1–2 (2002), 83–90 | DOI | MR | Zbl

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

[8] L. L. Ivanov, “An estimate for the chromatic number of the space $\mathbb R^4$”, Russian Math. Surveys, 61:5 (2006), 984–986 | DOI | DOI | MR | Zbl

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

[10] A. M. Raigorodskii, “On the chromatic number of a space”, Russian Math. Surveys, 55:2 (2000), 351–352 | DOI | DOI | MR | Zbl

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

[12] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

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

[14] P. Erdős, “Unsolved problems”, Congressus numerantium, v. 15, Utilitas Math., Winnipeg, 1976, 678–696 | MR

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

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

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

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

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

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

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

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

[23] J. Pach, P. K. Agarwal, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience Publ., New York, 1995 | MR | Zbl

[24] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Dolciani Math. Exp., 11, Math. Association of America, Washington, 1991 | MR | Zbl

[25] A. Soifer, The mathematical coloring book, Springer-Verlag, New York, 2009 | MR | Zbl

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

[27] O. I. Rubanov, “Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra”, Math. Notes, 82:5 (2007), 718–721 | DOI | DOI | MR | Zbl

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

[29] L. Babai, P. Frankl, Linear algebra methods in combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, 1992

[30] A. M. Raigorodskii, “The problems of Borsuk and Grunbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513–537 | DOI | DOI | MR | Zbl

[31] A. E. Guterman, V. K. Lyubimov, A. M. Raigorodskii, S. A. Usachev, “O chislakh nezavisimosti grafov rasstoyanii s vershinami v $\{-1,0,1\}^n $: otsenki, gipotezy i prilozheniya k zadacham Nelsona–Erdesha–Khadvigera i Borsuka”, Itogi nauki i tekhniki, ser. “Sovremennaya matematika”, 65 (2009), 82–100

[32] A. M. Raigorodskii, I. M. Shitova, “Chromatic numbers of real and rational spaces with real or rational forbidden distances”, Sb. Math., 199:4 (2008), 579–612 | DOI | DOI | MR | Zbl

[33] E. S. Gorskaya, I. M. Mitricheva, V. Yu. Protasov, A. M. Raigorodskii, “Estimating the chromatic numbers of Euclidean space by convex minimization methods”, Sb. Math., 200:6 (2009), 783–801 | DOI | DOI | MR | Zbl

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

[35] M. Hall, Combinatorial theory, Blaisdell Publ., Waltham, MA–Toronto–London, 1967 | MR | MR | Zbl | Zbl

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

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

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

[39] A. M. Raigorodskii, O. I. Rubanov, “On the clique and the chromatic numbers of high-dimensional distance graphs”, Number theory and applications, Hindustan Book Agency, New Delhi, 2009, 149–155 | MR | Zbl

[40] A. M. Raigorodskii, O. I. Rubanov, “Distance graphs with large chromatic number and without large cliques”, Math. Notes, 87:3 (2010), 392–402 | DOI | DOI | MR | Zbl

[41] B. W. Gnedenko, Lehrbuch der Wahrscheinlichkeitsrechnung, Math. Lehrbucher und Monogr., 9, Akademie-Verlag, Berlin, 1957 | MR | MR | Zbl | Zbl

[42] A. M. Raigorodskii, M. I. Absalyamova, “O nizhnei otsenke khromaticheskogo chisla prostranstva $\mathbb R^n$ s $k$ zapreschennymi rasstoyaniyami i metrikoi $l_1$”, Chebyshevskii sb., 2006, no. 4, 105–112 | MR | Zbl