Worked solution: Kahn–Kalai's disproof of Borsuk's conjecture via the Frankl–Wilson theorem
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.
Theorem (Frankl–Wilson, 1981). Let be a prime power and . Let be a family of -subsets of such that no two sets in intersect in exactly elements. Then .
The striking feature of this bound is its shape: the total number of -subsets of an -set is , exponentially larger (relative to the dimension) than the bound , which only counts subsets of size roughly 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 . A closely related result of Frankl and Vojtěch Rödl, answering a question of Erdős, gives a similar but weaker bound under the same hypothesis for any divisible by four, without requiring to be a prime power.
- 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.