Frankl-Wilson Theorem

The Frankl-Wilson theorem provides strong upper bounds on set families with restricted intersection sizes. It is proved using the linear algebra (dimension) method and has remarkable applications to geometry, coding theory, and combinatorial number theory.

Statement

Theorem6.3Frankl-Wilson Theorem

Let $p$ be a prime and let $L = \{l_1, \ldots, l_s\} \subseteq \{0, 1, \ldots, p-1\}$ . If $\mathcal{F}$ is a family of subsets of $[n]$ , each of size $k$ where $k \not\equiv l_i \pmod{p}$ for any $i$ , and $|F \cap G| \pmod{p} \in L$ for all distinct $F, G \in \mathcal{F}$ , then $|\mathcal{F}| \leq \binom{n}{s}.$

Proof Outline

Proof

Associate to each set $F \in \mathcal{F}$ the polynomial $f_F(x) = \prod_{l \in L} \left(\sum_{i \in F} x_i - l\right) \in \mathbb{F}_p[x_1, \ldots, x_n].$

This polynomial has degree $|L| = s$ . For distinct $F, G \in \mathcal{F}$ , evaluating $f_F$ at the characteristic vector $v_G$ gives $f_F(v_G) = \prod_{l \in L}(|F \cap G| - l) \equiv 0 \pmod{p}$ since $|F \cap G| \bmod p \in L$ .

For $F = G$ : $f_F(v_F) = \prod_{l \in L}(k - l) \not\equiv 0 \pmod{p}$ since $k \bmod p \notin L$ .

Now reduce each polynomial modulo the ideal $(x_i^2 - x_i)$ (since $v_G$ has $0/1$ entries) to obtain polynomials of degree at most $s$ in the reduced polynomial ring. The monomials of degree at most $s$ in this ring span a vector space of dimension $\sum_{j=0}^s \binom{n}{j}$ . But the matrix of evaluations $(f_F(v_G))_{F,G}$ has nonzero diagonal and zero off-diagonal, so the corresponding vectors are linearly independent. We conclude: $|\mathcal{F}| \leq \sum_{j=0}^s \binom{n}{j}.$

For the uniform version (all sets of the same size), a refinement gives the stronger bound $|\mathcal{F}| \leq \binom{n}{s}$ . $\square$

■

Applications

ExampleKahn-Kalai Counterexample to Borsuk's Conjecture

Borsuk conjectured (1933) that every bounded set in $\mathbb{R}^d$ can be partitioned into $d + 1$ sets of smaller diameter. Kahn and Kalai (1993) disproved this using the Frankl-Wilson theorem: they constructed a set in $\mathbb{R}^d$ requiring $(1.2)^{\sqrt{d}}$ parts, exponentially more than $d + 1$ .

RemarkRay-Chaudhuri-Wilson Theorem

The Frankl-Wilson theorem generalizes the Ray-Chaudhuri-Wilson theorem: if $\mathcal{F} \subseteq \binom{[n]}{k}$ and the intersection sizes $|F \cap G|$ take at most $s$ distinct values for $F \neq G$ , then $|\mathcal{F}| \leq \binom{n}{s}$ . This follows from a dimension argument over $\mathbb{R}$ using the same polynomial construction.

ExampleApplication to Chromatic Numbers

The Frankl-Wilson theorem implies that the fractional chromatic number of the Kneser graph $K(n,k)$ is at least $n/k$ , complementing the integer chromatic number result from Lovász's topological proof. This bound is tight, establishing $\chi_f(K(n,k)) = n/k$ .