Karol Borsuk conjectured in 1933 that every bounded set in can be covered by sets of smaller diameter. Jeff Kahn and I found a counterexample in 1993. It is based on the Frankl-Wilson theorem.

Let be the set of vectors of length . Suppose that and is a prime, as the conditions of Frankl-Wilson theorem require. Let . All vectors in are unit vectors.

Consider the set . is a subset of .

**Remark:** If , regard as the by matrix with entries .

It is easy to verify that:

**Claim:** .

It follows that all vectors in are unit vectors, and that the inner product between every two of them is nonnegative. The diameter of is therefore . (Here we use the fact that the square of the distance between two unit vectors and is 2 minus twice their inner product.)

Suppose that has a smaller diameter. Write for some subset of . This means that (and hence also ) does not contain two orthogonal vectors and therefore by the Frankl-Wilson theorem

.

It follows that the number of sets of smaller diameter needed to cover is at least . This clearly refutes Borsuk’s conjecture for large enough . **Sababa.**

Let me explain in a few more words how looks like when is large. the dominant binomial coefficient in the the sum defining is . (Since every binomial coefficient in the sum is smaller than half the next binomial coefficient.) is smaller than . When is large this binomial coefficient equal to , where is the entropy function. To verify it and even to get better estimates you can use Stirling’s formula.

We will further discuss Borsuk’s conjecture and related problems in a later post.

An extremely flattering I was very happy to read a description of the work of Jeff Kahn and me in the context of surprises in mathematics and theoretical computer science can be found in Dick’s Lipton’s blog.

Gil KalaiHere is a wikipedia article on the problem http://en.wikipedia.org/wiki/Borsuk%27s_conjecture

Pingback: Some musings around Borsuk’s conjecture « Konrad Swanepoel’s blog

rjliptonI disagree. I think my post is well deserved. One of the cool results of all time. And one of the biggest surprises.

dick

Pingback: Around Borsuk’s Conjecture 1: Some Problems | Combinatorics and more

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

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