Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 12 (Combinatorics)

For a nonempty $r$-uniform set family $\mathcal{F}$, write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, $A$ precedes $B$ exactly when the largest point of $A△B$ belongs to $B$. The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than $\left(\genfrac{}{}{0ex}{}{a_j}{j-1}\right)$, forcing the next top argument below $a_j$. This also proves uniqueness.

Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets $U,V$ of equal size, let $C_{U,V}$ replace a member $A$ containing $V$ and avoiding $U$ by $A^{\prime }=(A\setminus V)\cup U$ only when $A^{\prime }$ is absent. Other members stay. This UV-compression preserves cardinality. Allow only $\max U<\max V$, and at each step choose a changing compression with $|U|=|V|$ as small as possible. Every smaller allowed UV-compression then fixes the current family.

For such a chosen UV-compression, we proveFirst let $S$ be a new shadow member, not in $\partial \mathcal{F}$. It has the form $A^{\prime }\setminus \{x\}$ for a moved member $A$. If $x\in U$, choose $y\in V$ with $y\ne \max V$ when $|V|>1$. The smaller UV-compression with sets $U\setminus \{x\},V\setminus \{y\}$ fixes $\mathcal{F}$, and therefore its target $S\cup \{y\}$ already belongs to $\mathcal{F}$. This would put $S$ in the old shadow, a contradiction. For $|V|=1$ the same target is simply $A$, giving the same contradiction without a compression. Hence $x\notin U$. Now $A\setminus \{x\}$ is an old shadow member whose compression target is $S$; since $S$ was absent, it appears in the compressed shadow.

It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for $S$ containing $V$, avoiding $U$, with $S^{\prime }=(S\setminus V)\cup U$ absent from the old shadow. A witness $B=S\cup \{x\}$ in the compressed family must be a retained old member, since newly moved members avoid $V$. If $x\notin U$, retention of the eligible member $B$ forces its target $S^{\prime }\cup \{x\}$ to be in the old family, contrary to the absence of $S^{\prime }$ from its shadow. If $x\in U$, the smaller fixed compression just used forces $S^{\prime }\cup \{y\}$ into the old family; for $|U|=1$ this is $B$ itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.

Each change strictly decreases the integer potential ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}{2}^a$. The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set $X$ and a present later set $Y$. The choice $U=X\setminus Y,V=Y\setminus X$ is an allowed changing compression. Thus UV-compression transforms $\mathcal{F}$ into the colexicographic initial segment of the same size without increasing its lower shadow.

Finally compute that shadow. The first block comprises all $r$-subsets of $[a_r]$ and contributes $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ shadow members. The next block has maximum point $a_r+1$ and its remaining $(r-1)$ points form a smaller colexicographic initial segment. Shadow members omitting $a_r+1$ are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.

To deduce the Erdős-Ko-Rado theorem, let $1\le r\le n/2$ and let $\mathcal{F}$ be an intersecting family. Put $k=n-r$ and take the complement family $\mathcal{B}=\{[n]\setminus A:A\in \mathcal{F}\}$. Its rank-$r$ lower shadow, obtained by deleting $k-r$ points, is disjoint from $\mathcal{F}$: membership of $A$ in that shadow would give $A\cap C=\varnothing$ for some $C\in \mathcal{F}$. If $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every $k$-set of $[n-1]$ and a further $k$-set containing $n$. Its rank-$r$ shadow therefore contains every $r$-set of $[n-1]$ and at least one more $r$-set containing $n$. This applies also when $k=r$, with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus $\boxed{|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)}$, attained by all $r$-sets containing a fixed point.

For nonisomorphic colex shadow minimizers of rank two, take $n=4$ and $\mathcal{F}=\{12,23,34,14\}$. Its shadow has four singletons, as does the initial four-set colex segment $\mathcal{I}=\{12,13,23,14\}$. The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees $3,2,2,1$, so no permutation makes them isomorphic.

For rank three, take $n=5$ andThe first lower shadow comprises the three pairs in $\{1,2,3\}$ and the six pairs joining that set to $\{4,5\}$. The second shadow comprises every pair on $[5]$ except $45$. Both therefore have size nine. Their point-degree multisets are respectively $\{4,4,4,3,3\}$ and $\{5,4,4,3,2\}$, so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.

There is a genuine qualification missing from the printed bound. With $n=3,r=1,m=4$, the family of three singletons has distinct intersections of size zero, which is not congruent to $r$ modulo $m$. Nevertheless its size is three, whereas $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)=\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when $m-1\le r$.

Put $m=p^a$ with $p$ a prime number, and $d=m-1$. If $r<d$, the corrected bound is simply the total number $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ of $r$-sets. Assume henceforth $d\le r$. For an integer $z$, consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base-$p$ digit of $d$ equals $p-1$ show that $f(z)$ is one when $z\equiv r(\mathrm{mod}m)$ and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of $u^d$ in $(1+u{)}^q$ is periodic in the integer exponent $q$ modulo $m$: in characteristic $p$, $(1+u{)}^m=1+u^m$, so multiplying even a formal power series by $(1+u{)}^m$ does not change coefficients of degrees below $m$. Reduce any exponent modulo $m$ to obtain the stated detector.

For each $A\in \mathcal{F}$, apply that detector to $|A\cap B|$. Its evaluations on $B\in \mathcal{F}$ form the identity matrix, since the diagonal intersection is $r$ and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of $B$: summing by $j=|S|$ gives ${\sum }_j\left(\genfrac{}{}{0ex}{}{|A\cap B|}{j}\right)\left(\genfrac{}{}{0ex}{}{d-r}{d-j}\right)=\left(\genfrac{}{}{0ex}{}{|A\cap B|+d-r}{d}\right)$ by the coefficient identity for $(1+u{)}^{|A\cap B|}(1+u{)}^{d-r}$.

Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic $p$. Let $M$ be the integer incidence matrix whose rows are subsets $S$ of size at most $d$, whose columns are all $r$-sets $B$, and whose entries are $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j\le d$ its row satisfiesThus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. Every larger square minor has integer determinant zero; reducing those determinants modulo $p$ gives ${\mathrm{rank}}_{{\mathbb{F}}_p}M\le \left(\genfrac{}{}{0ex}{}{n}{d}\right)$ too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix $(f_A(1_B){)}_{A,B\in \mathcal{F}}$ factors through these incidence rows, so its rank $|\mathcal{F}|$ is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. This proves the qualified bound.

Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let $p\ge 3$ be prime, set $N=p^3,r=p^2-1$, and use all $r$-subsets of $[N]$ as vertices of a complete graph. Color a pair red when its intersection size is $-1$ modulo $p$, and blue otherwise. A blue clique has size at most $D=\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ by the proved bound with modulus $p$. In a red clique, all distinct intersections belong toFor each vertex $A$ of that clique, the polynomial $P_A(x)={\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers $x_i^j$ by $x_i$ on Boolean vectors. Its degree is at most $p-1$, so the rational version of the same incidence-rank argument bounds a red clique by $D$ as well. Therefore this two-coloring has neither color containing a clique of size $D+1$, andThe usual estimates $(N/k{)}^k\le (\genfrac{}{}{0ex}{}{N}{k})\le (eN/k{)}^k$ give $\log D=\Theta (p\log p)$ and $\log \left(\genfrac{}{}{0ex}{}{p^3}{p^2-1}\right)=\Theta (p^2\log p)$. Thus along this explicit sequence the diagonal Ramsey number exceeds $\exp (c(\log s{)}^2/\log \log s)$ for some absolute $c>0$. This is substantially larger than any fixed power of $s$.

Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let $N=4p-1,r=2p-1$, and join two $r$-subsets exactly when their intersection has size $p-1$. An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes $0,\dots ,2p-2$, the only one congruent to $r$ modulo $p$ is $p-1$. Hence every independent set has size at most $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$. Embed each vertex as $v_A=1_A/\sqrt{2p}$ in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio $N(\log 2-h(1/4))+o(N)$, where $h(x)=-x\log x-(1-x)\log (1-x)$. Since $\log 2-h(1/4)>0$, this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.

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.

View a set family as a set of vertices of the Boolean lattice. The operation $D_i$ acts independently on each pair $\{S,S\cup \{i\}\}$, where $i\notin S$: it keeps a full or empty pair and moves a sole upper member down. Thus downward coordinate compression preserves cardinality.

Fix a tracing set $Y$. If $i\notin Y$, compression leaves the trace of a set family on $Y$ unchanged. If $i\in Y$, write $B_0,B_1\subseteq \mathcal{P}(Y\setminus \{i\})$ for the two sections of the old trace, according to absence or presence of $i$. The absent-$i$ section of the new trace is $B_0\cup B_1$. Its present-$i$ section is contained in $B_0\cap B_1$: an upper member survives only when its lower partner was also present in the original family. ConsequentlyIn particular, downward coordinate compression cannot create new set shattering.

Repeatedly apply any changing downward coordinate compression. Each change strictly decreases ${\sum }_{A\in \mathcal{F}}|A|$, so the process terminates at a down-set $\mathcal{D}$ with the same cardinality and with no larger trace on any $Y$. The Sauer-Shelah lemma says that a family shattering no $k$-element set satisfiesIndeed, the compressed down-set also shatters no $k$-element set. If it contained any member of size at least $k$, all subsets of a $k$-subset of that member would belong to the down-set, contradicting this restriction. Every member therefore has size at most $k-1$, giving the bound. Equivalently, VC dimension at most $d$ gives size at most ${\sum }_{j=0}^d\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The family of all sets of size at most $d$ attains this bound.

There is a different extremal example when $n\ge 3$. Toggle a fixed coordinate in the family of sets of size at most two:The symmetric difference is a bijection, so this family has $1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. On each tracing set $Y$, it simply toggles coordinate $1$ if $1\in Y$; thus it preserves trace cardinality and set shattering. A triple has seven trace patterns, not eight. The new family differs from the original one because it contains $\{1,2,3\}$. For $n\le 2$ the specified cardinality is $2^n$, so the entire power set is the unique family of that size; the different example requires $n\ge 3$.

For the final bound, let $e_i(\mathcal{F})$ count pairs $S,S\cup \{i\}$ both in the family. Deleting coordinate $i$ identifies precisely these pairs, soSuppose every deletion lost at least two members, so $e_i(\mathcal{F})\ge 2$ for every $i$. The trace inequality and preservation of cardinality show that $e_i(\mathcal{D})\ge e_i(\mathcal{F})$ after downward coordinate compression. The down-set $\mathcal{D}$ contains the empty set and every singleton. For each $i$, its second edge in direction $i$ has an upper endpoint of size at least two. Downward closure then supplies a pair $\{i,j\}\in \mathcal{D}$. The pairs in $\mathcal{D}$ therefore cover all $n$ coordinates, so at least $\lceil n/2\rceil$ pairs are needed. This proves two cube edges in every direction force many vertices:Taking the contrapositive gives the required answer:The threshold is sharp for every $n\ge 2$. Take the empty set, all singletons and $\lceil n/2\rceil$ pairs covering every coordinate. For even $n$, use the disjoint pairs $12,34,\dots ,(n-1)n$; for odd $n$, pair the first $n-1$ coordinates and add $(n-1)n$. This down-set has exactly $\lceil 3n/2\rceil +1$ members and at least two edges in every direction, so every $(n-1)$-coordinate trace has size at most $|\mathcal{F}|-2$. Adding further members preserves those pairs and therefore preserves the failure whenever a larger cardinality is feasible. For $n=1$, the putative counterexample cardinality is three, exceeding the size of the Boolean lattice; the sharpness construction naturally starts at $n=2$.