Abstract
An explicit exponentially growing lower bound for the chromatic number of Euclidean space with forbidden regular simplex is constructed.
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,” in Mat. Pros., Ser. 3 (MTsNMO, Moscow, 2004), Vol. 8, pp. 186–221 [in Russian].
A. M. Raigorodskii, “On the chromatic number of a space,” Uspekhi Mat. Nauk 55 (2 (332)), 147–148 (2000) [Russian Math. Surveys 55 (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).
R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory (JohnWiley and Sons, New York, 1990).
P. Frankl and V. Rödl, “All triangles are Ramsey,” Trans. Amer. Math. Soc. 297 (2), 777–779 (1986).
P. Frankl and V. Rödl, “Forbidden intersections,” Trans. of Amer. Math. Soc. 300 (1), 259–286 (1987).
P. Frankl and V. Rödl, “A partition property of simplices in Euclidean space,” J. Amer. Math. Soc. 3 (1), 1–7 (1990).
A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, and A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle,” Mat. Sb. 205 (9), 97–120 (2014) [Sb. Math. 205 (9), 1310–1333 (2014)].
A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, and A. A. Kharlamova, “Improvement of the Frankl–Rödl theorem on the number of edges of a hypergraph with forbidden intersection,” Dokl. Akad. Nauk 457 (2), 144–146 (2014) [Dokl. Math. 90, 432–434 (2014)].
A. A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth,” Mat. Zametki 101 (3), 430–445 (2017) [Math. Notes 101 (3–4), 515–528 (2017)].
A. E. Zvonarev and A. M. Raigorodskii, “Improvements of the Frankl–Rödl theorem on the number of edges of a hypergraph with forbidden intersections, and their consequences in the problem of finding the chromatic number of a space with forbidden equilateral triangle,” in Trudy Mat. Inst. Steklov., Vol. 288: Geometry, Topology, and Applications (2015), pp. 109–119 [Proc. Steklov Inst. Math. 288 (1), 94–104 (2015)].
A. B. Kupavskii, “Distance graphs with large chromatic number and arbitrary girth,” Mosc. J. Comb. Number Theory 2 (2), 52–62 (2012).
A. M. Raigorodskii, “On distance graphs with large chromatic number but without large simplices,” Uspekhi Mat. Nauk 62 (6 (378)), 187–188 (2007) [RussianMath. Surveys 62 (6), 1224–1225 (2007)].
A. M. Raigorodskii and O. I. Rubanov, “Small clique and large chromatic number,” in European Conference on Combinatorics, Graph Theory and Applications, Electron. Notes DiscreteMath. (Elsevier Sci. B. V., Amsterdam, 2009), Vol. 34, pp. 441–445.
A. M. Raigorodskii and O. I. Rubanov, “On the clique and the chromatic numbers of high-dimensional distance graphs,” in Number Theory and Applications (Hindustan Book Agency, New Delhi, 2009), pp. 149–157.
A. M. Raigorodskii and O. I. Rubanov, “Distance Graphs with Large Chromatic Number and without Large Cliques,” Mat. Zametki 87 (3), 417–428 (2010) [Math. Notes 87 (3–4), 392–402 (2010)].
A. B. Kupavskii and A. M. Raigorodskii, “On distance graphs with large chromatic numbers and small clique numbers,” Dokl. Akad. Nauk 444 (5), 483–487 (2012) [Dokl. Math. 85 (3), 394–398 (2012)].
A. E. Zvonarev and A. M. Raigorodskii, “On distance graphs with large chromatic and small clique numbers,” Trudy Mosk. Fiz.-Tekh. Inst. 4 (1), 122–126 (2012).
A. B. Kupavskii and A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii,” Mat. Sb. 204 (10), 47–90 (2013) [Sb. Math. 204 (10), 1435–1479 (2013)].
E. E. Demekhin, A. M. Raigorodskii, and O. I. Rubanov, “Distance graphs having large chromatic numbers and not containing no cliques or cycles of a given size,” Mat. Sb. 204 (4), 49–78 (2013) [Sb. Math. 204 (4), 508–538 (2013)].
A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers,” Izv. Ross. Akad. Nauk Ser. Mat. 78 (1), 65–98 (2014) [Izv.: Math. 78 (1), 59–89 (2014)].
N. Alon and A. Kupavskii, “Two notions of unit distance graphs,” J. Combin. Theory Ser. A 125, 1–17 (2014).
D. D. Cherkashin and A. M. Raigorodskii, “On the chromatic number of low-dimensional spaces,” Dokl. Akad. Nauk 472 (1), 11–12 (2017) [Dokl. Math. 95 (1), 5–6 (2017)].
A. M. Raigorodskii and D. V. Samirov, “New bounds for the chromatic number of a space with forbidden isosceles triangles,” Dokl. Akad. Nauk 456 (3), 280–283 (2014) [Dokl. Math. 89 (3), 313–316 (2014)].
P. K. Agarwal and J. Pach, Combinatorial Geometry (JohnWiley and Sons, New York, 1995).
P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry (Springer, New York, 2005).
A. Soifer, The Mathematical Coloring Book (Springer, New York, 2009).
A. M. Raigorodskii, “Borsuk’s problem and the chromatic numbers of some metric spaces,” Uspekhi Mat. Nauk 56 (1 (337)), 107–146 (2001) [Russian Math. Surveys 56 (1), 103–139 (2001)].
A. M. Raigorodskii, “Around Borsuk’s hypothesis,” in Contemporary Mathematics. Fundamental Directions, Vol. 23: Geometry and Mechanics (2007), pp. 147–164 [J. Math. Sci. 154 (4), 604–623 (2008)].
A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters,” in Thirty Essays on Geometric Graph Theory (Springer, New York, 2013), pp. 429–460.
A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” in Discrete Geometry and Algebraic Combinatorics, Contemp. Math. (Amer. Math. Soc., Providence, RI, 2014), Vol. 625, pp. 93–109.
K. Prachar, Primzahlverteilung (Springer-Verlag, Berlin, 1957; Mir, Moscow, 1967).
R. C. Baker, G. Harman, and J. Pintz, “The difference between consecutive primes. II,” Proc. LondonMath. Soc. (3) 83 (3), 532–562 (2001).
P. Frankl and R. M. Wilson, “Intersection theorems with geometric consequences,” Combinatorica 1 (4), 357–368 (1981).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A. A. Sagdeev, 2017, published in Matematicheskie Zametki, 2017, Vol. 102, No. 4, pp. 579–585.
Rights and permissions
About this article
Cite this article
Sagdeev, A.A. The chromatic number of space with forbidden regular simplex. Math Notes 102, 541–546 (2017). https://doi.org/10.1134/S0001434617090267
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0001434617090267