The Borsuk problem for integral polytopes

A. M. Raigorodskii

Sbornik. Mathematics, Tome 193 (2002) no. 10, pp. 1535-1556

Résumé

Let $f(d)$ be the minimum number of parts of smaller diameter into which one can partition an arbitrary bounded subset of $d$-dimensional Euclidean space $\mathbb R^d$. In 1933, Borsuk conjectured that $f(d)=d+1$. Recent results of Kahn–Kalai, Nilli, and the present author demonstrate that the class of integral polytopes is one of the most important classes having a direct connection with Borsuk's conjecture and problems close to it. In the present paper, with the use of the methods of the set-covering problem new upper bounds are obtained for the minimum number of parts of smaller diameter into which each $d$-dimensional $(0,1)$-polytope or cross-polytope can be partitioned. These bounds are substantially better than the author's similar former results as well as all previously known bounds for $f(d)$. In addition, $(0,1)$-polytopes and cross-polytopes in small dimensions are studied in this paper.

Bibliographie

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

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

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

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

[5] Eggleston H. G., “Covering a three-dimensional set with sets of smaller diameter”, J. London Math. Soc. (2), 30 (1955), 11–24 | DOI | MR | Zbl

[6] Perkal J., “Sur la subdivision des ensembles en parties de diamètre inférieur”, Colloq. Math., 1 (1947), 45

[7] Grünbaum B., “A simple proof of Borsuk's conjecture in three dimensions”, Proc. Cambridge Philos. Soc., 53 (1957), 776–778 | DOI | MR | Zbl

[8] Heppes A., “Térbeli ponthalmazok felosztása kisebb átméröjü részhalmazok összegére”, Magyar Tud. Akad. Math. Fiz. Tud. Oszt. Közl., 7 (1957), 413–416 | MR | Zbl

[9] Katzarowa-Karanowa P., “Über ein euklidisch-geometrisches Problem von B. Grünbaum”, Arch. Math. (Basel), 18 (1967), 663–672 | MR | Zbl

[10] Makeev V. V., “Ob affinnykh obrazakh rombododekaedra, opisannykh vokrug trekhmernogo vypuklogo tela”, Zapiski nauch. sem. POMI, 246, POMI, SPb., 1997, 191–195 | Zbl

[11] Makeev V. V., “Affinno-vpisannye i affinno-opisannye mnogougolniki i mnogogranniki”, Zapiski nauch. sem. POMI, 231, POMI, SPb., 1996, 286–298

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

[13] Rogers C. A., “Symmetrical sets of constant width and their partitions”, Mathematika, 18 (1971), 105–111 | MR | Zbl

[14] Risling A. S., “Problema Borsuka v trekhmernykh prostranstvakh postoyannoi krivizny”, Ukr. geom. sb., 11 (1971), 78–83

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

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

[17] Bourgain J., Lindenstrauss J., “On covering a set in $\mathbb R^d$ by balls of the same diameter”, Geometric aspects of functional analysis, Lecture Notes in Math., 1469, eds. J. Lindenstrauss, V. Milman, Springer-Verlag, Berlin, 1991, 138–144 | MR

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

[19] Nilli A., “On Borsuk's problem”, Contemp. Math., 178 (1994), 209–210 | MR | Zbl

[20] Raigorodskii A. M., “O razmernosti v probleme Borsuka”, UMN, 52:6 (1997), 181–182 | MR | Zbl

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

[22] Erdös P., “My Scottish book “problems””, The Scottish book. Mathematics from the Scottish Café, ed. R. D. Mauldin, Birkhäuser, Boston, 1981, 35–43 | MR

[23] Ziegler G. M., Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions, Preprint, June 2000, TU, Berlin | MR

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

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

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

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

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

[29] Erdös P., “On sets of distances of $n$ points”, Amer. Math. Monthly, 53 (1946), 248–250 | DOI | MR | Zbl

[30] Heppes A., Révész P., “Zum Borsukschen Zerteilungsproblem”, Acta Math. Acad. Sci. Hung., 7 (1956), 159–162 | DOI | MR | Zbl

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

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

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

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

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

[36] Füredi Z., “Turán's type problems”, Surveys in combinatorics, Proc. of the 13th British Combin. Conference, London Math. Soc. Lecture Note Ser., 166, ed. A. D. Keedwell, 1991, 253–300 | MR | Zbl

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

[38] Erdös P., Ko Ch., Rado R., “Intersection theorems for systems of finite sets”, Q. J. Math., 12 (1961), 313–320 | DOI | MR | Zbl

[39] Ahlswede R., Khachatrian L. H., “The complete nontrivial-intersection theorem for systems of finite sets”, J. Combin. Theory Ser. A, 76 (1996), 121–138 | DOI | MR | Zbl

[40] Ahlswede R., Khachatrian L. H., “The complete intersection theorem for systems of finite sets”, European J. Combin., 18 (1997), 125–136 | DOI | MR | Zbl

[41] Frankl P., “The Erdös–Ko–Rado theorem is true for $n=ckt$”, Combinatorics, Colloq. Math. Soc. János Bolyai, 18, 1978, 365–375 | MR | Zbl

[42] Wilson R. M., “The exact bound in the Erdös–Ko–Rado theorem”, Combinatorica, 4 (1984), 247–257 | DOI | MR | Zbl

[43] Deza M., Frankl P., “Erdös–Ko–Rado theorem – 22 years later”, SIAM J. Algebraic Discrete Methods, 4 (1983), 419–431 | DOI | MR | Zbl

[44] Raigorodskii A. M., “The Borsuk partition problem”, London Math. Soc. Lecture Note Series (to appear)

[45] Raigorodskii A. M., Kalnishkan Yu. A., “O probleme Borsuka”, IV Mezhdunarodnaya konferentsiya “Sovremennye problemy teorii chisel i ee prilozheniya”, Tezisy dokladov (Tula, 10–15 sentyabrya 2001 g.), 98–99

[46] Lassak M., “An estimate concerning Borsuk's partition problem”, Bull. Acad. Polon. Sci. Ser. Math., 30 (1982), 449–451 | MR | Zbl