MathLabs

Worked solution: Kahn–Kalai's disproof of Borsuk's conjecture via the Frankl–Wilson theorem

Step 2 of 7: Larman's reduction: turn the geometry into a question about set intersections
In plain words

David Larman noticed a shortcut: if you only look at (0,1)(0,1)-vectors (points whose coordinates are all 00 or 11) that all have the same number of 11s, 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.

∥x−y∥22=2(k−∣A∩B∣),x,y∈{0,1}n of weight k\|x-y\|_2^2 = 2\big(k - |A \cap B|\big), \qquad x,y \in \{0,1\}^n \text{ of weight } k
Detailed analysis

Identify a (0,1)(0,1)-vector x∈{0,1}nx \in \{0,1\}^n with the set A⊂{1,…,n}A \subset \{1,\ldots,n\} of coordinates where xx equals 11. If two such vectors x,yx, y both have exactly kk ones (corresponding to sets A,BA, B of size kk), then ∥x−y∥22=2(k−∣A∩B∣)\|x-y\|_2^2 = 2(k - |A\cap B|): the squared distance shrinks exactly as the overlap ∣A∩B∣|A \cap B| grows, and is maximised precisely when ∣A∩B∣|A \cap B| is as small as possible. So among kk-subsets of {1,…,n}\{1,\ldots,n\}, 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 (0,1)(0,1)-vectors, reduces to a clean combinatorial statement: if K\mathcal{K} is a family of kk-subsets of {1,…,n}\{1,\ldots,n\} such that every two members share exactly tt elements (so K\mathcal K has just one non-trivial pairwise distance, realising the diameter), can K\mathcal K always be split into nn parts so that within each part every two members share at least t+1t+1 elements (i.e. lie at a strictly smaller distance)? A counterexample to this purely finite question — a family K\mathcal K that provably needs far more than nn parts — is exactly what Kahn and Kalai go on to build, without even requiring the constant-intersection hypothesis in its cleanest form.

Terms in this step
(0,1)(0,1)-vector of constant weight
A point in {0,1}n\{0,1\}^n, thought of as a subset of {1,…,n}\{1,\ldots,n\} via its 11-coordinates; 'constant weight kk' means every vector considered has exactly kk ones, i.e. corresponds to a kk-element subset.
Knowledge used in this step