Around Borsuk’s Conjecture 1: Some Problems

Posted on June 30, 2011 by Gil Kalai

Greetings to all!

Karol Borsuk conjectured in 1933 that every bounded set in R^d can be covered by d+1 sets of smaller diameter. In a previous post I described the counterexample found by Jeff Kahn and me. I will devote a few posts to related questions that are still open. I will list and discuss such questions in the first and second  parts. In the third part I will describe an approach towards better examples which is related to interesting extremal combinatorics. (Of cocyclec. this post appeared already.) In the fourth part I will try to “save the conjecture”, namely to present a variation of the conjecture which might be true. Let f(d) be the smallest integer so that every set of diameter one in R^d can be covered by f(d) sets of smaller diameter

For a bounded metric space X let b(X) be the smallest number of subsets of smaller diameter needed to cover X.  We can redefine f(d) to be the smallest value of b(X) over bounded subsets of the d-dimensional Euclidean space.

1) What is the asymptotic behavior of f(d)?

Improving the lower bound

The best lower bound are of the form exp(C \sqrt d). The best known value of C was found by Andrei Raigorodskii   In the previous post I presented a speculative approach towards improving the exponent from d^{1/2} to a higher power of d. Is the true exponent one?

Improving the upper bound.

The best asymptotic upper bound is of the form \sqrt{(3/2)+o(1)}^d. There are two different proofs for this result. The first by Oded Schramm is based on covering a set of constant width by smaller homothets. The second by Jean Bourgain and Joram Lindenstrauss is based by covering a set of diameter 1 by balls of diameter 1. There is a result by Danzer showing that we need at least 1.001^d balls of diameter 1 to cover an arbitrary set of diameter 1 in R^d.

2) Dimension 4 and other low dimensions

Is there a counter example in dimension 4? What is the smallest $lated d$ for which Borsuk’s conjecture is false?

3) Order preserving embeddings for the elliptic metric space

Let {\cal E}_{n-1} be the metric space of lines through the origin in R^{n} where the distance between two lines is the smaller angle between them. Frankl Wilson’s theorem implies an exponential lower bound in n for b({\cal E}_n). The crux of the matter for the counterexample is that there is an embedding \phi from {\cal E}_{n-1} to R^{n^2} so that  the order relation between distances is preserved. So that if d(x,y) \le d(z,u) then d(\phi(x),\phi(y)) \le d(\phi(z),\phi(u)).

The embedding \phi is very simple. It is given by \phi(x) =x\otimes x.

(As a matter of fact we need this property to hold just for the case that z and u are of maximum distance.)

Problem: Let \psi be an order preserving embedding of the elliptic n-dimensional space into a d-dimensional Euclidean space. Does it follows that d is at least quadratic in n?

Metric embeddings have become a very hot topic in the last two decades. But I am not aware of much study of questions related to embeddings that preserve the order relations between distances.

4) Larman’s conjecture and Erdos-Faver-Lovasz conjecture

The proof

Larman’s conjecture: Let F be a family of k-subsets of \{1,2,\dots,n\}. Suppose that every two sets in \cal f have at least r elements in common, then F can be divided into at most n families so that every two sets in each of these families have at least r+1 elements in common!

Larman observed that Borsuk’s conjecture implies Larman’s conjecture. But on the other hand while Borsuk’s conjecture looked correct Larman’s conjecture did not look correct. One of the earliest observation

Question: Is Larman’s conjecture for r=1 correct?

A question that closely resembles to the case r=1 of Larman’s conjecture is:

Erdos-Faber-Lovasz Conjecture: Let F be a family of k-subsets of \{1,2,\dots,n\}. Suppose that every two sets in \cal f have at most one element in common, then F can be divided into at most n families so that every two sets in each of these families are disjoint!

5) Borsuk’s conjecure for two distances sets

A set in latex R^d$ is called a 2-distance set if it realizes only 2 distances.

Problem (also posed by David Larman in the 70s): Prove the assertion of Borsuk’s conjecture for two-distance sets.

This entry was posted in Combinatorics, Convexity and tagged , . Bookmark the permalink.

11 Responses to Around Borsuk’s Conjecture 1: Some Problems

  1. Andy D says:
    June 30, 2011 at 6:29 pm

    Very nice questions. Here’s a (not carefully-considered) attempt at a related one:

    given a finite set S of m points in R^d, let dd(S) be the number of distinct pairwise distances in S. We’d like to partition S into S_1, \ldots, S_k such that dd(S_i) < dd(S) for all i.

    How large must k be in general (as determined by m, d)? The Borsuk function f(d) is an easy upper bound.

    Reply
  2. Andriy says:
    May 23, 2013 at 12:45 pm

    Well, the Borsuk’s conjecture for two distance sets is also wrong. The smallest known example is coming from the strongly regular graph G2(4).
    http://arxiv.org/abs/1305.2584

    Reply
  3. Andriy says:
    May 23, 2013 at 9:59 pm

    Thank you very much! I still hope that it is possible to reduce 65. But it seems not very easy.

    Reply

  4. Pingback: Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65! | Combinatorics and more

  5. Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more

  6. Pingback: Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture | Combinatorics and more

  7. Pingback: Some Mathematical Puzzles that I encountered during my career | Combinatorics and more

  8. Pingback: Serge Vlăduţ : Lattices with exponentially large kissing numbers | Combinatorics and more

  9. Felix says:
    September 3, 2020 at 3:58 pm

    Dear author,
    im new to the Borsuk conjecture, but I already spent some time studying it by now.

    Considering Larmans question we now know that two-distance can help to construct counter-examples like Bondarenko did.

    My concern at the moment is:
    How did Larman come up with two-distance set? Why is it reasonable to think that those kind of sets contain many difficulties intrinsic to the general problem? What are those difficulties?

    Reply

  10. Pingback: To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus! | Combinatorics and more

Leave a reply to Andy D Cancel reply