Book contents
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
4 - Some old and new problems in combinatorial geometry I: around Borsuk's problem
Published online by Cambridge University Press: 05 July 2015
By
Book contents
- Frontmatter
- Contents
- Preface
- 1 Ramsey classes: examples and constructions
- 2 Recent developments in graph Ramsey theory
- 3 Controllability and matchings in random bipartite graphs
- 4 Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5 Randomly generated groups
- 6 Curves over finite fields and linear recurring sequences
- 7 New tools and results in graph minor structure theory
- 8 Well quasi-order in combinatorics: embeddings and homomorphisms
- 9 Constructions of block codes from algebraic curves over finite fields
- References
Summary
Abstract
Borsuk [16] asked in 1933 if every set of diameter 1 in Rd can be covered by d + 1 sets of smaller diameter. In 1993, a negative solution, based on a theorem by Frankl and Wilson [42], was given by Kahn and Kalai [65]. In this paper I will present questions related to Borsuk's problem.
1 Introduction
The title of this paper is borrowed from Paul Erdős who used it (or a similar title) in many lectures and papers, e.g., [39]. I will describe several open problems in the interface between combinatorics and geometry, mainly convex geometry. In this part, I describe and pose questions related to the Borsuk conjecture. The selection of problems is based on my own idiosyncratic tastes. For a fuller picture, the reader is advised to read the review papers on Borsuk's problem and related questions by Raigorodskii [105, 106, 107, 110, 112]. Among other excellent sources are [13, 14, 18, 89, 99].
Karol Borsuk [16] asked in 1933 if every set of diameter 1 in Rd can be covered by d + 1 sets of smaller diameter. That the answer is positive was widely believed and referred to as the Borsuk conjecture. However, some people, including Rogers, Danzer, and Erdős, suggested that a counterexample might be obtained from some clever combinatorial configuration. In hindsight, the problem is related to several questions that Erdős asked and its solution was a great triumph for Erdősian mathematics.
2 Better lower bounds to Borsuk's problem
The asymptotics
Let f(d) be the smallest integer such that every set of diameter one in Rd can be covered by f(d) sets of smaller diameter. The set of vertices of a regular simplex of diameter one demonstrates that f(d) ≥ d + 1. The famous Borsuk–Ulam theorem [16] asserts that the d-dimensional ball of diameter 1 cannot be covered by d sets of smaller diameter.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2015 , pp. 147 - 174Publisher: Cambridge University PressPrint publication year: 2015
References
[1] , , , , , and , Lenses in arrangements of pseudocircles and their applications, J. ACM 51 (2004), 139–186.Google Scholar
[2] and , Combinatorial GeometryJohn Wiley and Sons, New York, 1995.
[3] , , and , Multilinear polynomials and Frankl–Ray-Chaudhuri–Wilson type intersection theorems, J. Combin. Theory A 58 (1991), 165–180.Google Scholar
[5] , , and , Linear codes with exponentialy many light vectors, J. Combin. Theory A 96 (2001) 396–399.Google Scholar
[6] , , , and , On the complexity of arrangements of circles in the plane, Discrete and Comput. Geometry 26 (2001), 465–492.Google Scholar
[8] , , , and , Lower bounds for measurable chromatic numbers, Geom. Funct. Anal. 19 (2009), 645–661.Google Scholar
[9] , , , and , Spectral bounds for the independence ratio and the chromatic number of an operator (2013), http://arxiv.org/abs/1301.1054.
[10] , , and , The density of sets avoiding distance 1 in Euclidean space (2014), arXiv:1401.6140
[11] , , , and , . Discrete Comput. Geom. 38 (2007), 201–230.
[12] and , Rigidity of ball-polyhedra in Euclidean 3-space, European J. Combin. 27 (2006), 255–268.Google Scholar
[13] and , Results and Problems in Combinatorial Geometry, Cambridge University Press, Cambridge, 1985.
[14] , , and , Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.
[15] , On Borsuk's conjecture for two-distance sets, arXiv:1305.2584. Disc. Comp. Geom., to appear.
[17] and , On covering a set in RN by balls of the same diameter, in Geometric Aspects of Functional Analysis ( and , eds.), Lecture Notes in Mathematics 1469, Springer, Berlin, 1991, pp. 138–144.
[18] , , and , Research problems in discrete geometry, Springer, Berlin, 2005.
[21] , Sur un nouvel invariant des graphes et un critére de planarité, J. Combin. Th. B 50 (1990): 11–21.Google Scholar
[22] and , Sphere Packings, Lattices and Groups, Grundlehren Math. Wiss., vol. 290, Springer, New York, third ed., 1993.
[23] , , and , Unsolved Problems in Geometry, Springer, New York, 1991.
[24] , Large equiangular sets of lines in Euclidean space, Electronic Journal of Combinatorics 7 (2000), Paper R55, 3 pages.
[25] , , and , On constructive upper bounds for the Turàn numbers T(n,2r+1,2r), Congressus Numerantium 65 (1988), 277–280.Google Scholar
[26] and , Spherical sets avoiding a prescribed set of angles, preprint 2014.
[27] and , A semidefinite programming hierarchy for packing problems in discrete geometry, arXiv:1311.3789 (2013).
[28] , Diameters of the pieces in Borsuk's covering Geometriae Dedicata 30 (1989), 35–41.Google Scholar
[29] , The Borsuk conjecture holds for convex bodies with a belt of regular points, Geometriae Dedicata 45 (1993), 301–306.Google Scholar
[30] , The Borsuk conjecture holds for bodies of revolution Journal of Geometry 52 (1995), 64–73.Google Scholar
[31] , An algebraic approach to the association schemes of coding theory, Diss. Universite Catholique de Louvain (1973).Google Scholar
[33] and , Geometry of Cuts and Metrics, Algorithms and Combinatorics, Springer, Berlin, 1997.
[34] , Some properties of graphs of diameters, Discrete Comput. Geom. 24 (2000), 293–299.Google Scholar
[35] , Covering a three-dimensional set with sets of smaller diameter, J. London Math. Soc. 30 (1955), 11–24.Google Scholar
[36] , Convexity, Cambridge University Press, 1958.
[38] , On the combinatorial problems I would like to see solved, Combinatorica 1 (1981), 25–42.Google Scholar
[39] , Some old and new problems in combinatorial geometry, Ann. of Disc. Math. 57 (1984), 129–136.Google Scholar
[40] , , , , and , Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, preprint, 2011.Google Scholar
[42] and , Intersection theorems with geometric consequences, Combinatorica 1 (1981), 259–286.Google Scholar
[43] , , and , Singularities of minimal surfaces and networks and related extremal problems inMinkowski space, Discrete and Computational Geometry Amer. Math. Soc., Providence, 1991, pp. 95–109.
[44] , , , and , Estimating the chromatic numbers of Euclidean spaces by methods of convex minimization, Sb. Math. 200 (2009), N6, 783–801.Google Scholar
[45] and , Geometry of Numbers, North-Holland, Amsterdam, 1987.
[46] , A proof of Váaszonyi's conjecture, Bull. Res. Council Israel, Sect. A 6 (1956), 77–78.Google Scholar
[47] , A simple proof of Borsuk's conjecture in three dimensions, Mathematical Proceedings of the Cambridge Philosophical Society 53 (1957), 776–778.Google Scholar
[48] , Borsuk's partition conjecture in Minkowski planes, Bull. Res. Council Israel (1957/1958), pp. 25–30.Google Scholar
[49] , Borsuk's problem and related questions, Convexity, Proc. Sympos. Pure Math., vol. 7, Amer. Math. Soc, Providence, RI, 1963.Google Scholar
[50] , , , and , On the independence numbers of distance graphs with vertices at {−1, 0, 1}n: estimates, conjectures, and applications to the Borsuk and Nelson – Erdős – Hadwiger problems, J. of Math. Sci. 165 (2010), N6, 689–709.
[51] and , On the Erdős distinct distances problem in the plane, Ann. Math. 181 (2015), 155–190.Google Scholar
[52] , Ein Überdeckungssatz füur den Euklidischen Raum, Portugaliae Math. 4 (1944), 140–144.Google Scholar
[53] , Überdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv., 18 (1945/46), 73–75; Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm.Math. Helv.19 (1946/47), 72–73.
[54] , Térbeli ponthalmazok felosztása kisebbátméerőjű részhalmazok ősszegére, A magyar tudományos akadémia 7 (1957), 413–416.Google Scholar
[55] , Beweis einer Vermutung von A. Vázsonyi, Acta Math. Acad. Sci. Hungar. 7 (1957), 463–466.Google Scholar
[56] , , Zum Borsukschen Zerteilungsproblem, Acta Math. Acad. Sci. Hung. 7 (1956), 159–162.Google Scholar
[59] and : Aufgabe Nr. 167, Jahresbericht d. Deutsch. Math.-Verein. 43 (1934), 114.
[60] and Z. Lángi, On the multiple Borsuk numbers of sets, Israel J. Math. 199 (2014), 219–239.Google Scholar
[61] , A 64-dimensional two-distance counterexample to Borsuk's conjecture, arxiv:1308.0206.
[62] , Coloring nearly-disjoint hypergraphs with n + o(n) colors, J. Combin. Th. A 59 (1992), 31–39,Google Scholar
[63] , Asymptotics of Hypergraph Matching, Covering and Coloring Problems, Proceedings of the International Congress of Mathematicians 1995, pp. 1353–1362.Google Scholar
[64] and , On a problem of Füredi and Seymour on covering intersecting families by pairs, Jour. Comb. Th. Ser A. 68 (1994), 317–339.Google Scholar
[65] and , A counterexample to Borsuk's conjecture, Bull. Amer. Math. Soc. 29 (1993), 60–62.Google Scholar
[66] and , A fractional version of the Erdős-Faber-Lovász conjecture Combin. 12 (1992), 155–160.Google Scholar
[67] and , Frankl–Rödl type theorems for codes and permutations, preprint.
[68] , A new approach to Turan's Problem (research problem) Graphs and Comb. 1 (1985), 107–109.Google Scholar
[69] and , The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l1. In The 46th Annual Symposium on Foundations of Computer Science 2005.Google Scholar
[70] and , Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.
[71] , An approximative theorem for Borsuk's conjecture, Proc. Cambridge Phil. Soc. (1974), N1, 75–76.Google Scholar
[73] , On lifting of estimation of chromatic number of ℝn in higher dimension, Doklady Math. 429 (2009), N3, 305–308.Google Scholar
[74] , On the chromatic number of ℝn with an arbitrary norm, Discrete Math. 311 (2011), 437–440.Google Scholar
[75] and , On the chromatic number of R9, J. of Math. Sci. 163 (2009), N6, 720–731.
[76] and , Counterexamples to Borsuk's conjecture on spheres of small radii, Moscow Journal of Combinatorics and Number Theory 2 N4 (2012), 27–48.
[77] and , Proof of Schur's conjecture in Rd, arXiv:1402.3694.
[78] , , and : Finite sets in Rd with many diameters a survey. In: Proceedings of the International Conference on Mathematics and Applications (ICMA-MU 2005, Bangkok), Mahidol University Press, Bangkok, 2005, 91–112.
[79] , , and , Ball polytopes and the Vázsonyi problem. Acta Mathematica Hungarica 126 (2010), 99–163.
[80] , , and , Diameter graphs and full equiintersectors in classical geometries. Rendiconti del Circolo Matematico di Palermo (2), Suppl. 70, Part II (2002), 65–74.Google Scholar
[81] and , The decomposition of the n-sphere and the boundaries of plane convex domains, Ann. Discrete Math. 20 (1984), 209–214.
[82] , A note on the realization of distances within sets in Euclidean space, Comment.Math.Helvet. 53 (1978), 529–535.
[83] and , The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24Google Scholar
[84] , An estimate concerning Borsuk's partition problem, Bull. Acad. Polon. Sci. Ser. Math. 30 (1982), 449–451.
[85] , Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. 45 (1983), 317–323.
[86] , Hunting unit-distance graphs in rational n-spaces, Geombinatorics 13 (2003), N2, 49–53.
[87] , Dependence of volume and diameter of sets in an n-dimensional Banach space (Russian), Uspehi Mat. Nauk 18 (1963), 165–170.
[88] and , Intersection reverse sequences and geometric applicationsJour.Combin. Th. A 113 (2006), 675–691.Google Scholar
[89] , Lectures on Discrete Geometry, Springer, May 2002.
[90] , Using the Borsuk – Ulam theorem, Universitext, Springer, Berlin, 2003.
[91] , The number of unit distances is almost linear for most norms, Advances in Mathematics 226 (2011), 2618–2628.Google Scholar
[92] and , Remarks on Schurs Conjecture, in: Computational Geometry and Graphs Lecture Notes in Computer Science Volume 8296, 2013, pp. 120–131
[93] and , On colouring the space n with several forbidden distances, Math. Notes 81 (2007), N5, 656–664.
[94] and , New lower bounds for the independence numbers of distance graphs with vertices at {−1, 0, 1}, Math. Notes 89 (2011), N2, 307–308.Google Scholar
[95] , Note on the space chromatic number, Discrete Math. 256 (2002), 499–507.
[96] , On Borsuk problem, in Jerusalem Combinatorics 1993 ( et , eds) 209–210, Contemporary Math. 178, AMS, Providence, 1994.
[97] and . Fourier analysis, linear programming, and densities of distance avoiding sets in Rn, J. Eur.Math. Soc. 12 (2010) 1417–1428.Google Scholar
[98] , The Beginnings of Geometric Graph Theory, Erdős centennial, Bolyai Soc. Math. Studies 25, 2013.
[99] , Lectures on Discrete and Polyhedral Geometry, forthcoming.
[100] , M.Sc thesis, Hebrew University of Jerusalem, 2012.
[101] , Equilateral sets in Minkowski spaces, Proc. Amer. Math. Soc. 29 (1971), 369–374.
[102] , Borsuk's conjecture fails in dimensions 321 and 322, arXiv: CO/0202112, 2002.
[103] , Gallai–Sylvester Theorem for Pairwise Intersecting Unit Circles, Discrete and Computational Geometry 28 (2002), 607–624.
[104] and , On the Number of Edges in a Topological Graph with no Self-intersecting Cycle of Length 4, in 19th ACM Symposium on Computational Geometry, San Diego, USA, 2003, pp 98–103.
[105] , Around Borsuk's conjecture, Itogi Nauki i Tekhniki, Ser. “Contemp. Math.” 23 (2007), 147–164; English transl. in J. of Math. Sci., 154 (2008), N4, 604–623.
[106] , Cliques and cycles in distance graphs and graphs of diameters, Discrete Geometry and Algebraic Combinatorics, AMS, Contemporary Mathematics, 625 (2014), 93–109.Google Scholar
[107] , Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, ed., Springer, 2013, 429–460.
[108] , On a bound in Borsuk's problem, Uspekhi Mat. Nauk, 54 (1999), N2, 185–186; English transl.in Russian Math. Surveys, 54 (1999), N2, 453–454.Google Scholar
[109] , On the dimension in Borsuk's problem, Russian Math. Surveys, 52 (1997), N6, 1324–1325.Google Scholar
[110] , The Borsuk partition problem: the seventieth anniversary, Mathematical Intelligencer 26 (2004), N3, 4–12.Google Scholar
[111] , The Borsuk problem and the chromatic numbers of some metric spaces, Uspekhi Mat. Nauk, 56 (2001), N1, 107–146; English transl.in Russian Math. Surveys, 56 (2001), N1, 103–139.Google Scholar
[112] , Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202–248.
[114] , Symmetrical sets of constant width and their partitions, Mathematika 18 (1971), 105–111.Google Scholar
[115] , Odd integral distances among points in the plane, Geombinatorics 5 (1996), 156–159.Google Scholar
[117] , On the volume of sets having constant widthIsrael J. of Math. Volume 63 (1988), 178–182.Google Scholar
[118] , , , and , On the number of maximal regular simplices determined by n points in Rd. In: Discrete and Computational Geometry The Goodman-Pollack Festschrift, Eds. , , , and , Springer, New York et al., 2003, 767–787.
[119] , A survey of two-graphs, in: Teorie Combinatorie (Proc. Intern. Coll., Roma 1973), Accad. Nac. Lincei, Roma, 1976, pp. 481–511
[120] , Analogues of regular simplexes in normed spaces (Russian), Dokl. Akad. Nauk SSSR 222 (1975), 1303-1305. English translation: Soviet Math. Dokl. 16 (1975), 787–789.Google Scholar
[121] , On Coloring the Odd-Distance GraphElectronic Journal of Combinatorics 16:N12 (2009).Google Scholar
[122] , Equilateral sets in finite-dimensional normed spaces. In: Seminar of Mathematical Analysis, eds. , , , Secretariado de Publicationes, Universidad de Sevilla, Seville, 2004, pp. 195–237.
[123] and , A lower bound for the equilateral number of normed spaces, Proc. of the Amer. Math. Soc. 136 (2008), 127–131.Google Scholar
[124] on unit distances and the Szemerédi – Trotter theorems, Paul Erdős and his Mathematics, Bolyai Series Budapest, Math. Soc., Springer, 11 (2002), 649–666.
[125] , , Bounds on the measurable chromatic number of ℝn, Discrete Math. 75 (1989), 343–372.
[127] , Distances realized by sets covering the plane, J. Combin. Theory A 14 (1973), 187–200.
[128] , A 4-Chromatic Graph With a Special Plane Drawing, Australian Mathematics Society (Series A) 28 (1979), 1–8.Google Scholar
[129] . Spherical sets without orthogonal point pairs, American Mathematical Monthly (1974): 1101–1102.Google Scholar
[130] , Coloring Hamming graphs, optimal binary codes, and the 0/1 - Borsuk problem in low dimensions, Lect. Notes Comput. Sci. 2122 (2001), 159–171.Google Scholar
- 4
- Cited by