Around Borsuk's Hypothesis

A. M. Raigorodskii

Contemporary Mathematics. Fundamental Directions, Geometry and mechanics, Tome 23 (2007), pp. 147-164.

Bibliographie

[1] Boltyanskii V. G., “Zadacha ob osveschenii granitsy vypuklogo tela”, Izv. Moldavskogo filiala AN SSSR, 76:10 (1960), 77–84

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

[3] Gluskin E. D., “Ekstremalnye svoistva ortogonalnykh parallelepipedov i ikh prilozhenie k geometrii banakhovykh prostranstv”, Mat. sb., 136:1 (1988), 85–96 | MR | Zbl

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

[5] Distel R., Teoriya grafov, Inst. Mat., Novosibirsk, 2002

[6] Kabatyanskii G. A., Levenshtein V. I., “O granitsakh dlya upakovok na sfere i v prostranstve”, Problemy peredachi informatsii, 14:1 (1978), 3–25 | MR | Zbl

[7] Katok A. B., Khasselblat B., Vvedenie v sovremennuyu teoriyu dinamicheskikh sistem, Faktorial, M., 1999

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

[9] Kornfeld I. P., Sinai Ya. G., Fomin S. V., Ergodicheskaya teoriya, Nauka, M., 1980 | MR

[10] Kuzyurin N. N., “Asimptoticheskoe issledovanie zadachi o pokrytii”, Probl. kibern., 37 (1980), 19–56 | MR | Zbl

[11] Leontev V. K., “Verkhnie otsenki $\alpha$-glubiny $(0,1)$-matrits”, Mat. zametki, 15:3 (1974), 421–429 | MR

[12] Lyusternik L. A., Shnirelman L. G., Topologicheskie metody v variatsionnykh zadachakh, M., 1930

[13] Makeev V. V., “Universalnye pokryshki i proektsii tel postoyannoi shiriny”, Ukr. geom. sb., 32 (1989), 84–88 | MR

[14] Makeev V. V., “Affinno-vpisannye i affinno-opisannye mnogougolniki i mnogogranniki”, Zap. nauch. semin. POMI, 231, 1996, 286–298 | MR

[15] Makeev V. V., “Ob affinnykh obrazakh rombododekaedra, opisannykh vokrug trekhmernogo vypuklogo tela”, Zap. nauch. semin. POMI, 246, 1997, 191–195 | MR | Zbl

[16] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, Probl. kibern., 21 (1969), 5–103

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

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

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

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

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

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

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

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

[25] Raigorodskii A. M., “Problemy Borsuka i Khadvigera i sistemy vektorov s zapretami na skalyarnye proizvedeniya”, Usp. mat. nauk, 57:3 (2002), 159–160 | MR

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

[27] Raigorodskii A. M., “O nizhnikh otsenkakh dlya chisel Borsuka i Khadvigera”, Usp. mat. nauk, 59:3 (2003), 177–178 | MR

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

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

[30] Raigorodskii A. M., “Problemy Borsuka i Gryunbauma dlya reshetchatykh mnogogrannikov”, Izv. RAN, 69:3 (2005), 81–108 | MR | Zbl

[31] Raigorodskii A. M., “O khromaticheskom chisle prostranstva s metrikoi $l_q$”, Usp. mat. nauk, 59:5 (2004), 161–162 | MR | Zbl

[32] Raigorodskii A. M., “O khromaticheskikh chislakh metricheskikh prostranstv”, Chebyshevskii sb., 5, no. 1(9), 2004, 175–185 | MR

[33] Raigorodskii A. M., “O svyazi mezhdu zadachami Borsuka i Erdesha–Khadvigera”, Usp. mat. nauk, 60:4 (2005), 219–220 | MR | Zbl

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

[35] Raigorodskii A. M., Khromaticheskie chisla metricheskikh prostranstv, Tr. in-ta matematiki NAN Belarusi, 2005 | Zbl

[36] Raigorodskii A. M., “O chislakh Borsuka i Erdesha–Khadvigera”, Mat. zametki, 79:6 (2006), 913–924 | MR | Zbl

[37] Raigorodskii A. M., Kalnishkan Yu. A., “O probleme Borsuka v $\mathbb{R}^3$”, Mat. zametki, 74:1 (2003), 149–151 | MR | Zbl

[38] Raigorodskii A. M., Chernov A. A., “Problema Borsuka dlya nekotorykh klassov mnogogrannikov”, Chebyshevskii sb., 5, no. 2(10), 2004, 98–103 | MR

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

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

[41] Sapozhenko A. A., “O slozhnosti diz'yunktnykh normalnykh form, poluchaemykh s pomoschyu gradientnogo algoritma”, Diskretnyi analiz, no. 21, Novosibirsk, 1972, 62–71 | Zbl

[42] Tarakanov V. E., Kombinatornye zadachi i $(0,1)$-matritsy, Nauka, M., 1985 | MR

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

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

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

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

[47] Aigner M. and Ziegler G. M., Proofs from THE BOOK, Springer-Verlag, Berlin, 1998 | Zbl

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

[49] Alon N., Spencer J., The probabilistic method, Wiley Interscience, 2000 | MR

[50] Babai L., Frankl P., Linear algebra methods in combinatorics. Part 1, The Univ. of Chicago Press, 1992 | Zbl

[51] Benda M., Perles M., “Colorings of metric spaces”, Geombinatorics, 9 (2000), 113–126 | MR | Zbl

[52] Bollobás B., “The chromatic number of random graphs”, Combinatorica, 8 (1988), 49–56 | DOI | MR

[53] Bollobás B., Random Graphs, Cambridge Univ. Press, 2001 | MR

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

[55] Borsuk K., “Über die Zerlegung einer Euklidischen $n$-dimensionalen Vollkugel in $n$ Mengen”, Verh. Int. Math. Kongr., v. 2, Zürich, 1932, 192 | Zbl

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

[57] Bourgain J., Lindenstrauss J., “On covering a set in $\mathbb{R}^d$ by balls of the same diameter”, Geometric Aspects of Functional Analysis, Lect. Notes Math., 1469, eds. J. Lindenstrauss and V. Milman, Springer-Verlag, Berlin, 1991, 138–144 | MR

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

[59] de Bruijn N. G., Erdős P., “A colour problem for infinite graphs and a problem in the theory of relations”, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54:5 (1951), 371–373 | Zbl

[60] Deza M., Erdős P., Frankl P., “Intersection properties of systems of finite sets”, Proc. London Math. Soc., 36 (1978), 369–384 | DOI | MR | Zbl

[61] Deza M., Erdős P., Singhi N. M., “Combinatorial problems on subsets and their intersections”, Adv. Math., Suppl. Stud., 1 (1978), 259–265 | MR | Zbl

[62] Deza M., Frankl P., “Erdős–Ko–Rado theorem: 22 years later”, SIAM J. Alg. Disc. Methods., 4 (1983), 419–431 | DOI | MR | Zbl

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

[64] Eggleston H. G., Convexity, Cambridge Univ. Press., 1958 | MR

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

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

[67] Erdős P., Chao Ko, Rado R., “Intersection theorems for systems of finite sets”, J. Math. Oxford, 12(48) (1961) | MR

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

[69] Frankl P., “Extremal problems and coverings of the space”, Eur. J. Combs., 1 (1980), 101–106 | MR | Zbl

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

[71] Füredi Z., “Turán's type problems”, Surv. Combinatorics, Proc. 13th British Combin. Conference, London Math. Soc. Lect. Note Ser., 166, ed. A. D. Keedwell, Cambridge Univ. Press, 1991, 253–300 | MR

[72] Gale D., “On inscribing $n$-dimensional sets in a regular $n$-simplex”, Proc. Amer. Math. Soc., 4 (1953), 222–225 | DOI | MR | Zbl

[73] Grey J., Weissbach B., Ein weiteres Gegenbeispiel zur Borsukschen Vermutung, Preprint 25, Univ. Magdeburg, Fakultät für Mathematik, 1997

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

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

[76] Grünbaum B., “Borsuk's problem and related questions”, Proc. Symp. Pure Math., 7 (1963), 271–284 | MR | Zbl

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

[78] Hadwiger H., “Ungelöste Probleme No 20”, Elem. Math., 12 (1957), 121 | MR

[79] Hadwiger H., “Ungelöste Probleme No 38”, Elem. Math., 15 (1960), 130–131 | MR

[80] Hadwiger H., “Ungelöste Probleme No 40”, Elem. Math., 16 (1961), 103–104 | MR

[81] Hansen H. C., “Small universal covers for sets of unit diameter”, Geom. Dedic., 42 (1992), 205–213 | DOI | MR | Zbl

[82] Helly E., “Über Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten”, Monatsh. Math., 37 (1930), 281–302 | DOI | MR | Zbl

[83] Helly E., “On a collection of convex bodies with common points”, Russ. Math. Surv., 2:2 (1936)

[84] Heppes A., “Térbeli ponthalmazok felosztása kisebb átmérőjű részhalmazok ősszegére”, A Magyar Tudományos Akadémia, 7 (1957), 413–416 | MR | Zbl

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

[86] Hinrichs A., “Spherical codes and Borsuk's conjecture”, Discr. Math., 243 (2002), 253–256 | DOI | MR | Zbl

[87] Hinrichs A., Richter C., New sets with large Borsuk numbers, http://www.minet.uni-jena.de/h̃inrichs/paper/18/borsuk.pdf

[88] Jung H. W. E., “Über die kleinste Kugel, die eine räumliche Figur einschliesst”, J. Reine Angew. Math., 123 (1901), 241–257 | DOI | Zbl

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

[90] Kang J-H., Füredi Z., “Distance graphs on $\mathbb{Z}^n$ with $l_1$-norm”, Theor. Comp. Sci., 319:1–3 (2004), 357–366 | MR | Zbl

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

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

[93] Larman D., “Open problem 6”, Convexity and graph theory, Ann. Discr. Math., 20, eds. M. Rozenfeld and J. Zaks, North-Holland, Amsterdam–New York, 1984, 336

[94] Larman D. G., “A note on the realization of distances within sets in Euclidean space”, Comm. Math. Helv., 53 (1978), 529–535 | DOI | MR | Zbl

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

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

[97] Lenz H., “Zur Zerlegung von Punktmengen in solche kleineren Durchmessers”, Arch. Math., 6:5 (1955), 413–416 | DOI | MR | Zbl

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

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

[100] Martini H., Soltan V., “Combinatorial problems on the illumination of convex bodies”, Aequationes Math., 57 (1999), 121–152 | DOI | MR | Zbl

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

[102] Pál J., Über ein elementares Variationsproblem., Bull. de l'Acad. de Dan., 3, no. 2, 1920, 35 S | Zbl

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

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

[105] Pikhurko O., Borsuk's conjecture fails in dimensions 321 and 322, arXiv: /arXiv:math/0202112

[106] Raigorodskii A. M., “The Borsuk partition problem: the seventieth anniversary”, Math. Intelligencer, 26:4 (2004), 4–12 | DOI | MR | Zbl

[107] Rankin R., “On the closest packing of spheres in $n$ dimensions”, Ann. Math., 48 (1947), 1062–1081 | DOI | MR | Zbl

[108] Ray-Chaudhuri D. K., Wilson R. M., “On $t$-designs”, Osaka J. Math., 12 (1975), 735–744 | MR

[109] Reuleaux F., Lehrbuch der Kinematik, I, Vieweg, Braunschweig, 1875 | Zbl

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

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

[112] Rogers C. A., “Some problems in the geometry of convex bodies”, The Geometric Vein – The Coxeter Festschrift, eds. C. Davis, B. Grünbaum, and F. A. Sherk, Springer-Verlag, New York, 1981, 279–284 | MR

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

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

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

[116] Soifer A., “Chromatic number of the plane: a historical essay”, Geombinatorics, 1:3 (1991), 13–15 | MR | Zbl

[117] Soifer A., Mathematical coloring book, Center for Excellence in Mathematical Education, 1997

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

[119] Weissbach B., “Polyhedral covers”, Coll. Math. Soc. J. Bolyai, 48, North-Holland, Amsterdam, 1987, 639–646 | MR

[120] Weissbach B., “Sets with large Borsuk number”, Beiträge Alg. Geom., 41 (2000), 417–423 | MR | Zbl

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

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

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