Worked solution: Kahn–Kalai's disproof of Borsuk's conjecture via the Frankl–Wilson theorem
David Larman noticed a shortcut: if you only look at -vectors (points whose coordinates are all or ) that all have the same number of s, then the distance between any two of them is completely determined by how many coordinates they share — no calculus or continuous geometry needed, just counting overlaps between finite sets. This turns Borsuk's geometric partition problem into a purely combinatorial puzzle about families of sets and how their intersection sizes can be controlled.
Identify a -vector with the set of coordinates where equals . If two such vectors both have exactly ones (corresponding to sets of size ), then : the squared distance shrinks exactly as the overlap grows, and is maximised precisely when is as small as possible. So among -subsets of , the pairs at maximum (diameter-realising) distance are exactly the pairs with minimum intersection.
Larman observed that Borsuk's conjecture, restricted to finite sets of constant-weight -vectors, reduces to a clean combinatorial statement: if is a family of -subsets of such that every two members share exactly elements (so has just one non-trivial pairwise distance, realising the diameter), can always be split into parts so that within each part every two members share at least elements (i.e. lie at a strictly smaller distance)? A counterexample to this purely finite question — a family that provably needs far more than parts — is exactly what Kahn and Kalai go on to build, without even requiring the constant-intersection hypothesis in its cleanest form.
- -vector of constant weight
- A point in , thought of as a subset of via its -coordinates; 'constant weight ' means every vector considered has exactly ones, i.e. corresponds to a -element subset.