= Ray-Chaudhuri–Wilson theorem
{c}
{wiki}
Let $0\leq s\leq k\leq n$, and let $\mathcal F$ be a <uniform set family> of $k$-element subsets of $[n]$. If distinct members have at most $s$ possible <intersection> sizes, then the <Ray-Chaudhuri–Wilson theorem> gives
$$
|\mathcal F|\leq\binom ns.
$$
For $s\leq\min\{k,n-k\}$, let $L$ be the allowed intersection sizes and use, over the <rational numbers>, the <intersection polynomials>
$$
P_A(x)=\prod_{\ell\in L}\left(\sum_{i\in A}x_i-\ell\right).
$$
Their evaluation on the family's <characteristic vectors of sets> is diagonal with nonzero diagonal, so they are <linearly independent>. The <low-degree evaluation rank on a uniform layer> bounds the space of their restrictions by $\binom ns$. If $n-k<s\leq k$, the bound follows directly from $|\mathcal F|\leq\binom nk\leq\binom ns$.<On t-designs by Dijen K. Ray-Chaudhuri and Richard M. Wilson>[Theorem3, printed pages741–742]{ref}
All $s$-element subsets attain equality when $k=s$. The range restriction matters: all five singleton subsets of $[5]$ have only one intersection size, hence also at most five, but using the invalid choice $s=5>k=1$ would falsely bound five members by $\binom55=1$.
Back to article page
