Abstract
We study chromatic numbers of spaces \(\mathbb{R}_p^n=(\mathbb{R}^n, \ell_p)\) with forbidden monochromatic sets. For some sets, we for the first time obtain explicit exponentially growing lower bounds for the corresponding chromatic numbers; for some others, we substantially improve previously known bounds.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Soifer, A., The Chromatic Number of the Plane: Its Past, Present, and Future, Mat. Prosveshchenie, Ser. 3, Moscow: MCCME, 2004, no. 8, pp. 186–221.
de Grey, A.D.N.J., The Chromatic Number of the Plane Is at Least 5, arXiv:1804.02385v2 [math.CO], 2018.
Frankl, P. and Wilson, R.M., Intersection Theorems with Geometric Consequences, Combinatorica, 1981, vol. 1, no. 4, pp. 357–368.
Kupavskiy, A., On the Chromatic Number of Rn with an Arbitrary Norm, Discrete Math., 2011, vol. 311, no. 6, pp. 437–440.
Raigorodskii, A.M., On the Chromatic Number of a Space, Uspekhi Mat. Nauk, 2000, vol. 55, no. 2, pp. 147–148 [Russian Math. Surveys (Engl. Transl.), 2000, vol. 55, no. 2, pp. 351–352].
Larman, D.G. and Rogers, C.A., The Realization of Distances within Sets in Euclidean Space, Mathematika, 1972, vol. 19, no. 1, pp. 1–24.
Raigorodskii, A.M., On the Chromatic Number of a Space with the Metric q, Uspekhi Mat. Nauk, 2004, vol. 59, no. 5 (359), pp. 161–162 [Russian Math. Surveys (Engl. Transl.), 2004, vol. 59, no. 5, pp. 973–975].
Székely, L.A., Erdős on Unit Distances and the Szemerédi–Trotter Theorems, Paul Erdős and His Mathematics, II (Proc. Conf. Held in Budapest, Hungary, July 4–11, 1999), Halász, G., Lovász, L., Simonovits, M., and Sós, V.T., Eds., Bolyai Soc. Math. Stud, vol. 11, Berlin: Springer; Budapest: János Bolyai Math. Soc., 2002, pp. 649–666.
Graham, R.L., Rothschild, B.L., and Spencer, J.H., Ramsey Theory, New York: Wiley, 1990, 2nd ed.
Erdős, P., Graham, R.L., Montgomery, P., Rothschild, B.L., Spencer, J., and Straus, E.G., Euclidean Ramsey Theorems, I, J. Combin. Theory Ser. A, 1973, vol. 14, pp. 341–363.
Erdős, P., Graham, R.L., Montgomery, P., Rothschild, B.L., Spencer, J., and Straus, E.G., Euclidean Ramsey Theorems, II, III, Infinite and Finite Sets (Colloq. dedicated to P. Erdős on his 60th birthday, Keszthely, Hungary, June 25–July 1, 1973), vol. 1, Hajnal, A., Rado, R., and Sós, V.T., Eds., Colloq. Math. Soc. János Bolyai, vol. 10, Amsterdam: North-Holland, 1975, pp. 529–557, 559–583.
Frankl, P. and Rödl, V., All Triangles Are Ramsey, Trans. Amer. Math. Soc., 1986, vol. 297, no. 2, pp. 777–779.
Frankl, P. and Rödl, V., A Partition Property of Simplices in Euclidean Space, J. Amer. Math. Soc., 1990, vol. 3, no. 1, pp. 1–7.
Frankl, P. and Rödl, V., Strong Ramsey Properties of Simplices, Israel J. Math., 2004, vol. 139, no. 1, pp. 215–236.
Kříž, I., Permutation Groups in Euclidean Ramsey Theory, Proc. Amer. Math. Soc., 1991, vol. 112, no. 3, pp. 899–907.
Kříž, I., All Trapezoids Are Ramsey, Discrete Math., 1992, vol. 108, no. 1–3, pp. 59–62.
Cantwell, K., Edge-Ramsey Theory, Discrete Comput. Geom., 1996, vol. 15, no. 3, pp. 341–352.
Cantwell, K., All Regular Polytopes Are Ramsey, J. Combin. Theory Ser. A, 2007, vol. 114, no. 3, pp. 555–562.
Frankl, P. and Rödl, V., Forbidden Intersections, Trans. Amer. Math. Soc., 1987, vol. 300, no. 1, pp. 259–286.
Zvonarev, A.E., Raigorodskii, A.M., Samirov, D.V., and Kharlamova, A.A., On the Chromatic Number of a Space with Forbidden Equilateral Triangle, Mat. Sb., 2014, vol. 205, no. 9, pp. 97–120 [Sb. Math. (Engl. Transl.), 2014, vol. 205, no. 9–10, pp. 1310–1333].
Zvonarev, A.E., Raigorodskii, A.M., 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, Tr. Mat. Inst. Steklova, 2015, vol. 288, pp. 109–119 [Proc. Steklov Inst. Math. (Engl. Transl.), 2015, vol. 288, no. 1, pp. 94–104].
Raigorodskii, A.M. and Sagdeev, A.A., On the Chromatic Number of a Space with a Forbidden Regular Simplex, Dokl. Akad. Nauk, 2017, vol. 472, no. 2, pp. 127–129 [Dokl. Math. (Engl. Transl.), 2017, vol. 95, no. 1, pp. 15–16].
Prosanov, R.I., Raigorodskii, A.M., and Sagdeev, A.A., Improvements of the Frankl–Rödl Theorem and Geometric Consequences, Dokl. Akad. Nauk, 2017, vol. 475, no. 2, pp. 137–139 [Dokl. Math. (Engl. Transl.), 2017, vol. 96, no. 1, pp. 336–338].
Sagdeev, A.A., On the Frankl–Rödl Theorem, Izv. Ross. Akad. Nauk, Ser. Mat., 2018, vol. 82, no. 6, pp. 128–157.
Sagdeev, A.A., Improved Frankl–Rödl Theorem and Some of Its Geometric Consequences, Probl. Peredachi Inf., 2018, vol. 54, no. 2, pp. 45–72 [Probl. Inf. Trans. (Engl. Transl.), 2018, vol. 54, no. 2, pp. 139–164].
Raigorodskii, A.M., The Borsuk Problem and the Chromatic Numbers of Some Metric Spaces, Uspekhi Mat. Nauk, 2001, vol. 56, no. 1 (337), pp. 107–146 [Russian Math. Surveys (Engl. Transl.), 2001, vol. 56, no. 1, pp. 103–139].
Raigorodskii, A.M., Around the Borsuk Conjecture, Sovrem. Mat. Fundam. Napravl., 2007, vol. 23, pp. 147–164 [J. Math. Sci. (N.Y.) (Engl. Transl.), 2007, vol. 154, no. 4, pp. 604–623].
Raigorodskii, A.M., Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, Pach, J., Ed., New York: Springer, 2013, pp. 429–460.
Raigorodskii, A.M., Cliques and Cycles in Distance Graphs and Graphs of Diameters, Discrete Geometry and Algebraic Combinatorics, Barg, A. and Musin, O.R., Eds., Providence, RI: Amer. Math. Soc., 2014, pp. 93–109.
Raigorodskii, A.M., Combinatorial Geometry and Coding Theory, Fund. Inform., 2016, vol. 145, no. 3, pp. 359–369.
Cherkashin, D., Kulikov, A., and Raigorodskii, A., On the Chromatic Numbers of Small-Dimensional Euclidean Spaces, Discrete Appl. Math., 2018, vol. 243, pp. 125–131.
Prosanov, R.I., Upper Bounds for the Chromatic Numbers of Euclidean Spaces with Forbidden Ramsey Sets, Mat. Zametki, 2018, vol. 103, no. 2, pp. 248–257 [Math. Notes (Engl. Transl.), 2018, vol. 103, no. 1–2, pp. 243–250].
Prachar, K., Primzahlverteilung (Distribution of Prime Numbers), Berlin, Springer, 1957. Translated under the title Raspredelenie prostykh chisel, Moscow: Mir, 1967.
Baker, R.C., Harman, G., and Pintz, J., The Difference between Consecutive Primes, II, Proc. London Math. Soc., 2001, vol. 83, no. 3, pp. 532–562.
Raigorodskii, A.M., Lineino-algebraicheskii metod v kombinatorike (The Linear Algebra Method in Combinatorics), Moscow: MCCME, 2015, 2nd ed.
Ponomarenko, E.I. and Raigorodskii, A.M., New Estimates in the Problem of the Number of Edges in a Hypergraph with Forbidden Intersections, Probl. Peredachi Inf., 2013, vol. 49, no. 4, pp. 98–104 [Probl. Inf. Trans. (Engl. Transl.), 2013, vol. 49, no. 4, pp. 384–390].
Raigorodskii, A.M. and Sagdeev, A.A., On a Bound in Extremal Combinatorics, Dokl. Akad. Nauk, 2018, vol. 478, no. 3, pp. 271–273 [Dokl. Math. (Engl. Transl.), 2018, vol. 97, no. 1, pp. 47–48].
Bobu, A.V., Kupriyanov, A.E., and Raigorodskii, A.M., On the Maximum Number of Edges of a Uniform Hypergraph with One Forbidden Intersection, Dokl. Akad. Nauk, 2015, vol. 463, no. 1, pp. 11–13 [Dokl. Math. (Engl. Transl.), 2015, vol. 92, no. 1, pp. 401–403].
Bobu, A.V., Kupriyanov, A.E., and Raigorodskii, A.M., Asymptotic Study of the Maximum Number of Edges in a Uniform Hypergraph with One Forbidden Intersection, Mat. Sb., 2016, vol. 207, no. 5, pp. 17–42 [Sb. Math. (Engl. Transl.), 2016, vol. 207, no. 5, pp. 652–677].
Bobu, A.V., Kupriyanov, A.E., and Raigorodskii, A.M., On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections, Probl. Peredachi Inf., 2017, vol. 53, no. 4, pp. 16–42 [Probl. Inf. Trans. (Engl. Transl.), 2017, vol. 53, no. 4, pp. 319–342].
Bobu, A.V., Kupriyanov, A.E., and Raigorodskii, A.M., On the Number of Edges in a Uniform Hypergraph with a Range of Permitted Intersections, Dokl. Akad. Nauk, 2017, vol. 475, no. 4, pp. 365–368 [Dokl. Math. (Engl. Transl.), 2017, vol. 96, no. 1, pp. 354–357].
Hall, M., Jr., Combinatorial Theory, Waltham: Blaisdell, 1967. Translated under the title Kombinatorika, Moscow: Mir, 1970.
Paley, R.E.A.C., On Orthogonal Matrices, J. Math. Phys. Mass. Inst. Techn., 1933, vol. 12, pp. 311–320.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.A. Sagdeev, 2018, published in Problemy Peredachi Informatsii, 2018, Vol. 54, No. 4, pp. 82–109.
Supported in part by the Russian Foundation for Basic Research, project no. 18-01-00355, and the President of the Russian Federation Council for State Support of Leading Scientific Schools, grant no. NSh-6760.2018.1.
Rights and permissions
About this article
Cite this article
Sagdeev, A.A. Exponentially Ramsey Sets. Probl Inf Transm 54, 372–396 (2018). https://doi.org/10.1134/S0032946018040051
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0032946018040051