Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 10 (Combinatorics)

For an $r$-uniform set family $\mathcal{F}$, its lower shadow is the set family of all $(r-1)$-sets contained in a member. Write a positive integer $m$ in its unique binomial representationThe Kruskal-Katona theorem states thatFor $m=0$ the bound is zero. Equality is attained by the first $m$ $r$-sets in colexicographic order. In that order $A$ precedes $B$ when the largest element of their symmetric difference belongs to $B$.

Here is a complete UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-sized sets $U,V$, put $C(A)=(A\setminus V)\cup U$ when $A$ contains every element of $V$ and no element of $U$, and put $C(A)=A$ otherwise. The UV-compression of a set family replaces an eligible $A$ only if its image is absent. It preserves cardinality: a retained collision keeps both the original set and its already present image.

We first prove the required Shadow lemma for UV-compressions. Suppose that, for each $x\in U$, a $y\in V$ can be chosen so the set family is fixed by $C_{U\setminus \{x\},V\setminus \{y\}}$. We claimConsider a lower shadow member obtained by deleting $z$ from a moved set $A^{\prime }=(A\setminus V)\cup U$. If $z\notin U$, it is the compressed image of $A\setminus \{z\}$, an old lower shadow member. If $z=x\in U$, the smaller compression of $A$ produces $A^{\prime }\setminus \{x\}\cup \{y\}$, which is in $\mathcal{F}$ by the assumed invariance. Thus $A^{\prime }\setminus \{x\}$ already belongs to the old lower shadow; it is not eligible to move since it lacks $x$.

It remains to consider a lower shadow member $B$ from a retained original member $A=B\cup \{z\}$. If $B$ is not eligible to move, it stays in the compressed lower shadow. If it is eligible, let $B^{\prime }=(B\setminus V)\cup U$. When $z\notin U$, retaining the eligible $A$ means its image already belongs to $\mathcal{F}$, and that image contains $B^{\prime }$. When $z=x\in U$, the smaller compression of $A$ belongs to $\mathcal{F}$ and equals $B^{\prime }\cup \{y\}$. In either case $B^{\prime }$ is in the old lower shadow too. Consequently the collision rule retains $B$ as well. This proves the claimed containment in every case. Since compression preserves cardinality, it cannot increase lower shadow size.

If $\mathcal{F}$ is not a colexicographic initial segment, an earlier absent set $A$ and a later present set $B$ give $U=A\setminus B$, $V=B\setminus A$ with $\max U<\max V$, and a nontrivial UV-compression. Choose such a compression with $|U|$ smallest. If $|U|>1$, choose $y\in V\setminus \{\max V\}$. For every $x\in U$, the smaller compression still has its largest differing element on the $V$ side and must fix $\mathcal{F}$ by minimality. If $|U|=1$, the smaller compression is the identity. Thus the lower shadow argument applies.

Each nontrivial step strictly decreases the positive integer weightbecause the largest differing coordinate belongs to $V$. Iteration therefore terminates. A terminal set family is a colexicographic initial segment, since an earlier gap and a later member would otherwise provide another nontrivial compression. The final set family has $m$ members and no larger lower shadow.

To compute its lower shadow, take $a_r$ maximal with $\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)\le m$. All $r$-sets of $[a_r]$ occur first. The next block consists of sets containing $a_r+1$ whose remaining $(r-1)$-set runs through the initial segment of length $m-\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)$. By Pascal's identity, the remainder is smaller than $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$, so its next leading top index is strictly less than $a_r$. Repeating gives the stated unique binomial representation. The first block contributes all $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ $(r-1)$-sets in $[a_r]$ to the lower shadow. Deleting $a_r+1$ from the next block contributes only sets already counted; deleting another coordinate contributes $a_r+1$ joined to the lower shadow of the smaller initial segment. This recursive decomposition gives exactly the displayed sum. The base $r=1$ has lower shadow $\{\varnothing \}$ for every nonempty set family. This completes the proof and the sharpness assertion.

Now let $\mathcal{C}$ be the set family of vertex sets of the graph's cliques of order four. Its twice-iterated lower shadow consists of edges of the graph. If there were at least sixteen such copies, choose a sixteen-member subfamily. The relevant binomial representation isThe proved theorem gives at least $\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)=23$ triples in its first lower shadow. Apply it again to any twenty-three of those triples, using $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Their edge lower shadow has at leastmembers, contradicting the fifteen available edges. Conversely, the complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges and $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ copies of $K_4$. Therefore the maximum number of copies is exactly 15.

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.

An $r$-uniform hypergraph is strongly saturated with respect to a complete uniform hypergraph of order $r+t$ if adding any missing edge creates a new complete uniform hypergraph on $r+t$ vertices containing that edge. Equivalently, for every missing $r$-set $e$, there is an $(r+t)$-set $T\supseteq e$ for which all other $r$-subsets are edges. Existing complete subhypergraphs are allowed in this strong-saturation definition.

We prove the bound by an exterior-power quotient bound for strong hypergraph saturation. Assume $r,t\ge 1$ and $n\ge r+t$. Let $V={\mathbb{R}}^n$ with basis $e_1,\dots ,e_n$. Choose distinct real numbers $a_1,\dots ,a_n$ and let $U$ be the kernel of the $t\times n$ matrix whose column $i$ isEvery $t$ columns are linearly independent by the Vandermonde determinant, so $\dim U=n-t$. Form the quotient vector spaceFor each $r$-set $e=\{i_1<\cdots <i_r\}$, let $v_e$ be the image in $W$ of the exterior product $e_{i_1}\wedge \cdots \wedge e_{i_r}$. These images span $W$.

For an $(r+t)$-set $T$, let $V_T$ be its coordinate subspace. The matrix restricted to $T$ has rank $t$, so $U\cap V_T$ has dimension $r$. The wedge of a basis of this intersection is a nonzero vectorEvery coefficient $c_e$ is nonzero. Indeed, projection from $U\cap V_T$ onto the $r$ coordinates in $e$ is an isomorphism: a vector in its kernel would be supported on $T\setminus e$, where the $t$ columns are independent, and hence would be zero. That projection's determinant is precisely the corresponding wedge coefficient. Thus, in the quotient vector space,For a missing edge, choose its strong-saturation witness $T$. All other vectors in this relation come from present edges, so the missing edge's vector is in their span. Consequently the present-edge vectors already span all of $W$. Their number is at least its dimension:This is sharp. Take all $r$-sets that meet a fixed $t$-set $D$. A missing edge $e$ is disjoint from $D$, and on $e\cup D$ every other $r$-set meets $D$; adding $e$ completes the required clique. The number of edges is exactly the boxed difference. If $r\le n<r+t$, no missing edge could have a witness, so a strongly saturated hypergraph must be complete; the substantive construction above is for the usual range $n\ge r+t$.

For the set-pair problem, write $m=|I|$ and choose $x_i\in R_i\cap S_i$. If $i\ne j$, the cross-disjointness implies that $x_i$ is in neither $R_j$ nor $S_j$. In particular, the witnesses are distinct. Let $D=\{x_i:i\in I\}$; each $R_i$ and $S_i$ contains exactly its own witness from $D$.

Choose two different indices $i,j$. The sets $R_i\setminus \{x_i\}$ and $S_j\setminus \{x_j\}$ are disjoint, lie outside $D$, and have sizes $r-1$ and $s-1$. HenceFor equality, partition the ground set into disjoint sets $P,Q,D$ with sizes $r-1,s-1,n-r-s+2$, respectively, and enumerate $D$ as $x_1,\dots ,x_m$. SetThen $R_i\cap S_j$ is $\{x_i\}$ for $i=j$ and empty otherwise. This realizes equality whenever the bound permits $m\ge 2$. The argument is a diagonal-intersection set-pair bound, with no additional assumptions on intersections among the $R_i$ or among the $S_i$.

A set family shatters a set $Z$ when its traces on $Z$ include all of $\mathcal{P}(Z)$. The Sauer-Shelah lemma says that a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ which shatters no $k$-set satisfiesEquivalently, if $|\mathcal{F}|$ exceeds this sum, it shatters a $k$-set. Binomial coefficients with index greater than $n$ are zero; if $k>n$ the inequality reduces to the whole-power-set bound. The VC dimension formulation puts $k=d+1$.

We give the full inductive proof. Split $\mathcal{F}$ according to the last coordinate, deleting that coordinate from the present section, and write these two set families on $[n-1]$ as ${\mathcal{F}}_0,{\mathcal{F}}_1$. PutThe inclusion-exclusion principle gives $|\mathcal{F}|=|\mathcal{C}|+|\mathcal{D}|$. If $\mathcal{C}$ shattered a $k$-set, then $\mathcal{F}$ would shatter it too. If $\mathcal{D}$ shattered a $(k-1)$-set $Z$, both versions of each required trace, with and without the last coordinate, would occur in $\mathcal{F}$, which would shatter $Z\cup \{n\}$. Thus the two mathematical induction bounds apply:using Pascal's identity. For $n=0$ the set family has at most one member. For $k=1$, the intersection section must be empty, since any nonempty set family shatters the empty set. These supply the mathematical induction bases; the forbidden-empty-set case has an empty set family and an empty sum. Sharpness is attained by all subsets of size at most $k-1$, which cannot shatter a $k$-set.

Now fix $k\ge 1$ in the infinite-ground-set problem. Choose, using the hypothesis with $2k$, a set $Y$ of size $2k$ with at least $2^{2k-1}$ distinct traces. If its trace set family shattered no $k$-set, the Sauer-Shelah lemma would givea contradiction. Therefore some $Z\subseteq Y$ of size $k$ is shattered by the trace set family, and hence by $\mathcal{A}$ itself. Thus every finite shattering size occurs. The use of $2k$ makes the contradiction strict, even though the hypothesis only gives a half-power-set lower bound.

An infinite realization does not follow. For a concrete unbounded finite shattering without an infinite universal trace construction, partition $X=\mathbb{N}$ into disjoint finite blocksand takeEvery member is finite. Given $k$, choose $Y=B_k$; its trace set family is the full power set, so it has $2^k\ge 2^{k-1}$ members and is shattered. However, an infinite $Z$ cannot be contained in one finite block. Choose $x,y\in Z$ from different blocks. No member of $\mathcal{A}$ contains both, so $\{x,y\}$ is not a trace on $Z$. Consequently there need not be an infinite $Z$ whose traces contain every finite subset of $Z$.