×

Around Borsuk’s hypothesis. (English. Russian original) Zbl 1165.52001

J. Math. Sci., New York 154, No. 4, 604-623 (2008); translation from Sovrem. Mat., Fundam. Napravl. 23, 147-164 (2007).
In 1933 K. Borsuk posed the question: Is it true that every bounded set in \(\mathbb{R}^{n}\) admits a partition into \(n+1\) parts of smaller diameter? The problem attracted many researchers, among them were prominent mathematicians. Numerous methods and results arose when making attempts to solve the problem. The hypothesis (conjecture) was proved for \(n=2\), 3 and for some special classes of sets. In 1993 counterexamples (for rather large dimensions \(n\)) were constructed answering the question negative.
The paper under review surveys numerous general approaches to solving Borsuk’s problem, involving several other classical problems. Many interesting results that have some connection with Borsuk’s problem are discussed.
Below the contents of the article are given:
Introduction
1. Notation and various versions of problem formulation
2. Universal covers
3. Universal covering systems
4. Truncations of an octahedron
5. Spherical u.c.s. in dimension 3
6. Sets of constant width
7. Covering the sets by balls
8. Special classes of sets
9. Counterexamples to Borsuk’s hypothesis
10. Borsuk’s, Grünbaum’s, and the Nelson–Erdös–Hadwiger problems for lattice polyhedra and graphs
11. Chromatic numbers of finite geometric graphs and the relation between the Borsuk and Nelson–Erdös–Hadwiger problems
References
The bibliography includes 123 sources.

MSC:

52-02 Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
52C22 Tilings in \(n\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] V. G. Boltyanskii, ”The problem on illuminating the boundary of a convex body,” Izv. Mold. Filiala AN SSSR, 76, No. 10, 77–84 (1960).
[2] V. G. Boltyanskii and I. Ts. Gokhberg, Theorems and Problems of Combinatorial Geometry [in Russian], Nauka, Moscow (1965).
[3] E. D. Gluskin, ”Extremal properties of orthogonal parallelepipeds and their application to the geometry of Banach spaces,” Mat. Sb., 136, No. 1, 85–96 (1988). · Zbl 0648.52003
[4] L. Danzer, B. Grünbaum, and V. Clee, Helly’s Theorem [Russian transl.], Mir, Moscow (1968).
[5] R. Diestel’, Theory of Graphs [in Russian], Izd. Inst. Mat., Novosibirsk (2002).
[6] G. A. Kabatyanskii and V. I. Levenshtein, ”Estimates for Packings on a Sphere and in a Space,” Probl. Pered. Inform., 14, 1–17 (1978).
[7] A. B. Katok and B. Khassel’blat, Introduction to the Modern Theory of Dynamical Systems [in Russsian], Faktorial, Moscow (1999).
[8] G. Conway and N. Slohen, Packings of Balls, a Lattice and a Group [Russian transl.], Mir, Moscow (1990).
[9] I. P. Kornfel’d, Ya. G. Sinai, and S. V. Fomin, Ergodic Theory [in Russian], Nauka, Moscow (1980).
[10] N. N. Kuzyurin, ”An asymptotic study of the covering problem,” Probl. Kibern., No. 37, 19–56 (1980). · Zbl 0464.05021
[11] V. K. Leont’ev, ”Upper estimates of the {\(\alpha\)}-depth of (0, 1)-matrices,” Mat. Zam., 15, No. 3, 421–429 (1974).
[12] L. A. Lyusternik and L. G. Shnirel’man, Topological Methods in Variational Problems [in Russian], Moscow (1930).
[13] V. V. Makeev, ”Universal covers and projections of bodies of constant width,” Ukr. Geom. Sb., bf32, 84–88 (1989). · Zbl 0707.51018
[14] V. V. Makeev, ”Affine-inscribed and affine-circumscribed polygons and polyhedra,” Zap. Nauchn. Sem. POMI, 231, 286–298 (1996). · Zbl 0908.52002
[15] V. V. Makeev, ”On affine images of a rhombododecahedron circumscribed around a three-dimensional convex body,” Zap. Nauchn. Sem. POMI, 246, 191–195 (1997). · Zbl 0921.52001
[16] E. I. Nechiporuk, ”On topological principles of self-correction,” Probl. Kibern., No. 21, 5–103 (1969). · Zbl 0195.46602
[17] A. M. Raigorodskii, ”On dimension in Borsuk’s problem,” Usp. Mat. Nauk, 52, No. 6, 181–182 (1997). · Zbl 0934.52005
[18] A. M. Raigorodskii, ”On one estimate in Borsuk’s problem,” Usp. Mat. Nauk, 54, No. 2, 185–186 (1999). · Zbl 0942.52004
[19] A. M. Raigorodskii, ”Systems of general representatives,” Fund. Prikl. Mat., 5, No. 3, 851–860 (1999) · Zbl 0963.05003
[20] A. M. Raigorodskii, ”On a chromatic number of a space,” Usp. Mat. Nauk, 55, No. 2, 147–148 (2000). · Zbl 0966.05029
[21] A. M. Raigorodskii, ”Borsuk’s problem for (0, 1)-polyhedra and cross-polytopes,” Dokl. Ross. Akad. Nauk, 371, 600–603 (2002).
[22] A. M. Raigorodskii, ”Borsuk’s problem and chromatic numbers of certain metric spaces,” Usp. Mat. Nauk, 56, No. 1, 107–146 (2001). · Zbl 1008.54018
[23] A. M. Raigorodskii, ”Borsuk’s problem for (0, 1)-polyhedra and cross-polytopes,” Dokl. Ross. Akad. Nauk, 384, 593–597 (2002).
[24] A. M. Raigorodskii, ”On one problem of an optimal covering of sets by balls,” Chebyshev. Sb., 3, No. 2(4), 100–106 (2002).
[25] A. M. Raigorodskii, ”Borsuk’s and Hadwiger’s problems and systems of vectors with bans on inner products,” Usp. Mat. Nauk, 57, No. 3, 159–160 (2002).
[26] A. M. Raigorodskii, ”Borsuk’s problem for integer polyhedra,” Mat. Sb., 193, No. 10, 139–160 (2002).
[27] A. M. Raigorodskii, ”On lower estimates for Borsuk’s and Hadwiger’s numbers,” Usp. Mat. Nauk, 59, No. 3, 177–178 (2003).
[28] A. M. Raigorodskii, ”Borsuk’s, Grünbaum, and Hadwiger’s problems for certain classes of polyhedra and graphs,” Dokl. Ross. Akad. Nauk, 388, No. 6, 738–742 (2003).
[29] A. M. Raigorodskii, ”The Erdös-Hadwiger problem and chromatic numbers of finite geometric graphs,” Dokl. Ross. Akad. Nauk, 392, No. 3, 313–317 (2003). · Zbl 1125.05041
[30] A. M. Raigorodskii, ”Borsuk’s and Grünbaum problems for lattice polyhedra,” Izv. Ross. Akad. Nauk, 69, No. 3, 96–121 (2004).
[31] A. M. Raigorodskii, ”On the chromatic number of the space with the metric l q,” Usp. Mat. Nauk, 59, No. 5, 161–162 (2004). · Zbl 1066.05066
[32] A. M. Raigorodskii, ”On chromatic numbers of metric spaces.” Chebyshev. Sb., 5, No. 1(9), 175–185 (2004).
[33] A. M. Raigorodskii, ”On relationship between the Borsuk and Nelson-Erdös-Hadwiger problems,” Usp. Mat. Nauk, 60 (2005) · Zbl 1138.05026
[34] A. M. Raigorodskii, ”The Erdös-Hadwiger problem and chromatic numbers of finite geometric graphs,” Mat. Sb., 196, No. 1 (2005). · Zbl 1070.05044
[35] A. M. Raigorodskii, ”Chromatic numbers of metric spaces,” in: Proc. Inst. Math. of the National Academy of Sciences, Belarus (2005). · Zbl 1070.05044
[36] A. M. Raigorodskii, ”On Borsuk and Erdös-Hadwiger’s numbers,” Mat. Zametki (2005). · Zbl 1138.05026
[37] A. M. Raigorodskii and Yu. A. Kalnishkan, ”On Borsuk’s problem in \(\mathbb{R}\)3,” Mat. Zametki, 74, No. 1, 149–151 (2003).
[38] A. M. Raigorodskii and A. A. Chernov, ”Borsuk’s problem for certain classes of polyhedra,” Chebyshev. Sb., 5, No. 2(10), 98–103 (2004).
[39] A. S. Riesling, ”Borsuk’s problem in three-dimensional spaces of constant curvature,” Ukr. Geom. Sb., 11, 78–83 (1971).
[40] K. Rogers, Packings and Coverings [Russian transl.], Mir, Noscow (1968).
[41] A. A. Sapozhenko, ”On complexity of disjunctive normal forms obtained by using the gradient algorithm,” Diskr. Anal., Novosibirsk, No. 21, 62–71 (1972).
[42] V. E. Tarakanov, Combinatorial Problems and (0, 1)-Matrices [in Russian], Nauka, Moscow (1985). · Zbl 0641.05012
[43] H. Hadwiger and H. Debrunner, Combinatorial Geometry of a Plane [Russian transl.], Nauka, Moscow (1965).
[44] F. Harari, Theory of Graphs [Russian transl.], Mir, Moscow (1973).
[45] R. Ahlswede and L. H. Khachatrian, ”The complete nontrivial-intersection theorem for systems of finite sets,” J. Combin. Theor. Ser. A, 76, 121–138 (1997). · Zbl 0861.05058
[46] R. Ahlswede, L. H. Khachatrian, ”The complete intersection theorem for systems of finite sets,” Eur. J. Combin., 18, 125–136 (1997). · Zbl 0869.05066
[47] M. Aigner and G. M. Ziegler, Proofs from THE BOOK, Springer-Verlag Berlin (1998). · Zbl 0905.00001
[48] N. Alon, L. Babai, and H. Suzuki, ”Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems,” J. Combin. Theor. Ser. A, 58, 165–180 (1991). · Zbl 0751.05009
[49] N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience Ser. in Discr. Math. and Optimization (2000).
[50] L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, September 1992.
[51] M. Benda and M. Perles, ”Colorings of metric space,” Geombinatorics, 9, 113–126 (2000). · Zbl 0951.05037
[52] B. Bollobás, ”The chromatic number of random graphs,” Combinatorica, 8, 49–56 (1988). · Zbl 0666.05033
[53] B. Bollobás, Random Graphs, Cambridge Univ. Press, Second Edition (2001).
[54] V. G. Boltyanski, H. Martini and P. S. Soltan, Excursions into Combinatorial Geometry, Berlin-Heidelberg: Universitext, Springer-Verlag (1997). · Zbl 0877.52001
[55] K. Borsuk, ”Über die Zerlegung einer Euklidischen n-dimensionalen Vollkugel in n Mengen,” Verh. Internat Math. Kongr., Zürich, 2, 192 (1932). · JFM 58.0647.06
[56] K. Borsuk, ”Drei Sätze über die n-dimensionale euklidische Sphäre,” Fundam. Math., 20, 177–190 (1933). · JFM 59.0560.01
[57] J. Bourgain and J. Lindenstrauss, ”On covering a set in \(\mathbb{R}\)d by balls of the same diameter,” in: Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Berlin: Springer-Verlag (1991), pp. 138–144. · Zbl 0815.46017
[58] L. Danzer, ”On the kth diameter in E d and a problem of Grünbaum,” Proc. Colloquium on Convexity, Copenhagen, (1965), p. 41.
[59] N. G. de Bruijn and P. Erdös, ”A colour problem for infinite graphs and a problem in the theory of relations,” Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54, No. 5, 371–373 (1951). · Zbl 0044.38203
[60] M. Deza, P. Erdös, and P. Frankl, ”Intersection properties of systems of finite sets,” Proc. London Math. Soc., 36, 369–384 (1978). · Zbl 0407.05006
[61] M. Deza, P. Erdös, and N. M. Singhi, ”Combinatorial problems on subsets and their intersections,” Adv. Math., Suppl. Stud., 1, 259–265 (1978). · Zbl 0434.05001
[62] M. Deza and P. Frankl, ”Erdös-Ko-Rado theorem: 22 years later,” SIAM J. Alg. Disc. Methods, 4, 419–431 (1983). · Zbl 0526.05001
[63] H. G. Eggleston, ”Covering a three-dimensional set with sets of smaller diameter,” J. London Math. Soc., 30, 11–24 (1955). · Zbl 0065.15304
[64] H. G. Eggleston, Convexity, Cambridge Univ. Press (1958).
[65] P. Erdös, ”On sets of distances of n points,” Am. Math. Mon., 53, 248–250 (1946). · Zbl 0060.34805
[66] P. Erdös, ”My Scottish Book Problems,” in: The Scottish Book, Mathematics from the Scottish Café (R. D. Mauldin ed.), Birkhäuser (1981), pp.35–43.
[67] P. Erdös, Chao Ko and R. Rado, ”Intersection theorems for systems of finite sets,” J. Math. Oxford, 12(48) (1961). · Zbl 0100.01902
[68] P. Frankl, ”The Erdös-Ko-Rado theorem is true for n = ckt,” Combinatorics, Coll. Math. Soc. J. Bolyai 18, 365–375 (1978).
[69] P. Frankl, ”Extremal problems and coverings of the space,” Eur. J. Combin., 1, 101–106 (1980). · Zbl 0463.05043
[70] P. Frankl and R. M. Wilson, ”Intersection theorems with geometric consequences,” Combinatorica, 1, 357–368 (1981). · Zbl 0498.05048
[71] Z. Füredi, ”Turán’s type problems,” in: Surveys in Combinatorics, Proc. of the 13th British Combinatorics Conference (A. D. Keedwell, ed.). Cambridge Univ. Press, London Math. Soc. Lecture Note Series, 166 (1991), pp. 253–300.
[72] D. Gale, ”On inscribing n-dimensional sets in a regular n-simplex,” Proc. Am. Math. Soc., 4, 222–225 (1953). · Zbl 0051.13403
[73] J. Grey und B. Weissbach, Ein weiteres Gegenbeispiel zur Borsukschen Vermutung, Univ. Magdeburg, Fakultät für Mathematik, Preprint 25 (1997).
[74] P. M. Gruber and C. G. Lekkerkerker, Geometry of Numbers, North-Holland, Amsterdam (1987). · Zbl 0611.10017
[75] B. Grünbaum, ”A simple proof of Borsuk’s conjecture in three dimensions,” Proc. Cambridge Philos. Soc., 53, 776–778 (1957). · Zbl 0073.39201
[76] B. Grünbaum, ”Borsuk’s problem and related questions,” Proc. Symp. Pure Math., 7, 271–284 (1963). · Zbl 0151.29101
[77] H. Hadwiger, ”Überdeckung einer Menge durch Mengen kleineren Durchmessers,” Commun. Math. Helv., 18, 73–75 (1945/46); Mitteilung betreffend meine Note: ”Überdeckung einer Menge durch Mengen kleineren Durchmessers,” Commun. Math. Helv., 19, 72–73 (1946/47). · Zbl 0063.01851
[78] H. Hadwiger, ”Ungelöste Probleme No. 20,” Elem. Math., 12, 121 (1957). · Zbl 0080.15403
[79] H. Hadwiger, ”Ungelöste Probleme No. 38,” Elem. Math., 15, 130–131 (1960).
[80] H. Hadwiger, ”Ungelöste Probleme No. 40,” Elem. Math., 16, 103–104 (1961).
[81] H. C. Hansen, ”Small universal covers for sets of unit diameter,” Geom. Dedicata, 42, 205–213 (1992). · Zbl 0752.52011
[82] E. Helly, ”Über Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten,” Monatsh. Math., 37, 281–302 (1930). · JFM 56.0499.03
[83] E. Helly, ”On a collection of convex bodies with common points,” Russ. Math. Surv., 2, No. 2 (1936).
[84] A. Heppes, ”Térbeli ponthalmazok felosztása kisebb átméröjü részhalmazok összegére,” A magyar tudományos akadémia, 7, 413–416 (1957).
[85] A. Heppes and P. Révész, ”Zum Borsukschen Zerteilungsproblem,” Acta Math. Acad. Sci. Hung., 7, 159–162 (1956). · Zbl 0073.39103
[86] A. Hinrichs, ”Spherical codes and Borsuk’s conjecture,” Discr. Math., 243, 253–256 (2002). · Zbl 1010.52004
[87] A. Hinrichs and Ch. Richter, ”New sets with large Borsuk numbers,” (2002) http://www.minet.uni-jena.de/hinrichs/paper/18/borsuk.pdf · Zbl 1028.52012
[88] H. W. E. Jung, ”Über die kleinste Kugel, die eine räumliche Figur einschliesst,” J. Reine Angew. Math., 123, 241–257 (1901). · JFM 32.0296.05
[89] J. Kahn and G. Kalai, ”A counterexample to Borsuk’s conjecture,” Bull. Am. Math. Soc. (New Ser.), 29, No. 1, 60–62 (1993). · Zbl 0786.52002
[90] J-H. Kang and Z. Füredi, ”Distance graphs on \(\mathbb{Z}\)n with l 1-norm,” Theor. Comput. Sci., 319, No. 1–3, 357–366 (2004). · Zbl 1043.05047
[91] G. Katona, T. Nemetz, and M. Simonovitz, ”On a graph problem of Turan” [in Hungarian], Mat. Lapok, 15, 228–238 (1964). · Zbl 0138.19402
[92] P. Katzarowa-Karanowa, ”Über ein euklidisch-geometrisches Problem von B. Grünbaum,” Arch. Math., 18, 663–672 (1967). · Zbl 0152.39503
[93] D. Larman, ”Open problem 6. Convexity and Graph theory,” (M. Rozenfeld and J. Zaks eds.), Ann. Discr. Math., 20, North-Holland, Amsterdam and New York (1984), p. 336.
[94] D. G. Larman, ”A note on the realization of distances within sets in Euclidean space,” Comment. Math. Helv., 53, 529–535 (1978). · Zbl 0408.52005
[95] D. G. Larman and C. A. Rogers, ”The realization of distances within sets in Euclidean space,” Mathematika, 19, 1–24 (1972). · Zbl 0246.05020
[96] M. Lassak, ”An estimate concerning Borsuk’s partition problem,” Bull. Acad. Pol. Sci. Ser. Math., 30, 449–451 (1982). · Zbl 0514.52011
[97] H. Lenz, ”Zur Zerlegung von Punktmengen in solche kleineren Durchmessers,” Arch. Math., 6, No. 5, 413–416 (1955). · Zbl 0065.15401
[98] H. Lenz, ”Über die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers,” Arch. Math., 4, 34–40 (1956). · Zbl 0073.17503
[99] N. Linial, R. Meshulam, and M. Tarsi, ”Matroidal bijections between graphs,” J. Combin. Theor. Ser. B, 45, No. 1, 31–44 (1988). · Zbl 0724.05067
[100] H. Martini and V. Soltan, ”Combinatorial problems on the illumination of convex bodies,” Aequationes Math., 57, 121–152 (1999). · Zbl 0937.52006
[101] A. Nilli, ”On Borsuk’s problem,” Contemp. Math., 178, 209–210 (1994). · Zbl 0816.52001
[102] J. Pál, ”Über ein elementares Variationsproblem,” Danske Videnskab. Selskab., Math.-Fys. Meddel, 3, No. 2 (1920). · JFM 47.0684.01
[103] C. Payan, ”On the chromatic number of cube like graphs,” Discr. Math., 103, 271–277 (1992). · Zbl 0772.05043
[104] J. Petersen, Färbung von Borsuk-Graphen in niedriger Dimension, Diplomarbeit, TU Berlin (1998).
[105] O. Pikhurko, ”Borsuk’s conjecture fails in dimensions 321 and 322,” e-print: arXiv: math.CO/0202112, 2002.
[106] A. M. Raigorodskii, ”The Borsuk partition problem: the seventieth anniversary,” Mathematical Intelligencer, 26, No. 4, 4–12 (2004). · Zbl 1067.52006
[107] R. Rankin, ”On the closest packing of spheres in n dimensions,” Ann. Math., 48, 1062–1081 (1947). · Zbl 0029.34503
[108] D. K. Ray-Chaudhuri and R. M. Wilson, ”On t-designs,” Osaka J. Math., 12, 735–744 (1975). · Zbl 0342.05018
[109] F. Reuleaux, Lehrbuch der Kinematik I. Vieweg, Braunschweig (1875). · JFM 07.0540.03
[110] C. A. Rogers, ”Covering a sphere with spheres,” Mathematika, 10, 157–164 (1963). · Zbl 0158.19603
[111] C. A. Rogers, ”Symmetrical sets of constant width and their partitions,” Mathematika, 18, 105–111 (1971). · Zbl 0227.52006
[112] C. A. Rogers, ”Some problems in the geometry of convex bodies. The Geometric Vein,” in: The Coxeter Festschrift (C. Davis, B. Grünbaum, and F. A. Sherk, eds.), Springer-Verlag, New York (1981), pp. 279–284.
[113] F. Schiller, Zur Berechnung und Abschätzung von Färbungszahlen und der -Funktion von Graphen, Diplomarbeit, TU Berlin (1999).
[114] J. Schopp, ”Die Abdeckung ebener Bereiche mit konstanten Durchmessern durch drei Kreise von kleinerem Durchmesser,” Vortrag, gehalten auf der Geometrie-Tegen in Tihany (Ungarn) (1965).
[115] O. Schramm, ”Illuminating sets of constant width,” Mathematika, 35, 180–189 (1988). · Zbl 0673.52003
[116] A. Soifer, ”Chromatic number of the plane: a historical essay,” Geombinatorics, 13–15 (1991). · Zbl 0853.05038
[117] A. Soifer, Mathematical Coloring Book, Center for Excellence in Mathematical Education (1997).
[118] P. Turán, ”Egy grafelmeletiszelsoertek feladatrol,” Mat. Fiz. Lapok, 48, 436–452 (1941).
[119] B. Weissbach, ”Polyhedral covers,” Collect. Math. Soc. J. Bolyai, 48 (Intuitive Geometry), North-Holland, Amsterdam et al. (1987), pp. 639–646.
[120] B. Weissbach, ”Sets with large Borsuk number,” Beitr. Alg. Geom., 41, 417–423 (2000). · Zbl 0973.52011
[121] R. M. Wilson, ”The exact bound in the Erdös-Ko-Rado theorem,” Combinatorica, 4, 247–257 (1984). · Zbl 0556.05039
[122] G. M. Ziegler, ”Lectures on 0/1-polytopes,” in: Polytopes-Combinatorics and Computation (G. Kalai and G. M. Ziegler, eds.), DMV, seminar 29, Birkhäuser, Basel (2000), pp. 1–44. · Zbl 0966.52012
[123] G. M. Ziegler, ”Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions,” Lect. Notes Comput. Sci., 2122, 159–171 (2001). · Zbl 1004.52010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.