Frankl-Wilson theorem

Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements, and suppose $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfies $|A\cap B|\mathrm{mod}p\in L$ for distinct members while $k\mathrm{mod}p\notin L$. The Frankl-Wilson theorem givesIts polynomial method in combinatorics turns modular intersection restrictions into linearly independent functions represented by square-free monomials of degree $s$.

For a prime number $p$, the vertices are $k$-subsets of $[N]$. An independent set avoids the only off-diagonal intersection congruent to $k$ modulo $p$, so the Frankl-Wilson theorem bounds its size by $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$. A clique has constant intersection $p-1$ and has size at most $N$, by the same theorem modulo a prime larger than $k$. This explicit graph gives an asymmetric Ramsey number lower bound and an exponential chromatic number lower bound.

If member sizes modulo a prime number $p$ avoid $L$ while distinct intersections lie in $L$, evaluation at characteristic vectors of sets gives a diagonal matrix with nonzero diagonal. After multilinear reduction on the Boolean cube, these polynomials remain linearly independent and have degree at most $|L|$. Counting square-free monomials proves $|\mathcal{F}|\le {\sum }_{j=0}^{|L|}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. On a fixed uniform layer, the low-degree evaluation rank on a uniform layer sharpens this to $\left(\genfrac{}{}{0ex}{}{n}{|L|}\right)$ when $|L|$ does not exceed the layer rank.

For a prime $p$, take rank-$2p$ subsets of $[4p]$ with no distinct pair meeting in $p$ points. Split by membership of coordinate one. In the containing part, remove that coordinate; in the avoiding part, first take complements and then remove it. Both transformed families have rank $2p-1$ on $4p-1$ points. Their distinct intersections avoid residue $p-1$ modulo $p$. The uniform Frankl-Wilson theorem bounds each by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$, yielding the displayed stronger form of the requested bound.

Fix a $(p+1)$-set $B\subseteq [4p]$. Take every $2p$-set $B\cup X$ with $X$ a $(p-1)$-subset of the remaining $3p-1$ points, together with the complements of all these sets. Within either half, intersections have size at least $p+1$. Across the halves they have size $|X\setminus Y|\le p-1$. Thus no intersection has size $p$, and the two disjoint halves give the displayed family size.

Let $m=p^a$ and let an $r$-uniform set family have no distinct pair whose intersection is congruent to $r$ modulo $m$. Its size is bounded as displayed; the customary nontrivial form $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)$ requires $m-1\le r$. The Lucas theorem makes $\left(\genfrac{}{}{0ex}{}{z-r+m-1}{m-1}\right)$ a residue detector modulo $p$, equal to one exactly when $z\equiv r(\mathrm{mod}m)$. Its Boolean evaluation functions have degree at most $m-1$ and a diagonal evaluation matrix on the family. The low-degree evaluation rank on a uniform layer supplies the sharp dimension bound. Without the size qualification, three singletons with $n=3,r=1,m=4$ contradict the customary printed form, since $3>\left(\genfrac{}{}{0ex}{}{3}{3}\right)$.

In the polynomial method in combinatorics, a set family of sets with common size residue $r$ modulo a prime number $p$ annihilates the displayed auxiliary functions. After multilinear reduction on the Boolean cube, functions with $|S|\le s-1$ have degree at most $s$. If $r$ avoids every $j=0,\dots ,s-1$ modulo $p$, these functions are linearly independent: evaluation at a set $T$ gives $(|T|-r){\sum }_{S\subseteq T}{c}_S$, and increasing $|T|$ eliminates coefficients. Combining them with diagonal intersection polynomials removes the lower-degree monomial count and strengthens the dimension bound from ${\sum }_{j\le s}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ to $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

Let $p$ be a prime number, $0\le a<p$, $1\le s<p$, and $n\ge a+s$. A multilinear polynomial over ${\mathbb{F}}_p$ of degree less than $s$ that vanishes on every Boolean vertex whose weight is not congruent to $a$ modulo $p$ vanishes everywhere. Alternating sums over intervals of $s$ free coordinates eliminate the possible nonzero weight levels one at a time. This proves independence of the auxiliary functions used for the uniform Frankl-Wilson theorem bound.

Let $p$ be a prime number and $L\subseteq {\mathbb{F}}_p$ have $s$ elements. A set family whose member sizes modulo $p$ avoid $L$, and whose distinct pairwise intersection sizes modulo $p$ belong to $L$, has at most ${\sum }_{j=0}^{\min (s,n)}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ members. The intersection polynomials ${\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ have a diagonal, nonzero evaluation matrix on the family's characteristic vectors of sets. Multilinear reduction on the Boolean cube places these linearly independent functions in the space spanned by square-free monomials of degree at most $s$.

If a $k$-uniform set family on an $n$-element ground set has at most $s$ possible intersection sizes between distinct members, then its size is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The proof uses the linear independence of incidence polynomials on the $k$-slice.