On the Borsuk and Erd\"os--Hadwiger numbers

A. M. Raigorodskii

Matematičeskie zametki, Tome 79 (2006) no. 6, pp. 913-924.

Résumé

Two classical problems of combinatorial geometry, the Borsuk problem about splitting sets into parts of smaller diameter and the Erdös–Hadwiger problem about coloring Euclidean space, are studied. New asymptotic estimates are obtained for the quantities $f(d)$ (the minimal number of parts of smaller diameter into which any bounded set in $\mathbb R^d$ can be decomposed) and $\chi(\mathbb R^d)$ (the minimal number of colors required to color all points $\mathbb R^d$ so that any points at distance 1 from each other have different colors), which are the main objects of study in these problems.

Bibliographie

[1] Borsuk K., “Drei Sätze über die $n$-dimensionale Euklidische Sphäre”, Fundamenta Math., 20 (1993), 177–190

[2] Eggleston H. G., Convexity, Cambridge Univ. Press, Cambridge, 1958

[3] Hadwiger H., “Ein Überdeckungssatz für den Euklidischen Raum”, Portugaliae Math., 4 (1944), 140–144 | Zbl

[4] Rogers C. A., “Covering a sphere with spheres”, Mathematika, 10 (1963), 157–164 | MR | Zbl

[5] Schramm O., “Illuminating sets of constant width”, Mathematika, 35 (1988), 180–189 | MR | Zbl

[6] Bourgain J., Lindenstrauss J., “On covering a set in $\mathbb R^d$ by balls of the same diameter”, Lecture Notes in Math., 1469, Springer-Verlag, Berlin, 1991, 138–144

[7] Kahn J., Kalai G., “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc., 29:1 (1993), 60–62 | DOI | MR | Zbl

[8] Raigorodskii A. M., “Ob odnoi otsenke v probleme Borsuka”, UMN, 54:2 (1999), 185–186 | MR | Zbl

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

[10] Raiskii D. E., “Realizatsiya vsekh rasstoyanii pri razbienii prostranstva $\mathbb R^n$ na $n+1$ chast”, Matem. zametki, 7 (1970), 319–323 | MR

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

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

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

[14] Székely L. A., “Erdös on unit distances and the Szemerédi–Trotter theorems”, Paul Erdös and his Mathematics, Bolyai Math. Soc. Stud., 11, Springer, 2002, 649–666 | MR | Zbl

[15] Boltyanskii V. G., Gokhberg I. Ts., Teoremy i zadachi kombinatornoi geometrii, Nauka, M., 1965 | Zbl

[16] Boltyanski V. G., Martini H., Soltan P. S., Excursions into combinatorial geometry, Universitext, Springer-Verlag, Berlin–Heidelberg, 1997 | MR | Zbl

[17] Klee V., Wagon S., Old and New Unsolved Problems in Plane Geometry and Number Theory, Math. Association of America, 1991 | MR

[18] Raigorodskii A. M., “Problema Erdesha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Dokl. RAN, 392:3 (2003), 313–317 | MR

[19] Raigorodskii A. M., “Problema Erdesha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Matem. sb., 196:1 (2005), 123–156 | MR | Zbl

[20] Prakhar K., Raspredelenie prostykh chisel, Mir, M., 1967 | MR

[21] Kharari F., Teoriya grafov, Mir, M., 1973 | MR

[22] Alon N., Babai L., Suzuki H., “Multilinear polynomials and Frankl–Ray-Chaudhuri–Wilson type intersection theorems”, J. Comb. Theory. Ser. A, 58 (1991), 165–180 | DOI | MR | Zbl

[23] Babai L., Frankl P., Linear algebra methods in combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, September, 1992

[24] Raigorodskii A. M., “Zadachi Borsuka i Khadvigera i sistemy vektorov s zapretami na skalyarnye proizvedeniya”, UMN, 57:3 (2002), 159–160 | MR

[25] Raigorodskii A. M., The Borsuk Partition Problem, Lect. Note Ser. of the London Math. Soc., 2004 | Zbl