Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 11 (Combinatorics)

The LYM inequality. For an antichain $\mathcal{F}$ in the Boolean lattice,To prove this by double counting, generate a maximal chain in a Boolean lattice from a permutation $\pi$ of $[n]$: its members are the first $j$ entries of $\pi$, for $0\le j\le n$. A particular $j$-set belongs to exactly $j!(n-j)!$ of the $n!$ resulting maximal chains in a Boolean lattice. Each such maximal chain in a Boolean lattice meets the antichain at most once. Counting pairs consisting of a member of $\mathcal{F}$ and a permutation whose associated maximal chain in a Boolean lattice contains it givesDivision by $n!$ proves the LYM inequality, including the empty antichain and the levels containing $\varnothing$ or $[n]$.

A symmetric chain decomposition of a Boolean lattice. A symmetric chain has one set at every size from $k$ to $n-k$, with consecutive members related by inclusion. Start with the single symmetric chain containing $\varnothing$ when $n=0$. Given a symmetric chainin a symmetric chain decomposition of a Boolean lattice on $[n]$, let $x=n+1$ and replace its two copies in the larger Boolean lattice byand, when it is nonempty, byThe endpoint sizes of the first symmetric chain sum to $n+1$; those of the second symmetric chain also sum to $n+1$. These symmetric chains partition the original symmetric chain together with its copy containing $x$. Thus this construction inductively partitions the entire Boolean lattice into symmetric chains. Each symmetric chain contains exactly one set of size $\lfloor n/2\rfloor$, so the number of symmetric chains is

The proposed sum bound for cross-intersecting families is false. Take $n=3$ andBoth are antichains, and any member of one meets any member of the other. Nevertheless,The hypothesis permits the two antichains to coincide. Even if distinct antichains were wanted, taking $\mathcal{B}=\{\{1,2\},\{1,3\}\}$ gives $5>3$.

The Kruskal-Katona theorem. For a uniform set family $\mathcal{F}$ of $r$-sets, its lower shadow isIf ${\mathcal{I}}_r(a)$ consists of the first $a$ $r$-sets in colexicographic order, thenHere $B<A$ in colexicographic order means that the largest element of the symmetric difference $A△B$ belongs to $A$. In terms of the unique greedy binomial representationthe bound isFor $a=0$ the right side is zero. We prove both the minimizing assertion and this formula.

First, the lower shadow of a colexicographic initial segment is a colexicographic initial segment. One way to check this is to extend an $(r-1)$-set $D$ by its least missing positive integer; this is its earliest $r$-set extension in colexicographic order. If $E<D$, the earliest extension of $E$ is no later than the earliest extension of $D$. To see the latter assertion, let $j=\max (D△E)\in D$. If $E$ misses an integer below $j$, its least missing integer is below $j$, so its earliest extension is still earlier than the earliest extension of $D$. Otherwise $E$ contains every integer below $j$. Above $j$ the two sets agree, and their equal sizes force $D$ to contain $j$ and all but one integer below $j$. Adding that missing integer to $D$, or adding $j$ to $E$, gives the same earliest extension. Thus every set earlier than a member of the lower shadow is also in that lower shadow.

We now prove the minimizing assertion by induction on the size $N$ of a finite ground set. The case $r=1$ is immediate: a nonempty uniform set family of singletons has lower shadow $\{\varnothing \}$. The empty case and $r=N$ are also immediate. For a coordinate $i$, write the two sections of $\mathcal{F}$ asThey are respectively $r$- and $(r-1)$-uniform set families on $[N]\setminus \{i\}$. Perform a colexicographic section compression: replace each section by the colexicographic initial segment of the same size. The two sections of the lower shadow before this operation areBy the inductive hypothesis the individual lower shadows do not grow. After colexicographic section compression, both families in the displayed union are colexicographic initial segments, so their union has the larger of their two sizes. This is no greater than the original union. Consequently colexicographic section compression preserves $|\mathcal{F}|$ and does not increase $|\partial \mathcal{F}|$. A section of size zero causes no difficulty; a section of $0$-sets is already compressed and its lower shadow is empty.

Repeat any colexicographic section compression that changes the family. The sum of the positions of its members in colexicographic order strictly decreases, since restriction to either fixed-coordinate section preserves that order. Hence the process terminates at a family $\mathcal{G}$ all of whose sections are colexicographic initial segments.

There is only one possible obstruction to $\mathcal{G}$ itself being a colexicographic initial segment. Suppose $B<A$, $A\in \mathcal{G}$ and $B\notin \mathcal{G}$. No coordinate can belong to both $A,B$, or to neither: either possibility would contradict the compressed section at that coordinate. Thus $A,B$ partition $[N]$, and $N=2r$. Moreover, every such inversion must use this same complementary pair: any omitted set below $A$ equals $A^c=B$, and any included set above $B$ equals $B^c=A$. These observations also rule out an inversion completely before or after this pair. A set strictly between $B$ and $A$ would have to be both present, by comparison with $A$, and absent, by comparison with $B$. Therefore $B,A$ are consecutive in colexicographic order. Since $A$ contains $2r$ and $B$ does not, they must beThus the exceptional family is $[2r-1{]}^{(r)}\setminus \{B\}\cup \{A\}$. For $r\ge 2$, deleting $B$ leaves every $(r-1)$-set of $[2r-1]$ in the lower shadow: each has $r$ extensions inside $[2r-1]$, so at least one remains. Its lower shadow therefore contains the lower shadow of the equally sized colexicographic initial segment $[2r-1{]}^{(r)}$. The case $r=1$ was already handled. This proves the minimizing assertion in all cases.

Finally the greedy binomial representation describes the successive blocks of a colexicographic initial segment. Its first block is $[k_r{]}^{(r)}$, and the remaining sets are obtained by adding $k_r+1$ to an initial segment of $(r-1)$-sets inside $[k_r]$. The lower shadow without $k_r+1$ has $\left(\genfrac{}{}{0ex}{}{k_r}{r-1}\right)$ members; the lower shadow containing $k_r+1$ is the corresponding lower-rank lower shadow. Repeating this decomposition proves the displayed binomial coefficient formula and completes the Kruskal-Katona theorem proof.

The specified initial segment covers every $r$-set of $[m]$. Assume $m\ge r+1$ and $r\ge 1$, the nontrivial range. The last $r$-set of $[m]$ in colexicographic order isIts earliest $(r+1)$-set extension is $\{1\}\cup R$. Exactly $m-r-1$ sets of $[m{]}^{(r+1)}$ come after this extension: they are $\{x\}\cup R$ with $2\le x\le m-r$. Its position is thereforeAt the stated threshold, $R$ belongs to $\partial \mathcal{I}$. Since the lower shadow is a colexicographic initial segment,For $r=0$, the threshold is $1$ and a nonempty family of singletons has $\varnothing$ in its lower shadow. If $m=r\ge 1$, the threshold is again $1$; the first $(r+1)$-set is $[r+1]$, which contains $[r{]}^{(r)}$. If $m<r$, the desired inclusion is empty and automatic.

The nonuniform bound. Suppose first that $1\le r\le m$ and, contrapositively, that $|\mathcal{B}|\le \left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$. Let $\mathcal{J}$ be the colexicographic initial segment of $r$-sets of size $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$; this consists of $[m{]}^{(r)}$ with its last member $R$ removed. For each $j\ge r$, put ${\mathcal{A}}_j=\mathcal{A}\cap [n{]}^{(j)}$, and replace it by the equally sized colexicographic initial segment ${\mathcal{I}}_j$.

Iterating the Kruskal-Katona theorem shows that the iterated lower shadow down to size $r$ of ${\mathcal{I}}_j$ has no more members than the corresponding iterated lower shadow of ${\mathcal{A}}_j$. Indeed, at each step initial segments minimize the next lower shadow, and its minimum size is increasing in the input size. The latter iterated lower shadow lies in $\mathcal{B}$. Therefore every $r$-subset of every member of ${\mathcal{I}}_j$ lies in $\mathcal{J}$.

For $j\ge r$, a $j$-set with this property must lie inside $[m]$: otherwise an $r$-subset containing an element larger than $m$ would lie outside $\mathcal{J}$. Among $j$-sets inside $[m]$, exactly those containing $R$ are forbidden. HenceAdding these bounds proves the contrapositive. Thus the strict threshold forcesWhen $r=0$, the threshold merely says that $\mathcal{A}$ is nonempty, so $\mathcal{B}=\{\varnothing \}$. When $m<r$, the claimed lower bound is zero. The strict inequality is sharp: the family of all subsets of $[m]$ of size at least $r$ that do not contain $R$ attains the displayed sum and has exactly $\left(\genfrac{}{}{0ex}{}{m}{r}\right)-1$ members in its size-$r$ iterated lower shadow.

We use the standard convention that a two-intersecting family satisfies $|A\cap B|\ge 2$ for every pair of members, including $A=B$. In particular every member has at least two elements.

An intersecting shadow lemma. If $\mathcal{F}$ is an intersecting family of $r$-sets, $r\ge 1$, thenHere is a proof, so no additional shadow theorem is being assumed. For $i<j$, an elementary set shift replaces a member $A$ containing $j$ but not $i$ by $(A\setminus \{j\})\cup \{i\}$ exactly when that replacement is not already in the family. This preserves cardinality and the intersecting family property. The only potentially troublesome pair consists of a moved member and an unmoved member $B$ containing $j$ but not $i$. But then $B$'s replacement was already present, and the two original members obtained by using that replacement would have been disjoint if the new pair were disjoint.

Alsoso an elementary set shift cannot increase the lower shadow. For completeness, a shadow set containing neither $i,j$ or both has an unchanged witness in the original lower shadow. A shadow set containing $i$ but not $j$ is either originally present or the replacement of an originally present shadow set. If a shadow set contains $j$ but not $i$, its witnessing member survived the elementary set shift; either that member contains both coordinates, or its replacement was already present. In either case both the shadow set and its replacement were originally present, so the former survives in the shifted lower shadow.

Repeated elementary set shifts terminate because the sum of the elements of all members decreases whenever the family changes. In the resulting shifted set family $\mathcal{H}$, if $a_1<\cdots <a_r$ is a member and $b_1<\cdots <b_r$ satisfies $b_i\le a_i$ for every $i$, then $\{b_1,\dots ,b_r\}$ is also a member. Every $A\in \mathcal{H}$ has a prefix $[2q-1]$ containing $q$ of its elements. Otherwise its sorted elements satisfy $a_i\ge 2i$, and the first $r$ elements outside $A$ form a disjoint member componentwise no larger than $A$, contradicting the intersecting family property.

Choose the first such prefix and reflect membership inside it:This has size $r-1$. The set $D\cup \{2q-1\}$ is componentwise no larger than $A$: before the first excess, the prefix counts of $A$ are at most half the prefix length, and reflection only moves selected positions to the left. Thus $D$ belongs to $\partial \mathcal{H}$. This ballot reflection injection is injective: in $D$, the reflected prefix ends at the first position where unselected positions outnumber selected ones, and reflecting it again recovers $A$. Consequently $|\partial \mathcal{H}|\ge |\mathcal{H}|=|\mathcal{F}|$. Since elementary set shifts did not increase the lower shadow, this proves the intersecting shadow lemma.

The nonuniform two-intersecting family bound. Write ${\mathcal{A}}_i=\mathcal{A}\cap [n{]}^{(i)}$. No member of $\partial {\mathcal{A}}_i$ can be the complement of a member of ${\mathcal{A}}_{n-i+1}$: such an inclusion would make the intersection of the two original members have at most one element. The intersecting shadow lemma therefore givesFor $n=2h$, sum this over $1\le i\le h$. These pairs cover all nonempty levels, soEquality is attained by all subsets of size at least $h+1$: any two intersect in at least two elements.

For $n=2h+1$, the same pairs cover every level except $h+1$. Complements of the members of ${\mathcal{A}}_{h+1}$ form an intersecting family of $h$-sets, sinceFor $h\ge 1$, the permitted Erdős-Ko-Rado theorem bounds this middle level by $\left(\genfrac{}{}{0ex}{}{2h}{h-1}\right)=\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)$. HenceEquality is attained by all $(h+1)$-sets inside $[2h]$, together with all subsets of $[2h+1]$ of size at least $h+2$. Two members of the first group intersect in at least two elements; a member from each group intersects in at least two; two members of the second group intersect in at least three. For $n=1$ the only two-intersecting family is empty, which also gives equality. The empty-ground-set case is likewise immediate.

The pair-cover bound for a two-intersecting uniform family. If $\mathcal{A}$ is nonempty, fix $A_0\in \mathcal{A}$, with $|A_0|=r$. Every member contains one of the $\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ pairs inside $A_0$. Each fixed pair belongs to exactly $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets, so counting their union givesThe empty family is immediate; a nonempty two-intersecting family requires $r\ge 2$.

Witness-pair concentration for an intersecting uniform family. Let $\mathcal{A}$ now be an intersecting family of $r$-sets. If it is two-intersecting, the preceding bound, together with $\left(\genfrac{}{}{0ex}{}{r}{2}\right)\le (r-1{)}^2$ for $r\ge 2$, shows that any chosen $x\in [n]$ has the required property. Otherwise there are members $A,B$ with $A\cap B=\{x\}$. Every member $C$ not containing $x$ must contain some $a\in A\setminus \{x\}$ and some $b\in B\setminus \{x\}$. These two sets of possible witnesses are disjoint. There are $(r-1{)}^2$ witness pairs, and each is contained in $\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ $r$-sets. ThusFor $r=1$, a nonempty intersecting family consists of one singleton; choose its element and the number avoiding it is zero. This is the natural separate interpretation of the degenerate case, where the printed binomial coefficient has lower index $-1$. For an empty family any $x\in [n]$ works, provided $n\ge 1$ as usual.

The Frankl-Wilson theorem. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$. Suppose that $|A|\mathrm{mod}p\notin L$ for every $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for all distinct members. Thenwith terms beyond $n$ understood as zero.

Work over the finite field ${\mathbb{F}}_p$. For each member define its intersection polynomialReplace every positive power $x_i^d$ by $x_i$ to obtain a multilinear polynomial ${\tilde{f}}_A$ of polynomial degree at most $s$. This Boolean multilinearization preserves its values at every characteristic vector of a set. At the characteristic vector of a set $B$,It is zero if $A\ne B$ and nonzero if $A=B$. Evaluating a proposed linear relation at each $1_B$ therefore establishes linear independence of the ${\tilde{f}}_A$. The vector space of multilinear polynomials of polynomial degree at most $s$ has the basis of monomials ${\prod }_{i\in T}{x}_i$, $|T|\le s$, of size ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. This proves the Frankl-Wilson theorem by the polynomial method in combinatorics. The empty product for $s=0$ is $1$, and the argument still applies.

The constant-intersection family bound, directly. Write $\mathcal{F}=\{F_1,\dots ,F_q\}$ and assume $n\ge 1$. The cases $q\le 1$ are immediate. If $\lambda =0$, the nonempty members are pairwise disjoint and there can also be the empty set, givingFor $\lambda >0$, every member has size at least $\lambda$. If every member has size strictly greater than $\lambda$, form the real matrix $X$ whose rows are their characteristic vectors of sets. Its Gram matrix satisfiesFor any nonzero real vector $z$,Thus the rows are linearly independent and $q\le n$. If a member $F_1$ has size $\lambda$, it lies inside every other member. The sets $F_i\setminus F_1$, $i>1$, are nonempty and pairwise disjoint, so $q-1\le n-\lambda$. This also givesThese bounds are sharp: the singletons together with $\varnothing$ attain $n+1$ at $\lambda =0$, while all complements of singletons attain $n$ at $\lambda =n-2>0$ when $n\ge 3$.

The constant t-wise intersection dichotomy. In its substantive form the last argument requires $m\ge t$. The printed statement does not explicitly impose this. Without it the $t$-fold condition can be vacuous and the claimed dichotomy is false: take $t=3$, $m=2$, $n=1$, $A_1=\varnothing$, $A_2=\{1\}$ and $\lambda =1$. There is no $3$-tuple to test, no common $1$-set, and $k=0$, so $m=2>k+t-2=1$. We therefore prove the intended assertion for $m\ge t$ and record this necessary qualification.

If $\lambda =0$, the first alternative always holds with $S=\varnothing$. Suppose $\lambda >0$. Choose $t-2$ indices attaining the minimum intersection size $k$, and writeFor each of the $q=m-t+2\ge 2$ remaining indices put $B_j=K\cap A_j$. The hypothesis gives $|B_j\cap B_{\ell }|=\lambda$ for distinct remaining indices. This reduces the constant t-wise intersection dichotomy to a constant-intersection family bound on the $k$-element set $K$. The two possibilities are treated below.

A repeated trace produces the common set. If $B_j=B_{\ell }$ for two distinct remaining indices, their common value $S$ has size $\lambda$. For any other remaining index $h$, the identity $|B_h\cap B_j|=\lambda =|S|$ forces $S\subseteq B_h$. The inclusion also holds for $j,\ell$ themselves. Since $S\subseteq K$, it lies in every $A_i$ indexed by $I$ as well. ConsequentlyThis proves the common-set alternative of the constant t-wise intersection dichotomy. The conclusion only requires a common subset of size $\lambda$; for $m\ge t$, the full common intersection in fact also has size $\lambda$, because it is contained in a $t$-fold intersection of that size.

Distinct traces give the bound. If the common-set alternative fails, the preceding argument shows that the traces $B_j$ are all distinct. They form a set family on the $k$-element ground set $K$ with constant pairwise intersection $\lambda >0$. The constant-intersection family bound therefore gives $q\le k$. Since $q=m-t+2$,Here $k\ge \lambda >0$, because any two of the remaining traces intersect in $\lambda$ elements, so applying the bound to $K$ is legitimate.

The bound is sharp even when the common-set alternative fails. For any $m\ge t+1$, take ground set $[m]$ and $A_i=[m]\setminus \{i\}$ for $1\le i\le m$. Every $t$-fold intersection has size $\lambda =m-t>0$, but the intersection of all members is empty. Every $(t-2)$-fold intersection has size $k=m-t+2$. Thusand there is no common subset of size $\lambda$. These complement-of-singleton extremizers show that the bound cannot be reduced in general.