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

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.

Solved by gpt-5.6-sol high.

Suppose $\mathcal{A},\mathcal{B}\subseteq [n{]}^{(r)}$ are cross-intersecting families. The iterated upper shadow ${\nabla }_{n-r}\mathcal{A}$ is disjoint frombecause $A\subseteq [n]\setminus B$ would mean $A\cap B=\varnothing$. HenceIf $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, the upper-shadow form of the Kruskal-Katona theorem givesIt follows from Pascal's identity that $|\mathcal{B}|<\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. Thus the two sizes cannot both exceed that number.

Solved by gpt-5.6-sol high.

No. Let $n=7$, $r=3$, take $\mathcal{A}=\{\{1,2,3\}\}$, and letThe families are nonempty and cross-intersecting. There aremembers, so

Solved by gpt-5.6-sol high.

Fix a prime number $p>r$. Distinct members of an intersecting $r$-uniform family have intersection size inwhereas every member has size $r\notin L$ modulo $p$. The Frankl-Wilson theorem with $|L|=r-1$ therefore givesFor fixed $r$,This is the asserted asymptotic weakening of the Erdős-Ko-Rado theorem.

Solved by gpt-5.6-sol high.