Kahn-Kalai counterexample to the Borsuk conjecture

Kahn and Kalai represented uniform subsets by quadratic sign vectors so that diameter pairs correspond to one forbidden intersection size. The Frankl-Wilson theorem bounds each smaller-diameter part, forcing exponentially many parts while the ambient dimension grows only quadratically.

Take $N=4p-1$, $|A|=|B|=2p-1$ and sign vectors $u_A=21_A-1$. The Frobenius inner product of two outer products is $(u_A\cdot u_B{)}^2$, proving the formula. The squared Euclidean distance is largest precisely when $|A\cap B|=p-1$, where the inner product is minus one. The common diagonal can be deleted, leaving an isometric representation in dimension $\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ if off-diagonal coordinates are multiplied by $\sqrt{2}$. The Frankl-Wilson theorem then bounds each smaller-diameter class.

Use the balanced cut-vector distance formula with $p=13$. There are $\left(\genfrac{}{}{0ex}{}{51}{25}\right)=247959266474052$ distinct cuts. A subset of strictly smaller diameter contains no pair with side intersection thirteen, so deleting their shared coordinate one and applying the Frankl-Wilson theorem bounds its size by $\left(\genfrac{}{}{0ex}{}{51}{12}\right)=158753389900$. At least 1562 smaller-diameter parts are needed, exceeding $1325+1$. The cut vectors occupy an affine hyperplane in ${\mathbb{R}}^{1326}$, which identifies isometrically with ${\mathbb{R}}^{1325}$ and gives the stated explicit counterexample.

Represent a balanced partition of $[4p]$ by the zero-one vector recording which unordered pairs lie across its cut. Complementary subsets represent the same cut; choose the representative containing coordinate one. Two such cuts differ on the pairs crossing the symmetric difference of their sides, giving the displayed distance. Its maximum is $4p^2$, attained exactly when $t=p$. Every cut has $4p^2$ occupied coordinates, so the vectors lie in an affine hyperplane of dimension at most $\left(\genfrac{}{}{0ex}{}{4p}{2}\right)-1$.