Katona's intersection theorem

Fix a finite ground set $[n]$ of size $n$, and let $\mathcal{A}$ be a $t$-intersecting family of subsets of $[n]$ (TIntersecting): every two members $A, B \in \mathcal{A}$, allowing $A = B$, satisfy $|A \cap B| \ge t$. Suppose $1 \le t \le n$ and $n + t$ is even.

Then

where $M(n,t)$ (katonaBound) is the size of the family of all sets of size at least $(n+t)/2$ (a Hamming ball around the full set $[n]$), which is itself $t$-intersecting and attains this bound: any two sets of size at least $(n+t)/2$ meet in at least $(n+t)/2 + (n+t)/2 - n = t$ elements. The theorem therefore identifies the exact maximum size of a $t$-intersecting family.

The case $t = 1$ recovers the classical fact that an intersecting family (in the ordinary sense) has size at most $2^{n-1}$: for $n$ odd, $M(n,1)$ is exactly half of $2^n$, since the upper and lower halves of $\{0,\dots,n\}$ partition the binomial coefficients into two equal-sized sums by the symmetry $\binom{n}{i}=\binom{n}{n-i}$.

Formalization note. The proof compresses $\mathcal{A}$ toward a fixed element $z$ (via Katona.exists_compressed_TIntersecting) without changing its size or its $t$-intersecting property, then splits the compressed family by membership of $z$: the sets containing $z$, with $z$ removed, form a $(t-1)$-intersecting family, while full compression forces the sets avoiding $z$ to form a $(t+1)$-intersecting family. Both live on the $(n-1)$-element ground set obtained by deleting $z$; applying the bound recursively and combining via Pascal's identity $M(n-1,t-1)+M(n-1,t+1)=M(n,t)$ completes the induction on $n$, with $t=1$ and $t=n$ as base cases.