Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 109 / 2

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.