On the chromatic number of a space with forbidden equilateral triangle

A. E. Zvonarev   ; A. M. Raigorodskii   ; D. V. Samirov   ; A. A. Kharlamova

Sbornik. Mathematics, Tome 205 (2014) no. 9, pp. 1310-1333

Résumé

We improve the Frankl-Rödl estimate for the product of the numbers of edges in uniform hypergraphs with forbidden cardinalities of the intersection of edges. By using this estimate, we obtain explicit bounds for the chromatic number of a space with forbidden monochromatic equilateral triangles. Bibliography: 31 titles.

Détail

Keywords: hypergraph, systems of sets with forbidden intersections, Euclidean Ramsey theory, chromatic number of a space.

Bibliographie

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

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

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

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

[5] A. M. Raigorodskii, “On the chromatic numbers of spheres in Euclidean spaces”, Dokl. Math., 81:3 (2010), 379–382 | DOI | MR | Zbl

[6] A. M. Raigorodskii, “On the chromatic numbers of spheres in ${\mathbb R}^n$”, Combinbatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[7] A. B. Kupavskii, “On the chromatic number of ${\mathbb R}^n$ with a set of forbidden distances”, Dokl. Math., 82:3 (2010), 963–966 | DOI | MR | Zbl

[8] A. B. Kupavskiy, “On the chromatic number of ${\mathbb R}^n$ with an arbitrary norm”, Discrete Math., 311:6 (2011), 437–440 | DOI | MR | Zbl

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

[10] A. M. Raigorodskii, “The chromatic number of a space with the metric $l_q$”, Russian Math. Surveys, 59:5 (2004), 973–975 | DOI | DOI | MR | Zbl

[11] E. S. Gorskaya, I. M. Mitricheva (Shitova), 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

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

[13] N. G. Moshchevitin, A. M. Raigorodskii, “Colorings of the space $\mathbb R^n$ with several forbidden distances”, Math. Notes, 81:5 (2007), 656–664 | DOI | DOI | MR | Zbl

[14] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s dvumya zapreschennymi rasstoyaniyami”, Dokl. RAN, 408:5 (2006), 601–604 | MR

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

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

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

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

[19] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, Parts I, II, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam–New York–Oxford, 1977 | MR | MR | Zbl | Zbl

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

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

[22] D. E. Raiskii, “Realization of all distances in a decomposition of the space $R^n$ into $n+1$ parts”, Math. Notes, 7:3 (1970), 194–196 | DOI | MR | Zbl

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

[24] A. M. Raigorodskii, D. V. Samirov, “Chromatic numbers of spaces with forbidden monochromatic triangles”, Math. Notes, 93:1 (2013), 163–171 | DOI | DOI | MR | Zbl

[25] A. M. Raigorodskii, D. V. Samirov, “Novye nizhnie otsenki khromaticheskogo chisla prostranstva s zapreschennymi ravnobedrennymi treugolnikami”, Itogi nauki i tekhniki. Sovremennaya matematika i ee prilozheniya, 125 (2013), 252–268

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

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

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

[29] E. I. Ponomarenko, A. M. Raigorodskii, “Uluchshenie teoremy Frankla–Uilsona o chisle reber gipergrafa s zapretami na peresecheniya”, Dokl. RAN, 454:3 (2014), 268–269 | DOI | MR

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

[31] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007, 138 pp. | Zbl