In this paper, nontrivial upper bounds on the chromatic numbers of the spaces \( {\mathrm{\mathbb{R}}}_p^n=\left({\mathrm{\mathbb{R}}}^n, lp\right) \) with forbidden monochromatic sets are proved. In the case of a 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 \( {\mathrm{\mathbb{R}}}_p^n \) with a forbidden regular simplex in the case p = ∞ are found. Bibliography: 39 titles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Soifer, “The chromatic number of the plane: its past, present, and future,” Mat. Prosveshchenie, Ser. 3, No. 8, 186–221 (2004).
A.D.N.J. de Grey, “The chromatic number of the plane is at least 5,” https://arxiv.org/abs/1804.02385.
P. Frankl and R. M. Wilson, “Intersection theorems with geometric consequences,” Combinatorica, 1, No. 4, 357–368 (1981).
A. Kupavskiy, “On the chromatic number of ℝn with an arbitrary norm,” Discrete Math., 311, 437–440 (2011).
A. M. Raigorodskii, “On the chromatic number of a space with the metric lq,” Russian Math. Surveys, 59, No. 5, 973–975 (2004).
A. M. Raigorodskii, “On the chromatic number of a space,” Russian Math. Surveys, 55, No. 2, 351–352 (2000).
D. G. Larman and C. A. Rogers, “The realization of distances within sets in Euclidean space,” Mathematika, 19, 1–24 (1972).
L. A. Székely, “Erdős on unit distances and the Szemerédi-Trotter theorems,” in: Paul Erdős and His Mathematics. II, Proceedings of the Conference Held in Budapest, Hungary, July 4–11 (1999), János Bolyai Math. Soc., Budapest (2002), pp. 649–666.
P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus, “Euclidean Ramsey theorems. I,” J. Combin. Theory, Series A, 14, No. 3, 341–363 (1973).
P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus, “Euclidean Ramsey theorems. II,” in: Infinite and Finite Sets. I, Amsterdam, North Holland (1975), pp. 529–557.
P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus, “Euclidean Ramsey theorems. III,” in: Infinite and Finite Sets. II, Amsterdam, North Holland (1975), pp. 559–583.
R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, 2nd ed., John Wiley & Sons, New York (1990).
P. Frankl and V. Rödl, “A partition property of simplices in Euclidean space,” J. Amer. Math. Soc., 3, No. 1, 1–7 (1990).
I. Kříž, “Permutation groups in Euclidean Ramsey theory,” Proc. Amer. Math. Soc., 112, No. 3, 899–907 (1991).
K. Cantwell, “All regular polytopes are Ramsey,” J. Combin. Theory, Ser. A, 114, 555– 562 (2007).
I. Kříž, “All trapezoids are Ramsey,” Discrete Math., 108, 59–62 (1992).
A. Sagdeev, “On the Frankl-Rödl theorem,” Izvestiya: Mathematics, 82, No. 6, 1196–1224 (2018).
A. Sagdeev, “Improved Frankl-Rödl theorem and some of its geometric consequences,” Problems Inform. Transmission, 54, No. 2, 139–164 (2018).
A. Sagdeev, “Exponentially Ramsey sets,” Problems Inform. Transmission, 54, No. 4, 372–396 (2018).
R. I. Prosanov, A. M. Raigorodskii, and A. A. Sagdeev, “Improvements of the Frankl–Rödl theorem and geometric consequences,” Dokl. Math., 96, No. 1, 336–338 (2017).
R. I. Prosanov, “Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets,” Math. Notes, 103, No. 1–2, 243–250 (2018).
N. Alon and A. Kupavskii, “Two notions of unit distance graphs,” J. Comb. Theory, Ser. A, 125, 1–17 (2014).
A. M. Raigorodskii and D. V. Samirov, “New bounds for the chromatic number of a space with forbidden isosceles triangles,” Dokl. Math., 89, No. 3, 313–316 (2014).
D. D. Cherkashin and A. M. Raigorodskii, “On the chromatic numbers of low-dimensional spaces,” Dokl. Math., 95, No. 1, 5–6 (2017).
D. Cherkashin, A. Kulikov, and A. Raigorodskii, “On the chromatic numbers of smalldimensional Euclidean spaces,” Discrete Appl. Math., 243, 125–131 (2018).
L. I. Bogolyubsky and A. M. Raigorodskii, “A remark on lower bounds for the chromatic numbers of spaces of small dimension with metrics ℓ1 and ℓ2,” Math. Notes, 105, No. 1–2, 180–203 (2019).
F. A. Pushnyakov, “The number of edges in induced subgraphs of some distance graphs,” Math. Notes, 105, No. 3–4, 582–591 (2019).
L. E. Shabanov, “Turán-type results for distance graphs in an infinitesimal plane layer,” J. Math. Sci.236, No. 5, 554–578 (2019).
R. I. Prosanov, “Counterexamples to Borsuk’s conjecture with large girth,” Math. Notes, 105, Nos. 5–6, 874–880 (2019).
A. A. Sagdeev and A. M. Raigorodskii, “On a Frankl-Wilson theorem and its geometric corollaries,” Acta Math. Univ. Comenianae, 88, No. 3, 1029–1033 (2019).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “On the maximum number of edges of a uniform hypergraph with one forbidden intersection,” Dokl. Math., 92, No. 1, 401–403 (2015).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection,” Sb. Math., 207, No. 5, 652–677 (2016).
A. M. Raigorodskii and A. A. Sagdeev, “On a bound in extremal combinatorics,” Dokl. Math., 97, No. 1, 47–48 (2018).
A. Soifer, The Mathematical Coloring Book, Springer (2009).
A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters,” in: Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer (2013), pp. 429–460.
A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” Contemporary Math., 625, 93–109 (2014).
A. M. Raigorodskii, “Combinatorial geometry and coding theory,” Fundamenta Informatica, 145, 359–369 (2016).
N. D. Elkies, A. M. Odlyzko, and J. A. Rush, “On the packing densities of superballs and other bodies,” Invent. Math., 105, 613–639 (1991).
P. Erdős and C. A. Rogers, “Covering space with convex bodies,” Acta Arithmetica, 7, 281–285 (1962).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 475, 2018, pp. 174–189.
Rights and permissions
About this article
Cite this article
Sagdeev, A.A. On the Chromatic Numbers Corresponding to Exponentially Ramsey Sets. J Math Sci 247, 488–497 (2020). https://doi.org/10.1007/s10958-020-04815-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-020-04815-z