Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 12 / 3 / Solution

For $1\le t\le r\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient is taken as zero if its lower argument is outside its usual range.

First reduce to left-compressed set families. One of the coordinate shifts of a set family, $C_{ij}$ with $i<j$, replaces $j$ by $i$ only when the target set is absent. It preserves cardinality and the property of being t-intersecting. To verify the latter, a pair of newly moved sets has the same intersection size as its old pair. If just one member moves and its intersection with a retained member decreases, the retained member contains $j$ and avoids $i$. Its own shifted partner must already have belonged to the old family, otherwise it would have moved too. The old moved member and that shifted partner have the same intersection size as the allegedly bad new pair, a contradiction. Repeating changing shifts terminates because the sum of all point labels strictly decreases.

A generating family for a uniform set family is a collection $\mathcal{G}$ of sets of size at most $r$ such thatUse the following small-support generating lemma for extremal intersecting families, the auxiliary result permitted here. If $n>2r-t$, $j\ge 0$, andthen every maximum-cardinality left-compressed set family that is t-intersecting has a generating family contained in $\mathcal{P}([t+2j])$. Reflection gives the corresponding right-end supporting interval for a right-compressed optimum. The inequality is strict.

The main ideas of the generating lemma are as follows. When $n=2r-t+1$, its hypothesis forces $t+2j\ge n$, making the support conclusion automatic. Otherwise $n\ge 2r-t+2$. Choose inclusion-minimal compressed generators minimizing their furthest point $q$. Partition generators containing $q$ by size. A pair whose intersection would fall below $t$ on deleting $q$ must fill $[q]$ and have sizes summing to $q+t$. Compare the two replacements associated to those complementary size classes; counting their rank-$r$ extensions makes one replacement larger unless the sizes are equal. In that balanced case, put $q=t+2j+\delta$, where $\delta \ge 2$ is even. Delete $q$ from generators avoiding a suitably chosen earlier point. Averaging supplies a proportion at least $(q-t)/(2(q-1))$. The ratio of the guaranteed gain to the loss isIt exceeds one precisely when $n>(r-t+1)(2+(t-1)/(j+\delta /2))$, implied by the stated hypothesis. This contradicts maximal cardinality; redundant generators are removed after each replacement. These extension counts explain both the support bound and its strict threshold.

We also need the compatibility bound for complementary generating families, which has a short direct proof. Write $\overline{\mathcal{F}}=\{[n]\setminus A:A\in \mathcal{F}\}$. If $G$ generates $\mathcal{F}$ and $H$ generates $\overline{\mathcal{F}}$, thenOtherwise contain their union in a set $T$ of size $n-r+t-1$. Under $n>2r-t$ this size is at least both $r$ and $n-r$. Extend $G,H$ inside $T$ to sets $A,B$ of those respective sizes. Then $A,B^c\in \mathcal{F}$, whereas $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

The easy parameter ranges can now be disposed of. If $n\le 2r-t$, every two $r$-sets intersect in at least $t$ points, and $M(n,r,t)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. This is a candidate value too: choose $i=n-r$, for which the minimum possible intersection with $[t+2i]$ is exactly $t+i$. If $t=1$ and $n\ge 2r$, Question 1 gives $M(n,r,1)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=|{\mathcal{A}}_0|$. If $n=2r-t+1$, complementation of uniform intersecting families turns the problem into an intersecting family of rank $n-r=r-t+1$, on a ground set of size at least twice that rank. Question 1 then giveswith equality from that candidate, the family of all $r$-sets avoiding the last point.

It remains to treat $t>1$ and $n>2r-t+1$. Put $R=r-t+1$ andSince $N_R=2r-t+1$, there is $0\le k\le R-1$ with $N_{k+1}\le n<N_k$. Take a maximum left-compressed set family $\mathcal{F}$. Its complement family is right-compressed and has parametersIt is maximum for those parameters, since complementation is a cardinality-preserving bijection between the two intersection problems. Put $\ell =r-t-k=R-1-k$. The strict inequality $n<N_k$ impliesFor $k>0$, multiplying out reduces this to $nk<R(2k+t-1)$, exactly $n<N_k$; for $k=0$ it reduces to $t>1$. The reflected generating lemma therefore gives generators $\mathcal{H}$ for $\overline{\mathcal{F}}$ supported on

First suppose $N_{k+1}<n<N_k$. The original generating lemma supplies generators $\mathcal{G}$ supported on $X=[t+2k]$. If every $G\in \mathcal{G}$ has size at least $t+k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. The same conclusion follows if every $H\in \mathcal{H}$ has size at least $n-r-k$: every complement member then has at least that many points in $Y$, forcing each original member to have at least $t+k$ points in $X$. If neither condition holds, choose $|G|\le t+k-1$ and $|H|\le n-r-k-1$. Thencontradicting the proved compatibility bound. Thus $M(n,r,t)\le |{\mathcal{A}}_k|$, and the candidate itself attains equality.

Now suppose $n=N_{k+1}$. The earlier exceptional case excludes $k=R-1$. Since $t>1$, $n>N_{k+2}$, so the original generating lemma gives $\mathcal{G}$ supported on $[t+2k+2]$, while the same dual argument still gives $\mathcal{H}$ supported on $Y=[t+2k+1,n]$. If all $G$ have size at least $t+k+1$, then $\mathcal{F}\subseteq {\mathcal{A}}_{k+1}$. If all $H$ have size at least $n-r-k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. Otherwise a pair with $|G|\le t+k$ and $|H|\le n-r-k-1$ violates compatibility. HenceBoth candidates are available, so this proves the maximum formula also at the boundaries.

For completeness, their equality and the maximizing intervals follow from a direct count, with no appeal to the theorem. Moving from ${\mathcal{A}}_i$ to ${\mathcal{A}}_{i+1}$ adds sets containing both new coordinates and exactly $t+i-1$ old block points, and loses sets containing neither new coordinate and exactly $t+i$ old block points. ThusIn the nontrivial range, the gain-to-loss ratio is $\frac{(t+i)(r-t-i)}{(i+1)(n-r-i-1)}$. It exceeds, equals or falls below one according as $n$ is below, equal to or above $N_{i+1}$. Since the thresholds decrease with $i$ when $t>1$, the largest candidate is ${\mathcal{A}}_k$ in each strict interval and the consecutive candidates tie at $n=N_{k+1}$. This completes the proof of the cardinality theorem in every parameter range.