Some old and new problems in combinatorial geometry I: around Borsuk's problem

Borsuk asked in 1933 if every set of diameter 1 in $R^d$ can be covered by $d+1$ sets of smaller diameter. In 1993, a negative solution, based on a theorem by Frankl and Wilson, was given by Kahn and Kalai. In this paper I will present questions related to Borsuk's problem.

• Publication year

  2015

• Venue

  Surveys in Combinatorics

• Publication date

  2015-05-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/CBO9781316106853.005arXiv 1505.04952
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Geometry of Numbers

  2017cited by this paper
• On the Erdős distinct distances problem in the plane

  2015cited by this paper
• Spherical sets avoiding a prescribed set of angles

  2015influential reference
• Frankl-Rödl type theorems for codes and permutations

  2014cited by this paper
• Proof of Schur’s Conjecture in ℝD

  2014cited by this paper
• The Density of Sets Avoiding Distance 1 in Euclidean Space

  2014influential reference
• On Schur’s conjecture in ℝ4

  2014cited by this paper
• On Borsuk’s Conjecture for Two-Distance Sets

  2013cited by this paper
• Spectral bounds for the independence ratio and the chromatic number of an operator

  2013cited by this paper
• The Beginnings of Geometric Graph Theory

  2013cited by this paper
• A 64-dimensional two-distance counterexample to Borsuk's conjecture

  2013influential reference
• Cliques and cycles in distance graphs and graphs of diameters

  2013influential reference
• Coloring Distance Graphs and Graphs of Diameters

  2013cited by this paper
• A semidefinite programming hierarchy for packing problems in discrete geometry

  2013cited by this paper
• On the multiple Borsuk numbers of sets

  2012cited by this paper
• Combinatorial Geometry

  2012cited by this paper
• On the chromatic number of Rn with an arbitrary norm

  2011cited by this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cited by this paper
• On the chromatic number of ℝn with an arbitrary norm

  2011cited by this paper
• New lower bounds for the independence numbers of distance graphs with vertices in {−1, 0, 1}n

  2011cited by this paper
• AN ALGEBRAIC APPROACH TO THE ASSOCIATION SCHEMES OF CODING THEORY

  2011cited by this paper
• Counterexamples to Borsuk’s conjecture on spheres of small radius

  2010cited by this paper
• On independence numbers of distance graphs with vertices in {-1,0,1}n: estimates, conjectures, and applications to the Nelson–Erdős–Hadwiger problem and the Borsuk problem

  2010cited by this paper
• The number of unit distances is almost linear for most norms

  2010influential reference
• On the chromatic number of ℝ9

  2009cited by this paper
• Estimating the chromatic numbers of Euclidean space by convex minimization methods

  2009cited by this paper
• Geometry of cuts and metrics

  2009cited by this paper
• On Coloring the Odd-Distance Graph

  2009cited by this paper
• Ball polytopes and the Vázsonyi problem

  2009cited by this paper
• Fourier analysis, linear programming, and densities of distance avoiding sets in R^n

  2008cited by this paper
• Lower Bounds for Measurable Chromatic Numbers

  2008influential reference
• Surveys in Contemporary Mathematics: Three lectures on the Borsuk partition problem

  2007cited by this paper
• Using The Borsuk-Ulam Theorem

  2007cited by this paper
• Ball-Polyhedra

  2007cited by this paper
• Colorings of the space ℝn with several forbidden distances

  2007cited by this paper
• A lower bound for the equilateral number of normed spaces

  2006cited by this paper
• Rigidity of ball-polyhedra in Euclidean 3-space

  2006cited by this paper
• Research problems in discrete geometry

  2005cited by this paper
• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

  2005cited by this paper
• Intersection reverse sequences and geometric applications

  2004cited by this paper
• Γ and B

  2004cited by this paper
• Equilateral sets in finite-dimensional normed spaces

  2004cited by this paper
• The Borsuk Partition Problem: The Seventieth Anniversary

  2004influential reference
• -convexity

  2004cited by this paper
• New sets with large Borsuk numbers

  2003cited by this paper
• Equilateral Sets in lpn

  2003cited by this paper
• Discrete and computational geometry : the Goodman-Pollack Festschrift

  2003cited by this paper
• On the Number of Maximal Regular Simplices Determined by n Points in Rd

  2003cited by this paper
• Equilateral sets in l np

  2002influential reference
• On the space chromatic number

  2002cited by this paper
• Borsuk's Conjecture Fails in Dimensions 321 and 322

  2002cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Spherical codes and Borsuk's conjecture

  2002cited by this paper
• Gallai—Sylvester Theorem for Pairwise Intersecting Unit Circles

  2002influential reference
• Coloring Hamming Graphs, Optimal Binary Codes, and the 0/1-Borsuk Problem in Low Dimensions

  2001cited by this paper
• On the Complexity of Arrangements of Circles in the Plane

  2001cited by this paper
• Linear Codes with Exponentially Many Light Vectors

  2001cited by this paper
• Some Properties of Graphs of Diameters

  2000cited by this paper
• Large Equiangular Sets of Lines in Euclidean Space

  2000cited by this paper
• On a bound in Borsuk's problem

  1999cited by this paper
• Sphere packings, I

  1998cited by this paper
• On the dimension in Borsuk's problem

  1997cited by this paper
• Packings with large minimum kissing numbers

  1997cited by this paper
• Constructive Upper Bounds for the Turán Number

  1997cited by this paper
• Excursions into Combinatorial Geometry

  1996cited by this paper
• Asymptotics of Hypergraph Matching, Covering and Coloring Problems

  1995cited by this paper
• The Borsuk conjecture holds for bodies of revolution

  1995cited by this paper
• A Problem of Füredi and Seymour on Covering Intersecting Families by Pairs

  1994cited by this paper
• A counterexample to Borsuk's conjecture

  1993influential reference
• The Borsuk conjecture holds for convex bodies with a belt of regular points

  1993cited by this paper
• A fractional version of the Erdős-Faber-Lovász conjecture

  1992cited by this paper
• Coloring Nearly-Disjoint Hypergraphs with n+o(n) Colors

  1992cited by this paper
• Unsolved Problems In Geometry

  1991cited by this paper
• On convering a set in R N by balls of the same diameter

  1991influential reference
• Old And New Unsolved Problems In Plane Geometry And Number Theory

  1991cited by this paper
• Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems

  1991cited by this paper
• Sphere Packings, Lattices and Groups

  1990cited by this paper
• Singularities of Minimal Surfaces and Networks and Related Extremal Problems in Minkowski Space

  1990cited by this paper
• Sur un nouvel invariant des graphes et un critère de planarité

  1990cited by this paper
• Bounds on the measurable chromatic number of Rn

  1989cited by this paper
• Diameters of the pieces in Borsuk's covering

  1989cited by this paper
• Illuminating Sets of Constant Width

  1988influential reference
• Unit-distance graphs in rational n-spaces

  1988cited by this paper
• On the volume of sets having constant width

  1988cited by this paper
• Results and Problems in Combinatorial Geometry

  1985cited by this paper
• A new approach to Turán's conjecture

  1985cited by this paper
• The Decomposition of the n-Sphere and the Boundaries of Plane Convex Domains

  1984cited by this paper
• Some Old and New Problems in Combinatorial Geometry

  1984cited by this paper
• Intersection theorems with geometric consequences

  1981influential reference
• On the combinatorial problems which I would most like to see solved

  1981cited by this paper
• A 4-chromatic graph with a special plane drawing

  1979cited by this paper
• A note on the realization of distances within sets in euclidean space

  1978cited by this paper
• Spherical codes and designs

  1977cited by this paper
• A SURVEY OF TWO-GRAPHS

  1976cited by this paper
• Spherical Sets Without Orthogonal Point Pairs

  1974cited by this paper
• An approximate theorem for Borsuk's conjecture

  1974cited by this paper
• Distances Realized by Sets Covering the Plane

  1973cited by this paper
• The realization of distances within sets in Euclidean space

  1972cited by this paper
• Equilateral sets in Minkowski spaces

  1971cited by this paper
• Symmetrical sets of constant width and their partitions

  1971cited by this paper

• Conic optimization for extremal geometry

  2025influential citation
• On asymptotic Lebesgue's universal covering problem

  2025cites this paper
• Small Volume Bodies of Constant Width

  2024cites this paper
• Convex Bodies of Constant Width with Exponential Illumination Number

  2024influential citation
• Small Volume Bodies of Constant Width with Tetrahedral Symmetries

  2024influential citation
• Optimization hierarchies for distance-avoiding sets in compact spaces

  2023influential citation
• Convex bodies of constant width with exponential illumination number

  2023influential citation
• Unit and Distinct Distances in Typical Norms

  2023cites this paper
• Odd Distances in Colourings of the Plane

  2022cites this paper
• Four classic problems

  2022cites this paper
• Graph and hypergraph colouring via nibble methods: A survey

  2021cites this paper
• A solution to Ringel's circle problem

  2021cites this paper
• Domes over Curves

  2020cites this paper
• Borsuk’s partition problem and finite point sets

  2018cites this paper
• Complete positivity and distance-avoiding sets

  2018cites this paper
• Borsuk’s partition problem and finite point sets

  2018cites this paper
• A COUNTEREXAMPLE TO A CONJECTURE OF LARMAN AND ROGERS ON SETS AVOIDING DISTANCE 1

  2018cites this paper
• Forbidden vector‐valued intersections

  2017cites this paper
• Combinatorial distance geometry in normed spaces

  2017cites this paper
• On Almost-Equidistant Sets - II

  2017cites this paper