Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 14 (Combinatorics)

Write $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ for the $k$th uniform layer of the Boolean cube. For $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, $1\le k\le n$, its lower shadow is $\partial \mathcal{F}=\{B:|B|=k-1,B\subset A\text{ for some }A\in \mathcal{F}\}$. The Local LYM inequality statesTo prove it, count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=k-1$. Each $A$ contributes $k$ pairs; each member of the lower shadow contributes at most $n-k+1$. Thus $k|\mathcal{F}|\le (n-k+1)|\partial \mathcal{F}|$, which is exactly the displayed Local LYM inequality. The corresponding upper shadow inequality follows either by taking complements or by counting upward inclusion pairs.

For an antichain $\mathcal{A}\subseteq \mathcal{P}([n])$, put ${\mathcal{A}}_k=\mathcal{A}\cap \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$. The LYM inequality isFor the first proof, set ${\mathcal{B}}_n={\mathcal{A}}_n$ and recursively ${\mathcal{B}}_k={\mathcal{A}}_k\cup \partial {\mathcal{B}}_{k+1}$. Every member of ${\mathcal{B}}_{k+1}$ is a subset of an original member of $\mathcal{A}$ of size at least $k+1$. Consequently ${\mathcal{A}}_k$ and $\partial {\mathcal{B}}_{k+1}$ are disjoint: otherwise one original member would properly contain another, contradicting the antichain condition. The Local LYM inequality now givesIterating down to $k=0$ bounds the desired sum by $|{\mathcal{B}}_0|\le 1$, proving the LYM inequality.

For the second proof, a permutation $(i_1,\dots ,i_n)$ determines a maximal chain in a Boolean lattice through the successive initial subsets $\varnothing ,\{i_1\},\dots ,[n]$. A member $A$ of size $k$ lies on exactly $k!(n-k)!$ of these $n!$ maximal chains in a Boolean lattice. An antichain meets each such chain in a partially ordered set at most once. Counting its incidences with the maximal chains in a Boolean lattice therefore yields ${\sum }_{A\in \mathcal{A}}|A|!(n-|A|)!\le n!$. Division by $n!$ is the LYM inequality again.

The Sperner theorem says that an antichain has at most $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members. Indeed $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le M$ for every $k$, soThe middle uniform layer of the Boolean cube attains the bound. For equality in Sperner theorem, equality throughout forces every member to lie in a layer of maximum size. If $n=2k$, this forces $\mathcal{A}=\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$.

If $n=2k+1$, only ranks $k$ and $k+1$ are possible. Let $\mathcal{L}={\mathcal{A}}_k$, $\mathcal{U}={\mathcal{A}}_{k+1}$, and $\mathcal{S}=\nabla \mathcal{L}$ be the upper shadow. The antichain condition gives $\mathcal{U}\cap \mathcal{S}=\varnothing$. The Local LYM inequality for the two equally sized middle layers gives $|\mathcal{S}|\ge |\mathcal{L}|$, while $|\mathcal{L}|+|\mathcal{U}|=M$ forces $|\mathcal{S}|=|\mathcal{L}|$ and $\mathcal{U}=\left(\genfrac{}{}{0ex}{}{[n]}{k+1}\right)\setminus \mathcal{S}$.

Consider the inclusion bipartite graph between these two middle layers. It is a $(k+1)$-regular graph. Since $|\mathcal{S}|=|\mathcal{L}|$, all $(k+1)|\mathcal{S}|$ edges incident to $\mathcal{S}$ must come from $\mathcal{L}$; there are no edges from its complement on the lower side into $\mathcal{S}$. This bipartite graph is a connected graph: any two $k$-subsets can be joined by single-element exchanges, and each exchange passes through their common $(k+1)$-superset; every upper vertex has a lower neighbour. For $k=0$ it is just one edge. Hence either $\mathcal{L}=\varnothing$ or $\mathcal{L}$ is the whole lower layer. We have proved the complete classification:The two possibilities coincide for even $n$; for $n=0$ the unique maximum antichain is $\{\varnothing \}$.

Finally enumerate the members of the separating set system as $A_1,\dots ,A_m$ and encode each point $i\in [n]$ by $T_i=\{a\in [m]:i\in A_a\}$. Separation of the ordered pair $(i,j)$ means $T_i\setminus T_j\ne \varnothing$. Applying the hypothesis also to $(j,i)$ shows that the $n$ sets $T_i$ are distinct and pairwise incomparable. They form an antichain in $\mathcal{P}([m])$, so the Sperner theorem immediately gives

The Erdős-Ko-Rado theorem asserts that, for $1\le r<n/2$, every intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ satisfiesThe bound is attained by the set family of all $r$-subsets containing one prescribed point. Here lexicographic order means that $X<Y$ when the smallest element of their symmetric difference belongs to $X$.

The first $M=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ members in lexicographic order are exactly those containing $1$. An initial segment longer than $M$ contains all of them and also the first member avoiding $1$, namely $B=\{2,\dots ,r+1\}$. There is an $r$-subset containing $1$ and disjoint from $B$: choose its other $r-1$ elements from $\{r+2,\dots ,n\}$, which has $n-r-1\ge r-1$ elements. Consequently any longer lexicographic initial segment fails to be an intersecting family. Thus preservation of the intersection property upon replacing a set family by the equally large lexicographic initial segment proves the displayed bound.

Here is a direct UV-compression proof of that preservation statement. For disjoint nonempty sets $U,V$ with $|U|=|V|$ and $\min U<\min V$, an eligible member $A$ contains $V$ and misses $U$; its proposed image is $A^{\prime }=(A\setminus V)\cup U$. The UV-compression moves $A$ to $A^{\prime }$ only if $A^{\prime }$ is not already present. Each eligible pair is either kept as a pair or moved from its later to its earlier member, so this operation preserves cardinality and uniformity and strictly decreases the sum of lexicographic order positions whenever it changes the set family.

The essential intersection-preserving lexicographic UV-compression lemma is that this operation preserves an intersecting family whenever all smaller lexicographically improving UV-compressions already leave that set family unchanged. Suppose instead that the compressed set family has disjoint members. At least one, say $A^{\prime }$, must be newly moved. Both newly moved members would contain $U$, so the other, $B$, is a retained old member. Write $A=(A^{\prime }\setminus U)\cup V$ for the old preimage. Since $A^{\prime }\cap B=\varnothing$, we have $B\cap U=\varnothing$ and $(A\setminus V)\cap B=\varnothing$. Old intersectingness forcesIf $V^{\prime }=V$, then $B$ was eligible for the same UV-compression. Since it was retained, $B^{\prime }=(B\setminus V)\cup U$ was already present. But $A\cap B^{\prime }=\varnothing$, contradicting old intersectingness.

Otherwise $0<|V^{\prime }|<|V|$. Choose $U^{\prime }\subset U$ with $|U^{\prime }|=|V^{\prime }|$ and $\min U\in U^{\prime }$. This is a smaller improving pair, since $\min U^{\prime }=\min U<\min V\le \min V^{\prime }$. The old member $A$ is eligible for its UV-compression. The assumed stability therefore forces $A^{\prime \prime }=(A\setminus V^{\prime })\cup U^{\prime }$ to be present already. Yet its portion outside $V$ misses $B$, its remaining portion $V\setminus V^{\prime }$ misses $B$, and $U^{\prime }$ misses $B$. Thus $A^{\prime \prime }\cap B=\varnothing$, the required contradiction. This proves the lemma, including the size-one case, where only the first alternative can arise.

Starting with $\mathcal{A}$, repeatedly choose a changing improving UV-compression with the smallest possible $|U|$. The lemma applies at each step because every smaller improving UV-compression is then unchanged. Thus every intermediate set family is intersecting. The strictly decreasing nonnegative integer sum of lexicographic order positions ensures termination. If the terminal set family were not an initial segment, there would be a missing $X$ earlier than a present $Y$. Taking $U=X\setminus Y$ and $V=Y\setminus X$ gives equally sized nonempty disjoint sets with $\min U<\min V$, and moves $Y$ to the missing $X$. That contradicts termination. The terminal set family is therefore exactly the equally large lexicographic initial segment, and it is intersecting. This proves the required lexicographic statement directly, and hence the Erdős-Ko-Rado theorem.

Identify the vertices of the Boolean hypercube $Q_n$ with subsets of $[n]$, adjacent when their symmetric difference has size one. Write $N(\mathcal{A})$ for the closed graph neighbourhood, including $\mathcal{A}$ itself. In simplicial order on the discrete cube, smaller sets come first, and equal-sized sets are ordered by lexicographic order: the least element of the symmetric difference belongs to the earlier member. Let $I_m$ denote the first $m$ vertices. The vertex-isoperimetric inequality in the discrete cube statesSubtracting $|\mathcal{A}|$ gives the equivalent assertion for the external vertex boundary.

We first check that $N(I_m)$ is also an initial segment in simplicial order on the discrete cube. Apart from the empty and full cases, $I_m$ consists of complete lower layers and a lexicographic initial segment $\mathcal{F}$ in its top rank $r$. Its closed graph neighbourhood contains all ranks at most $r$ and the upper shadow $\nabla \mathcal{F}$ in rank $r+1$. This upper shadow is lexicographic initial: an $(r+1)$-subset $C$ belongs to it precisely when its first $r$-subset in lexicographic order, obtained by deleting its largest element, belongs to $\mathcal{F}$. Taking the first $r$ elements preserves weak lexicographic order, proving the assertion. This also handles $r=0$, where $N(\{\varnothing \})$ consists of ranks zero and one.

We prove the vertex-isoperimetric inequality in the discrete cube by mathematical induction on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the sections without and with $i$. The two sections of its closed graph neighbourhood areA simplicial section compression replaces ${\mathcal{A}}_j$ by the initial segment $I_{a_j}$ of size $a_j=|{\mathcal{A}}_j|$ in the other coordinates. By the preceding observation, both $N(I_{a_j})$ and $I_{a_{1-j}}$ are initial segments, so their union has size $\max \{|N(I_{a_j})|,a_{1-j}\}$. The mathematical induction hypothesis givesAdding the two section bounds proves that simplicial section compression cannot increase the closed graph neighbourhood.

Apply changing simplicial section compressions until none remains. The sum of the global simplicial order on the discrete cube positions strictly decreases at each step: within a section the order is exactly the restriction of the global order. Thus the procedure terminates at a set family $\mathcal{B}$ every coordinate section of which is initial. We now classify the possible terminal families for simplicial section compression, rather than assuming this terminal set family must be globally initial.

If $X<Y$, $X\notin \mathcal{B}$ and $Y\in \mathcal{B}$, then $X,Y$ cannot agree in any coordinate, since that coordinate section would have an omitted earlier member and an included later one. Therefore $Y=X^c$. Let $X$ be the first omitted vertex and $Y$ the last included vertex. If $\mathcal{B}$ is noninitial, $X<Y$ and $Y=X^c$. Any vertex $Z$ strictly between them would have to be included, since an omitted $Z$ paired with $Y$ would have to equal $Y^c=X$. But it would also have to be omitted, since an included $Z$ paired with $X$ would have to equal $X^c=Y$. Thus there is no such $Z$: $X,Y$ are consecutive complementary vertices. Everything before $X$ is included and everything after $Y$ omitted. Hence $\mathcal{B}$ is obtained from the initial segment of its size by replacing $X$ with its immediate successor $X^c$.

There are only two forms of this exception. If $n=2r+1$, consecutive complementary vertices must straddle ranks $r,r+1$; otherwise an intermediate rank or a further vertex in one of their ranks separates them. They are consequentlywith $X$ the last $r$-subset and $Y$ the first $(r+1)$-subset. The corresponding initial segment is all ranks at most $r$. For $r\ge 1$, the omitted $X$ remains in $N(\mathcal{B})$ through a lower neighbour, and every $(r+1)$-subset has at least two $r$-subsets, only one of which was omitted. Thus $N(\mathcal{B})$ contains every rank at most $r+1$, namely $N(I_{|\mathcal{B}|})$. For $r=0$ both singleton closed graph neighbourhoods are the whole $Q_1$.

If $n=2r$, the two complementary vertices must both have rank $r$. The complement map reverses the lexicographic order in that rank, so a consecutive complementary pair must be its central pair. Exactly half the $r$-subsets contain $1$, and all of those precede those missing $1$. Therefore the pair isHere $I_{|\mathcal{B}|}$ comprises all ranks below $r$ and all $r$-subsets containing $1$. For $r\ge 2$, $N(\mathcal{B})$ contains every rank at most $r$, because all lower ranks were retained. Every $(r+1)$-subset containing $1$ has $r\ge 2$ different $r$-subsets containing $1$, so deletion of the one member $X$ removes no vertex of the upper shadow. Consequently $N(\mathcal{B})\supseteq N(I_{|\mathcal{B}|})$. For $r=1$, the two closed graph neighbourhoods both have size three in $Q_2$. These cases exhaust the exceptions. Since the successive simplicial section compressions never increased the closed graph neighbourhood, this proves the vertex-isoperimetric inequality in the discrete cube.

The same argument gives all integer radii. Write $N^t$ for $t$ repetitions of the closed graph neighbourhood. Its application to an initial segment is again initial; the sizes of these initial segments are monotone in the original size. Inducting on $t$ therefore gives

For the concentration question, use uniform probability measure on a finite connected graph and normalize its graph distance by its graph diameter. A sequence is a Lévy family of graphs if, for every fixed $\epsilon >0$ and $\delta >0$, the radius-$\epsilon$ neighbourhood of every set of measure at least $\delta$ has measure tending to one, uniformly over those sets. One may equivalently require this only for sets of measure at least one half. To see the reverse implication, first the radius-$\epsilon /2$ neighbourhood of every positive-density set must eventually have measure greater than one half. Otherwise its complement has measure at least one half, while the radius-$\epsilon /4$ neighbourhood of that complement misses the original positive-density set, contradicting the half-measure condition. Apply the half-measure condition once more to the radius-$\epsilon /2$ neighbourhood, enlarging it by another $\epsilon /2$, to obtain the full claim. The metric normalization is essential here.

For $Q_n$, the graph diameter is $n$. A uniformly chosen vertex has size $Z_n$ with binomial distribution $\mathrm{Bin}(n,1/2)$, expectation $n/2$ and variance $n/4$. Fix $\delta >0$ and choose $C>0$ so that $1/(4C^2)<\delta$. By Chebyshev's inequality,For sufficiently large $n$, put $k_n=\lfloor n/2-C\sqrt{n}\rfloor \ge 0$. Every initial segment of measure at least $\delta$ contains the complete ranks through $k_n$. Its radius-$t$ graph neighbourhood therefore contains every rank at most $k_n+t$. Taking $t=\lfloor \epsilon n\rfloor$, the all-radius vertex-isoperimetric inequality in the discrete cube gives, uniformly for $|\mathcal{A}|\ge \delta 2^n$,The last Chebyshev's inequality is used only when its denominator has positive square root. These are precisely the radius-$\epsilon$ neighbourhoods in the normalized graph distance. The discrete cubes form a Lévy family. In fact, taking $t=\lfloor n^{3/4}\rfloor$ in the same bound makes the omitted measure $O(n^{-1/2})$ for each fixed $\delta$: a radius that is $o(n)$ already suffices.

For fixed $d\ge 1$, the nearest-neighbour grid $[n{]}^d$ has graph distance ${\sum }_i|x_i-y_i|$ and graph diameter $d(n-1)$. Take the slab ${\mathcal{A}}_n=\{x:x_1\le \lceil n/2\rceil \}$, whose uniform measure is at least one half. Its integer radius-$t$ graph neighbourhood is exactly $\{x:x_1\le \min (n,\lceil n/2\rceil +t)\}$: changing the first coordinate alone attains the minimum distance to the slab. For $0<\epsilon <1/(2d)$ and $t=\lfloor \epsilon d(n-1)\rfloor$, the omitted proportion tends toThus there is failure of concentration in fixed-dimensional grids, and the fixed-dimensional grids do not form a Lévy family with normalized graph distance.

The Frankl-Wilson theorem in its uniform form says: let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have size $s\le \min (k,n-k)$, and let $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ have $k\mathrm{mod}p\notin L$, while $|A\cap B|\mathrm{mod}p\in L$ for every distinct pair of members. Then

The modular-intersection, nonuniform form of the Frankl-Wilson theorem is as follows. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$ satisfy $|A|\mathrm{mod}p\notin L$ for each $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for distinct $A,B\in \mathcal{F}$. ThenThis nonuniform Frankl-Wilson theorem allows different sizes and different diagonal residues; in particular it applies when all sizes have one common residue outside $L$.

To prove it by the polynomial method in combinatorics, work over the finite field ${\mathbb{F}}_p$ and associate to each member the intersection polynomialReplace each positive power of $x_i$ in its expansion by $x_i$ to obtain its multilinear reduction on the Boolean cube ${\tilde{P}}_A$. This preserves evaluation on every characteristic vector, whose coordinates are zero or one, and leaves degree at most $s$. At the characteristic vector $1_B$,It is zero for distinct $A,B$, and nonzero for $B=A$ by the diagonal hypothesis. If ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at each $1_B$ forces $c_B=0$. Thus the multilinear polynomials are linearly independent. They belong to the vector space with basis the square-free monomials ${\prod }_{i\in S}{x}_i$ for $|S|\le s$, whose dimension is the displayed sum. This proves the nonuniform form, including $s=0$, where distinct members are impossible and the empty product is one.

For the sharp uniform form, we need the low-degree evaluation rank on a uniform layer. Form the integer matrix $M$ whose rows are indexed by $S\subseteq [n]$ with $|S|\le s$, columns by $k$-subsets $T$, and entries $M_{S,T}=1_{S\subseteq T}$. These are evaluations of the square-free monomials. Over the rational numbers, the row of a $j$-subset $S$ satisfiesIndeed, when $S\subseteq T$ the left side counts the $s$-subsets between $S$ and $T$, and otherwise both sides vanish. Since $s\le k$, the coefficient is a positive integer. Thus the degree-$s$ rows span all the rows over the rational numbers, giving ${\mathrm{rank}}_{\mathbb{Q}}M\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every square submatrix of larger size has integer determinant zero, so its determinant remains zero modulo $p$. HenceThis reduction of matrix rank is the reason one must not try to divide by $\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)$ directly in ${\mathbb{F}}_p$.

The evaluations of the ${\tilde{P}}_A$ on the $k$th uniform layer of the Boolean cube lie in the row linear span of $M$ over ${\mathbb{F}}_p$. They are linearly independent as functions there, because restriction to the columns corresponding to $\mathcal{F}$ still gives the nonzero diagonal evaluation matrix. Their number is consequently at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. This completes the proof of the uniform Frankl-Wilson theorem as well.

For the odd-cardinality problem the sharper Oddtown theorem follows directly from linear algebra. Let $v_A=1_A\in {\mathbb{F}}_2^n$ be the characteristic vector. The parity conditions sayFor any linear combination ${\sum }_A{c}_A{v}_A=0$, take its dot product with $v_B$. All off-diagonal terms vanish, leaving $c_B=0$. Hence these vectors are linearly independent in an $n$-dimensional vector space, givingThe singleton sets show that the bound can be attained. Notice why the constant term in the general nonuniform Frankl-Wilson theorem is unnecessary here: these dot products already give a diagonal evaluation matrix using only the $n$ coordinate functions.

For even $n$, partition $[n]$ into the pairs $\{1,2\},\{3,4\},\dots ,\{n-1,n\}$ and take every union of a selection of these pairs. This gives exactly $2^{n/2}$ distinct sets, including the empty set. Each has even size; every pairwise intersection is again a union of entire pairs and therefore has even size. This attains the proposed bound.

For any set family satisfying the even-cardinality conditions, let $W$ be the linear span of its characteristic vectors over ${\mathbb{F}}_2$. Now the self-dot products vanish as well as the off-diagonal ones. By bilinearity, $u\cdot v=0$ for all $u,v\in W$, so $W\subseteq W^{\perp }$: it is a self-orthogonal binary subspace.

For completeness the standard bilinear form on ${\mathbb{F}}_2^n$ is nondegenerate, because a vector orthogonal to every coordinate vector has every coordinate zero. Thus the map $v\mapsto (w\mapsto v\cdot w)$ from ${\mathbb{F}}_2^n$ onto the dual space $W^{\ast }$ is surjective: every linear functional on $W$ extends to the whole vector space by extending a basis, and every such functional on ${\mathbb{F}}_2^n$ is a dot product with a vector. Its kernel is $W^{\perp }$. The rank-nullity theorem consequently gives $\dim W^{\perp }=n-\dim W$. The inclusion $W\subseteq W^{\perp }$ implies $\dim W\le n/2$. Finally, distinct members have distinct characteristic vectors, all in $W$, and a $k$-dimensional vector space over ${\mathbb{F}}_2$ has exactly $2^k$ elements. ThereforeThis proves the Eventown theorem and also explains the suggested dimension contradiction if the set family had more than $2^{n/2}$ members.