Borsuk's Conjecture

Published Aug 17, 2025

Can every bounded subset $E$ of the space $\mathbb {R} ^{n}$ be partitioned into $(n + 1)$ sets, each of which has a smaller diameter than $E$?

—Borsuk’s Conjecture

The first counterexample was shown in 1993 by Kahn and Kalai, decades after the problem was posed. Surprisingly, however, one only needs elementary undergraduate math to disprove the conjecture.

Sets With Omitted Intersection Size

Define $[n] = \{1, 2, \dots, n\}$, and $\binom{[n]}{k}$ the set of subsets of $[n]$ with size $k$. We will prove the following statement:

Omitted Intersection Lemma

Let $p$ be a prime. If $A_1, A_2, \dots, A_m$ are distinct elements of $\binom{[4p]}{2p}$ such that

$$|A_i \cup A_j| \not = p \quad \forall \quad 1 \leq i \not = j \leq m$$

If $f(p)$ is the maximum $m$ possible, $f = \bigO(c^{4p})$ for some positive constant $c < 16$ independent of $p$.

Consider a maximal construction for $m$. Note that for each $A_i$, there should be some $A_j = [4p] \setminus A_i$. Therefore, we can further impose the restriction $|A_i \cup A_j| \not = 0$. Our restriction is now $|A_i \cup A_j| \not = 0 \pmod{p}$, so we can work under $\mathbb{F}_p$. Consider the characteristic vector $1_i \in \mathbb{F}_p^{4p}$ of $A_i$, and define the polynomial $F : \mathbb{F}_p^{4p} \times \mathbb{F}_p^{4p} \to \mathbb{F}_p$ as follows:

By Fermat’s Little Theorem, $F(1_i, 1_j) \not = 0$ if and only if $i = j$. Now consider the $m \times m$ matrix $M$ with $(i, j)$ entry $F(1_i, 1_j)$. Since $M$ is diagonal, $\rank M = m$. However note that the number of monomials in the expansion of $F$ is $1 + {5p - 2 \choose p - 1}$ by Stars and Bars.

Fact

If for some $f$, $g$, each entry $(i, j)$ of a matrix is $f(i) g(j)$, then this matrix has rank $1$.

Therefore, decomposing $M$ into a sum of $1 + {5p - 2 \choose p - 1}$ rank $1$ matrices as defined by the monomials, we have a bound on $m$:

Using Stirling estimates. Of course, $\frac{5}{4} \cdot \sqrt[4]{5} < 2 < 16$. $\square$

Fun exercise: We can get a slightly better bound on $c$ by making use of the fact that $x_i, y_i \in \{0, 1\}$. Details will be left to the reader.

A Graph Embedding

We define a graph $G_{4p}$ as follows:

• The $\binom{4p}{2p}$ elements of $\binom{[4p]}{2p}$ are the vertices.
• There is an edge between two vertices if and only if their corresponding sets have intersection size $p$.

Now let’s embed our graph into $\mathbb{R}^{{4p \choose 2}}$. For each vertex $v \in \binom{[4p]}{2p}$, we define its embedding $\varphi : V \to \mathbb{R}^{{4p \choose 2}}$ by associating each entry of $\varphi(v)$ with an unordered pair of elements from $[4p]$. This entry is zero unless exactly one element in the pair is in $v$ (the other would be in $[4p] \setminus v$), in which case the entry is $1$.

We claim that with this embedding, the diameter is exactly between adjacent vertices. Consider two vertices $v, w$ with $|v \cap w| = k$.

$\lvert \varphi(v)_i - \varphi(w)_i \rvert = 1$ (and not zero) if and only if either

• One element of the pair is in $v \cap w$ and the other is in $v \setminus w$ or $w \setminus v$.
• One element of the pair is in $[4p] \setminus (v \cup w)$ and the other is in $v \setminus w$ or $w \setminus v$.

Note that $v \cap w$, $v \setminus w$, $w \setminus v$, and $[4p] \setminus (v \cup w)$ are disjoint. Totally there are $4k(2p - k)$ such $i$ where $\lvert \varphi(v)_i - \varphi(w)_i \rvert = 1$, therefore $\text{dist}(\varphi(v), \varphi(w)) = 2\sqrt{k(2p - k)}$, which is maximized at exactly $k = p$. $\square$

Putting It Together

Our graph embedding is a bounded subset of $\mathbb{R}^n$, where $n = {4p \choose 2}$. Since the diameter is between any two adjacent vertices, each partition according to Borsuk’s Conjecture is an independent set.

Consider a sufficiently large $p$. By our Omitted Intersection Lemma, the independence number $\alpha$ of this graph is $\bigO(c^{4p})$. The chromatic number of the graph $\chi$ further satisfies $\chi \cdot \alpha \geq |V|$, so we can bound $\chi$:

This is on the order of $\Omega(C^{\sqrt{n}})$ for some $C > 1$. Of course, one needs at least $\chi$ partitions, which clearly disproves the conjecture. Conside the growth rate we obtained, the conjecture was way off!

$\blacksquare$