Borsuk's conjecture

Counterexample

Borsuk's conjecture concerns bounded sets $S \subseteq \R^n$ with more than one point, for $n \ge 1$. It says that every such $S$ can be split into $n + 1$ sets, each of smaller diameter than $S$. The conjecture is false. Kahn and Kalai proved this in 1993. For all large $n$, they found finite sets in $\R^n$ that cannot be split into fewer than $1.2^{\sqrt{n}}$ parts of smaller diameter. This number exceeds $n + 1$ for large $n$.

Their sets consist of the matrices $x x^T$, for $x$ in a suitable family of vectors in $\set{-1, 1}^m$. These matrices are viewed as points of $\R^{m \times m}$ with the Euclidean norm. For two such vectors, $\norm{x x^T - y y^T}^2 = 2 m^2 - 2 (x \cdot y)^2$. So the diameter is attained exactly by the pairs with $x \cdot y = 0$, and a part of smaller diameter contains no orthogonal pair. The Frankl–Wilson theorem shows that such parts are exponentially small in $m$. So exponentially many parts are needed, while the dimension is only of order $m^2$.