The problems of Borsuk and Gr\"unbaum on lattice polytopes

A. M. Raigorodskii

Izvestiya. Mathematics , Tome 69 (2005) no. 3, pp. 513-537.

Résumé

We study two classical problems of combinatorial geometry, the Borsuk problem on partitioning sets into parts of smaller diameter and the Grünbaum problem on covering sets by balls. We obtain new non-trivial upper bounds for the minimum number of parts of smaller diameter into which an arbitrary lattice polytope can be partitioned, as well as for the minimum number of balls of the same diameter by which any such polytope can be covered.

Bibliographie

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

[2] Dantser L., Gryunbaum B., Kli V., Teorema Khelli, Mir, M., 1968

[3] Khadviger G., Debrunner G., Kombinatornaya geometriya ploskosti, Nauka, M., 1965 | MR

[4] Lenz H., “Über die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers”, Arch. Math., 4 (1956), 34–40 | DOI | MR

[5] Schopp J., “Die Abdeckung ebener Bereiche mit konstanten Durchmessern durch drei Kreise von kleinerem Durchmesser”, Vortrag, gehalten auf der Geometrie-Tegen in Tihany, Ungarn, 1965

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

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

[8] Hadwiger H., “Überdeckung einer Menge durch Mengen kleineren Durchmessers”, Comm. Math. Helv., 18 (1945/46), 73–75 ; “Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers”, Comm. Math. Helv., 19 (1946/47), 72–73 | DOI | MR | Zbl | DOI | MR | Zbl

[9] Kahn J., Kalai G., “A counterexample to Borsuk's conjecture”, Bulletin (new series) of the AMS, 29:1 (1993), 60–62 | DOI | MR | Zbl

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

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

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

[13] 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 | MR

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

[15] Danzer L., “On the $k$-th diameter in $E^d$ and a problem of Grünbaum”, Proc. Colloquium on Convexity, Copenhagen, 1965, 41

[16] Schiller F., Zur Berechnung und Abschätzung von Färbungszahlen und der $\vartheta$-Funktion von Graphen, Diplomarbeit, TU, Berlin, 1999

[17] Petersen J., Färbung von Borsuk–Graphen in niedriger Dimension, Diplomarbeit, TU, Berlin, 1998

[18] Payan C., “On the chromatic number of cube-like graphs”, Discrete Math., 103 (1992), 271–277 | DOI | MR | Zbl

[19] Ziegler G. M., “Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions”, Lect. Notes Comput. Sci., 2122, 2001, 159–171 | MR | Zbl

[20] Ziegler G. M., “Lectures on 0/1-polytopes”, Polytopes–Combinatorics and Computation, DMV-seminar, 29, eds. G. Kalai, G. M. Ziegler, Birkhäuser-Verlag, Basel, 2000, 1–44 | MR

[21] Raigorodskii A. M., “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, DAN, 371:5 (2000), 600–603 | MR

[22] Raigorodskii A. M., “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, DAN, 384:5 (2002), 593–597 | MR | Zbl

[23] Raigorodskii A. M., “Problema Borsuka dlya tselochislennykh mnogogrannikov”, Matem. sb., 193:10 (2002), 139–160 | MR | Zbl

[24] Raigorodskii A. M., “Problemy Borsuka, Gryunbauma i Khadvigera dlya nekotorykh klassov mnogogrannikov i grafov”, DAN, 388:6 (2003), 738–742 | MR | Zbl

[25] Raigorodskii A. M., The Borsuk partition problem, Lect. Note Ser. of the London Math. Soc., 2005 | Zbl

[26] Raigorodskii A. M., “Ob odnoi zadache optimalnogo pokrytiya mnozhestv sharami”, Chebyshevskii sbornik, 3:2(4) (2002), 100–106 | MR | Zbl

[27] Linial N., Meshulam R., Tarsi M., “Matroidal bijections between graphs”, J. Combin. Theory. Ser. B, 45:1 (1988), 31–44 | DOI | MR | Zbl

[28] Raigorodskii A. M., “Sistemy obschikh predstavitelei”, Fund. i prikl. matematika, 5:3 (1999), 851–860 | MR | Zbl

[29] Kuzyurin N. N., “Asimptoticheskoe issledovanie zadachi o pokrytii”, Problemy kibernetiki, 1980, no. 37, 19–56 | MR | Zbl

[30] Turán P., “Egy grafelmeletiszelsoertek feladatrol”, Mat. Fiz. Lapok, 48 (1941), 436–452 | MR | Zbl

[31] Katona G., Nemetz T., Simonovitz M., “On a graph problem of Turan”, Mat. Lapok (in Hungarian), 15 (1964), 228–238 | MR

[32] Füredi Z., “Turán's type problems”, Surveys in Combinatorics, Proc. of the 13th British Combin. Conference, ed. A. D. Keedwell, Cambridge Univ. Press, Cambridge, 1991, 253–300 | MR

[33] Raigorodskii A. M., “Defekt dopustimykh sharov i oktaedrov v reshetke i sistemy obschikh predstavitelei”, Matem. sb., 189:6 (1998), 117–141 | MR | Zbl

[34] Kassels Dzh., Vvedenie v geometriyu chisel, Mir, M., 1965 | MR

[35] Gruber P. M., Lekkerkerker C. G., Geometry of numbers, North-Holland, Amsterdam, 1987 | MR | Zbl

[36] Konvei Dzh., Sloen N., Upakovki sharov, reshetki i gruppy, Mir, M., 1990

[37] Rodzhers K., Ukladki i pokrytiya, Mir, M., 1968 | MR