Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 10 / 2 / Solution

Take the natural parameter range $1\le t\le r\le n$ and admissible indices $0\le i\le r-t$. Larger indices give empty set families. Write $q=r-t+1$ and set $n_0=\infty$ when discussing the first interval. For the nontrivial interval calculation, $t>1$ and $n>2r-t+1$; all prefixes used below then lie inside the ground set.

To compare consecutive complete-intersection candidate families, put $a=t+2i$ and $b=t+i$. A set in ${\mathcal{A}}_{i+1}\setminus {\mathcal{A}}_i$ has exactly $b-1$ points in $[a]$ and both of the next two points. A set in ${\mathcal{A}}_i\setminus {\mathcal{A}}_{i+1}$ has exactly $b$ points in $[a]$ and neither next point. ThereforeFor $0\le i<r-t$ these quantities are positive in the present range, and cancellation of binomial coefficients givesThe numerator minus the denominator isThus $|{\mathcal{A}}_{i+1}|$ is larger, equal or smaller than $|{\mathcal{A}}_i|$ according as $n$ is smaller, equal or larger than $n_{i+1}$. Since these thresholds decrease with the index, $n_{k+1}<n<n_k$ implies strict increase up to ${\mathcal{A}}_k$ and strict decrease thereafter:At an interior boundary $n=n_{k+1}$, the two consecutive maxima tie. The interval assertion concerns admissible $k$; taking $k>r-t$ would instead refer to an empty set family and is not a valid interpretation.

The Ahlswede-Khachatrian theorem, in its cardinality form, statesHere ${\mathcal{A}}_i$ is interpreted exactly by its intersection with $[t+2i]$, even if that prefix extends beyond $[n]$. Its size can always be written with $m_i=\min \{n,t+2i\}$ aswhere impossible binomial coefficients are zero. When $n\le 2r-t$, the whole level is $t$-intersecting and the formula gives $M=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The nontrivial case has $n>2r-t$.

First, each candidate is a t-intersecting family: two members contain at least $2(t+i)-(t+2i)=t$ common points in the prefix. This proves the lower bound for $M$. We now prove the upper bound, using only the compression and generating-family facts expressly allowed in the question.

The first auxiliary fact is that the usual left coordinate shifts of a set family preserve cardinality and $t$-intersection. Iterating them produces a left-compressed set family of the same size. The shift $S_{ab}$ with $a<b$ replaces $b$ by $a$ only when $b$ is present, $a$ is absent, and the replacement is not already in the set family. A set family is left-compressed when it is fixed by every such shift. Right compression is the reflected notion.

For the second auxiliary fact, a generating family for a uniform set family $\mathcal{G}$ means a collection of sets of size at most $r$ withThe permitted small-support generating lemma for extremal intersecting families is this precise statement: if $\mathcal{F}$ is a maximum-cardinality left-compressed $t$-intersecting set family, $n>2r-t$, andthen it has a generating set family supported on $[t+2j]$. Reflection gives the same assertion for a right-compressed extremal set family, with the supporting interval at the right end. These two auxiliary results are being used as permitted lemmas; the extremal conclusion of the theorem is established in the remaining argument.

Choose a maximum left-compressed set family $\mathcal{F}$. Its complement set familyis right-compressed, has uniformity $r^{\prime }=n-r$ and intersection parameter $t^{\prime }=n-2r+t$, and is extremal for those parameters. Indeedso complementation gives a cardinality-preserving bijection between the two classes of intersecting set families. Notice that $r^{\prime }-t^{\prime }+1=q$ too.

We need a compatibility observation, which we prove. If $G$ generates $\mathcal{F}$ and $H$ generates ${\mathcal{F}}^{\ast }$, thenOtherwise extend $G\cup H$ to a set $T$ of size $n-r+t-1$. This size is at least both $r$ and $n-r$ because $n\ge 2r-t+1$ and $t\ge 1$. Choose an $r$-set $A\subseteq T$ containing $G$, and an $(n-r)$-set $B\subseteq T$ containing $H$. Their generating properties imply $A,[n]\setminus B\in \mathcal{F}$, buta contradiction. This compatibility bound for complementary generating families is the link between the two compression directions.

Suppose first that $t>1$ and $n>2r-t+1$ lies strictly between $n_{k+1}$ and $n_k$. Put $m=t+2k$ and $h=r-t-k$. The small-support lemma gives generators $\mathcal{G}$ for $\mathcal{F}$ supported on $[m]$. It also gives generators $\mathcal{H}$ for ${\mathcal{F}}^{\ast }$ supported on $[m+1,n]$. For completeness, the dual inequality required here isWriting $D=n-2q$, it is equivalent to $kD<q(t-1)$, exactly the upper interval inequality $n<n_k$; for $k=0$ it follows from $t>1$. The dual support length is $t^{\prime }+2h=n-m$.

Either every $G\in \mathcal{G}$ has $|G|\ge t+k$, or every $H\in \mathcal{H}$ has $|H|\ge n-r-k$. If neither assertion held, a pair of smaller generators would have union size at mostcontradicting the compatibility bound. In the first alternative, every member of $\mathcal{F}$ has at least $t+k$ points in $[m]$, so $\mathcal{F}\subseteq {\mathcal{A}}_k$. In the second alternative, each complement has at least $n-r-k$ points in $[m+1,n]$, leaving its original set with at most $r-t-k$ points there; again $\mathcal{F}\subseteq {\mathcal{A}}_k$. Therefore $M\le |{\mathcal{A}}_k|$, proving the theorem in every strict interval.

At an interior boundary $n=n_{k+1}$, with $0\le k\le r-t-1$, apply the small-support lemma at index $k+1$ to the original set family, since $n>n_{k+2}$. Its generators are supported on $[t+2k+2]$. The dual generators are still supported on $[t+2k+1,n]$, by the same dual calculation with $h=r-t-k$. Either all original generators have size at least $t+k+1$, or all dual generators have size at least $n-r-k$: failure of both would give union size at most $n-r+t-1$, again impossible. The first alternative places $\mathcal{F}$ inside ${\mathcal{A}}_{k+1}$, and the second places it inside ${\mathcal{A}}_k$. The comparison already proved gives $|{\mathcal{A}}_k|=|{\mathcal{A}}_{k+1}|$, so the common size is $M$.

It remains to cover the endpoint cases, not to assume them implicitly. For $t=1$ and $n>2r$, the small-support lemma with $j=0$ puts an extremal left-compressed set family's generators inside $\{1\}$. Its members must all contain one, giving $M\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, attained by ${\mathcal{A}}_0$. For $t=1$, $n=2r$, at most one member of each complementary pair can occur, so $M\le \frac{1}{2}\left(\genfrac{}{}{0ex}{}{2r}{r}\right)=\left(\genfrac{}{}{0ex}{}{2r-1}{r-1}\right)$, again attained by ${\mathcal{A}}_0$. If $n<2r$, the whole level is intersecting.

For $t>1$ and $n=2r-t+1$, complementation changes the problem into a one-intersection problem with uniformity $q=r-t+1$. Since $n=2q+t-1>2q$, the preceding case givesattained by ${\mathcal{A}}_{r-t}$, the set family of $r$-sets avoiding the final point. For $n\le 2r-t$, every two $r$-sets meet in at least $2r-n\ge t$, so $M=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ and ${\mathcal{A}}_{r-t}$ is the whole level. Finally, $t=r$ gives $M=1$ directly. These cases, the strict intervals and their boundaries cover all $1\le t\le r\le n$, completing the proof of the stated maximum formula.