On the chromatic numbers corresponding to exponentially Ramsey sets

A. A. Sagdeev

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part X, Tome 475 (2018), pp. 174-189

Résumé

In this paper, nontrivial upper bounds on the chromatic numbers of the spaces $\mathbb{R}^n_p=(\mathbb{R}^n, l_p)$ with forbidden monochromatic sets are proved. In the case of forbidden rectangular parallelepiped or a regular simplex, explicit exponential lower bounds on the chromatic numbers are obtained. Exact values of the chromatic numbers of the spaces $\mathbb{R}^n_p$ with forbidden regular simplex in case $p = \infty$ are found.

Bibliographie

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

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

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

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

[5] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s metrikoi $l_q$”, Uspekhi mat. nauk, 59:5 (2004), 161–162 | DOI

[6] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, Uspekhi mat. nauk, 55:2 (2000), 147–148 | DOI

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

[8] L. A. Székely, “Erdős on Unit Distances and the Szemerédi-Trotter Theorems”, Paul Erdős and His Mathematics, II (Budapest, Hungary, July 4–11, 1999), Bolyai Soc. Math. Stud., 11, eds. G. Halász, L. Lovász, M. Simonovits, V. T. Sós, Springer, Berlin; János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[9] P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, E. G. Straus, “Euclidean ramsey theorems. I”, J. Comb. Theor., Series A, 14:3 (1973), 341–363 | DOI | MR | Zbl

[10] P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, E. G. Straus, “Euclidean ramsey theorems II”, Infinite and Finite Sets I, eds. A. Hajnal, R. Rado, V. Sós, North Holland, Amsterdam, 1975, 529–557 | MR

[11] P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, E. G. Straus, “Euclidean ramsey theorems III”, Infinite and Finite Sets II, eds. A. Hajnal, R. Rado, V. Sós, North Holland, Amsterdam, 1975, 559–583 | MR

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

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

[14] I. Kříž, “Permutation groups in euclidean ramsey theory”, Proceedings of the American Math. Soc., 112:3 (1991), 899–907 | DOI | MR | Zbl

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

[16] I. Kříž, “All trapezoids are Ramsey”, Discr. Math., 108 (1992), 59–62 | DOI | MR | Zbl

[17] A. A. Sagdeev, “O teoreme Frankla-Redla”, Izv. RAN, Ser. matem., 82:6 (2018), 125–154 | DOI

[18] A. A. Sagdeev, “Uluchshennaya teorema Frankla-Redlya i nekotorye ee geometricheskie sledstviya”, Problemy peredachi informatsii, 54:2 (2018), 45–72

[19] A. A. Sagdeev, “Eksponentsialno ramseevskie mnozhestva”, Problemy peredachi informatsii (to appear)

[20] R. I. Prosanov, A. M. Raigorodskii, A. A. Sagdeev, “Uluchsheniya teoremy Frankla-Redlya i geometricheskie sledstviya”, Doklady RAN, 475:2 (2017), 137–139 | DOI | Zbl

[21] R. I. Prosanov, “Verkhnie otsenki khromaticheskikh chisel evklidovykh prostranstv s zapreschennymi ramseevskimi mnozhestvami”, Matem. zametki, 103:2 (2018), 248–257 | DOI | Zbl

[22] N. Alon, A. Kupavskii, “Two notions of unit distance graphs”, J. Comb. Theory, Ser. A, 125 (2014), 1–17 | DOI | MR | Zbl

[23] A. M. Raigorodskii, D. V. Samirov, “Novye otsenki v zadache o khromaticheskom chisle prostranstva s zapreschennymi ravnobedrennymi treugolnikami”, Doklady RAN, 456:3 (2014), 280–283 | DOI | Zbl

[24] A. M. Raigorodskii, D. D. Cherkashin, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Doklady RAN, 472:1 (2017), 11–12 | Zbl

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

[26] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O maksimalnom chisle reber odnorodnogo gipergrafa s odnim zapreschennym peresecheniem”, Doklady RAN, 463:1 (2015), 11–13 | DOI | Zbl

[27] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asimptoticheskoe issledovanie zadachi o maksimalnom chisle reber odnorodnogo gipergrafa s odnim zapreschennym peresecheniem”, Matem. sbornik, 207:5 (2016), 17–42 | DOI | Zbl

[28] A. M. Raigorodskii, A. A. Sagdeev, “Ob odnoi otsenke v ekstremalnoi kombinatorike”, Doklady RAN, 478:3 (2018), 271–273 | DOI | Zbl

[29] A. Soifer, The Mathematical Coloring Book, Springer, 2009 | MR | Zbl

[30] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, ed. J. Pach, Springer, 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, Contemporary Mathematics, 625, AMS, 2014, 93–109 | DOI | MR | Zbl

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

[33] N. D. Elkies, A. M. Odlyzko, J. A. Rush, “On the packing densities of superballs and other bodies”, Invent. Math., 105 (1991), 613–639 | DOI | MR | Zbl

[34] P. Erdős, C. A. Rogers, “Covering space with convex bodies”, Acta Arithmetica, 7 (1962), 281–285 | DOI | MR | Zbl