Geodesic
On the Frankl--R\"odl theorem
Izvestiya. Mathematics , Tome 82 (2018) no. 6, pp. 1196-1224.

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

In this paper we considerably strengthen the currently known explicit exponential lower bound for the chromatic number of a Euclidean space with a forbidden regular simplex. We also strengthen the exponential lower bound for the chromatic numbers of distance graphs with large girth.
Keywords: Frankl–Rödl theorem, Euclidean Ramsey theory, distance graph, chromatic number, girth. 
@article{IM2_2018_82_6_a4,
     author = {A. Sagdeev},
     title = {On the {Frankl--R\"odl} theorem},
     journal = {Izvestiya. Mathematics },
     pages = {1196--1224},
     publisher = {mathdoc},
     volume = {82},
     number = {6},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2018_82_6_a4/}
}
TY  - JOUR
AU  - A. Sagdeev
TI  - On the Frankl--R\"odl theorem
JO  - Izvestiya. Mathematics 
PY  - 2018
SP  - 1196
EP  - 1224
VL  - 82
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2018_82_6_a4/
LA  - en
ID  - IM2_2018_82_6_a4
ER  - 
%0 Journal Article
%A A. Sagdeev
%T On the Frankl--R\"odl theorem
%J Izvestiya. Mathematics 
%D 2018
%P 1196-1224
%V 82
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2018_82_6_a4/
%G en
%F IM2_2018_82_6_a4
A. Sagdeev. On the Frankl--R\"odl theorem. Izvestiya. Mathematics , Tome 82 (2018) no. 6, pp. 1196-1224. http://geodesic.mathdoc.fr/item/IM2_2018_82_6_a4/

[1] A. Yu. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosv., ser. 3, 8, MTsNMO, M., 2004, 186–221

[2] A. D. N. J. de Grey, The chromatic number of the plane is at least $5$, 2018, arXiv: 1804.02385

[3] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “On the chromatic number of infinitesimal plane layer”, St. Petersburg Math. J., 29:5 (2018), 761–775 | DOI | MR | Zbl

[4] D. Cherkashin, A. Kulikov, A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete Appl. Math., 243 (2018), 125–131 | DOI | MR | Zbl

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

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

[7] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., John Wiley Sons, Inc., New York, 1990, xii+196 pp. | MR | Zbl

[8] I. Kříž, “Permutation groups in Euclidean Ramsey theory”, Proc. Amer. Math. Soc., 112:3 (1991), 899–907 | DOI | MR | Zbl

[9] K. Cantwell, “All regular polytopes are Ramsey”, J. Combin. Theory Ser. A, 114:3 (2007), 555–562 | DOI | MR | Zbl

[10] P. Frankl, V. Rödl, “All triangles are Ramsey”, Trans. Amer. Math. Soc., 297:2 (1986), 777–779 | DOI | MR | Zbl

[11] P. Frankl, V. Rödl, “Forbidden intersections”, Trans. Amer. Math. Soc., 300:1 (1987), 259–286 | DOI | MR | Zbl

[12] P. Frankl, V. Rödl, “A partition property of simplices in Euclidean space”, J. Amer. Math. Soc., 3:1 (1990), 1–7 | DOI | MR | Zbl

[13] A. M. Raigorodskii, A. A. Sagdeev, “On the chromatic number of a space with a forbidden regular simplex”, Dokl. Math., 95:1 (2017), 15–16 | DOI | DOI | MR | Zbl

[14] A. Sagdeev, “The chromatic number of space with forbidden regular simplex”, Math. Notes, 102:4 (2017), 541–546 | DOI | DOI | MR | Zbl

[15] R. I. Prosanov, “Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets”, Math. Notes, 103:2 (2018), 243–250 | DOI | DOI | MR | Zbl

[16] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wetensch. Proc. Ser. A, 54, = Indagationes Math., 13 (1951), 371–373 | 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 embedding”, Geombinatorics, 9:4 (2000), 180–193 | MR | Zbl

[19] A. B. Kupavskii, “Distance graphs with large chromatic number and arbitrary girth”, Mosc. J. Comb. Number Theory, 2:2 (2012), 52–62 | MR | Zbl

[20] A. A. Sagdeev, “Lower bounds for the chromatic numbers of distance graphs with large girth”, Math. Notes, 101:3 (2017), 515–528 | DOI | DOI | MR | Zbl

[21] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the maximal number of edges in a uniform hypergraph with one forbidden intersection”, Dokl. Math., 92:1 (2015), 401–403 | DOI | DOI | MR | Zbl

[22] A. V. Bobu, A. È. Kupriyanov, A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection”, Sb. Math., 207:5 (2016), 652–677 | DOI | DOI | MR | Zbl

[23] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges of a uniform hypergraph with a range of allowed intersections”, Problems Inform. Transmission, 53:4 (2017), 319–342 | DOI | MR

[24] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges in a uniform hypergraph with a range of allowed intersections”, Dokl. Math., 96:1 (2017), 354–357 | DOI | DOI | MR | Zbl

[25] P. K. Agarwal, J. Pach, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley Sons, Inc., New York, 1995, xiv+354 pp. | MR | Zbl

[26] P. Brass, W. O. J. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005, xii+499 pp. | DOI | MR | Zbl

[27] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer, New York, 2009, xxx+607 pp. | DOI | MR | Zbl

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

[29] A. M. Raigorodskii, “Around Borsuk's hypothesis”, J. Math. Sci. (N. Y.), 154:4 (2008), 604–623 | DOI | MR | Zbl

[30] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, Springer, New York, 2013, 429–460 | DOI | MR | Zbl

[31] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete geometry and algebraic combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | DOI | MR | Zbl

[32] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | DOI | MR | Zbl

[33] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle”, Sb. Math., 205:9 (2014), 1310–1333 | DOI | DOI | MR | Zbl

[34] K. Prachar, Primzahlverteilung, Grundlehren Math. Wiss., 91, Springer-Verlag, Berlin–Göttingen–Heidelberg, 1957, x+415 pp. | MR | MR | Zbl | Zbl

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

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

[37] E. I. Ponomarenko, A. M. Raigorodskii, “An improvement of the Frankl–Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges”, Dokl. Math., 89:1 (2014), 59–60 | DOI | DOI | MR | Zbl

[38] E. I. Ponomarenko, A. M. Raigorodskii, “New estimates in the problem of the number of edges in a hypergraph with forbidden intersections”, Problems Inform. Transmission, 49:4 (2013), 384–390 | DOI | MR | Zbl

[39] A. M. Raigorodskii, A. A. Sagdeev, “On a bound in extremal combinatorics”, Dokl. Math., 97:1 (2018), 47–48 | DOI | DOI | Zbl