Upper Bounds for the Chromatic Numbers of Euclidean Spaces with Forbidden Ramsey Sets

R. I. Prosanov

Matematičeskie zametki, Tome 103 (2018) no. 2, pp. 248-257.

Résumé

The chromatic number of a Euclidean space $\mathbb R^n$ with a forbidden finite set $C$ of points is the least number of colors required to color the points of this space so that no monochromatic set is congruent to $C$. New upper bounds for this quantity are found.

Détail

Keywords: Euclidean Ramsey theory, chromatic number of space.

Bibliographie

[1] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (337) (2001), 107–146 | DOI | MR | Zbl

[2] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, 2009 | MR | Zbl

[3] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | 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 | MR | Zbl

[5] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (332) (2000), 147–148 | DOI | MR | Zbl

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

[7] P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. H. Spencer, E. G. Straus, “Euclidean Ramsey theorems”, J. Combin. Theory Ser. A, 14 (1973), 341–363 | DOI | MR | Zbl

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

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

[10] I. Kříž, “Permutation groups in Euclidean ramsey theory”, Proc. Amer. Math. Soc., 112:3 (1991), 899–907 | DOI | MR | Zbl

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

[12] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “Uluchshenie teoremy Frankla–Redlya o chisle reber gipergrafa s zapretami na peresecheniya”, Dokl. AN, 457:2 (2014), 144–146 | DOI | MR | Zbl

[13] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “O khromaticheskom chisle prostranstva s zapreschennym ravnostoronnim treugolnikom”, Matem. sb., 205:9 (2014), 97–120 | DOI | MR | Zbl

[14] A. E. Zvonarev, A. M. Raigorodskii, “Uluchsheniya teoremy Frankla–Redlya o chisle reber gipergrafa s zapreschennym peresecheniem i ikh sledstviya v zadache o khromaticheskom chisle prostranstva s zapreschennym ravnostoronnim treugolnikom”, Geometriya, topologiya i prilozheniya, Tr. MIAN, 288, MAIK, M., 2015, 109–119 | DOI | Zbl

[15] A. M. Raigorodskii, A. A. Sagdeev, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Dokl. AN, 472:2 (2017), 127–129 | MR | Zbl

[16] A. A. Sagdeev, “O nizhnikh otsenkakh khromaticheskikh chisel distantsionnykh grafov s bolshim obkhvatom”, Matem. zametki, 101:3 (2017), 430–445 | DOI | MR | Zbl

[17] A. A. Sagdeev, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Matem. zametki (to appear)

[18] A. A. Sagdeev, “On a Frank–Rödl theorem and its geometric corollaries”, Electron. Notes in Discrete Math. (to appear)

[19] H. Jung, “Über die kleinste Kugel, die eine räumliche Figur einschließt”, J. Reine Angew. Math, 123 (1901), 241–257 | MR | Zbl

[20] G. J. Butler, “Simultaneous packing and covering in Euclidean space”, Proc. London Math. Soc. (3), 25 (1972), 721–735 | DOI | MR | Zbl

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

[22] M. Naszodi, “On some covering problems in geometry”, Proc. Amer. Math. Soc., 144:8 (2016), 3555–3562 | DOI | MR | Zbl

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

[24] L. Lovász, “On the ratio of optimal integral and fractional covers”, Discrete Math., 13:4 (1975), 383–390 | DOI | MR | Zbl

[25] Z. Füredi, J.-H. Kang, “Covering the $n$-space by convex bodies and its chromatic number”, Discrete Math., 308:19 (2008), 4495–4500 | DOI | MR | Zbl

[26] A. B. Kupavskii, “O khromaticheskom chisle $\mathbb{R}^n$ s mnozhestvom zapreschennykh rasstoyanii”, Dokl. AN, 435:6 (2010), 740–743 | MR | Zbl

[27] R. Prosanov, A New Proof of the Larman–Rogers Upper Bound for the Chromatic Number of the Euclidean Space, 2016, arXiv: 1610.02846