MathLabs

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

Step 3 of 7: The Frankl–Wilson intersection theorem: the missing algebraic tool
In plain words

Peter Frankl and Richard Wilson proved, in 1981, a strikingly precise limit on how large a family of same-size sets can be if you forbid one specific intersection size: once you rule out just one 'forbidden overlap', the family collapses from astronomically large to a size controllable by ordinary binomial coefficients. Their proof is an early triumph of the 'linear algebra method' in combinatorics: turn each set into a polynomial, show the polynomials must be linearly independent, and read off a bound on how many of them can exist from the dimension of the space they live in.

∣K∣≤2(n−1n/4−1)(Frankl–Wilson, 1981; n=4k, k prime power)|\mathcal K| \le 2\binom{n-1}{n/4-1} \qquad \text{(Frankl–Wilson, 1981; } n=4k,\ k \text{ prime power)}
Detailed analysis

Theorem (Frankl–Wilson, 1981). Let kk be a prime power and n=4kn = 4k. Let K\mathcal{K} be a family of n/2n/2-subsets of {1,…,n}\{1, \ldots, n\} such that no two sets in K\mathcal{K} intersect in exactly n/4n/4 elements. Then ∣K∣≤2(n−1n/4−1)|\mathcal K| \le 2\binom{n-1}{n/4-1}.

The striking feature of this bound is its shape: the total number of n/2n/2-subsets of an nn-set is (nn/2)\binom{n}{n/2}, exponentially larger (relative to the dimension) than the bound 2(n−1n/4−1)2\binom{n-1}{n/4-1}, which only counts subsets of size roughly n/4n/4 from a slightly smaller ground set. So forbidding a single intersection size — an extremely mild-sounding restriction — forces a family to be a vanishing fraction of all possible sets, a gap that grows without bound as n→∞n \to \infty. A closely related result of Frankl and Vojtěch Rödl, answering a question of Erdős, gives a similar but weaker bound ∣K∣≤(1.99)n|\mathcal K| \le (1.99)^n under the same hypothesis for any nn divisible by four, without requiring k=n/4k=n/4 to be a prime power.

Terms in this step
linear algebra method (combinatorics)
A proof technique that bounds the size of a combinatorial family by associating a polynomial or vector to each member, showing these are linearly independent in some vector space, and concluding the family is no larger than that space's dimension.
Knowledge used in this step