Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 109 (Combinatorics)

For a uniform set family $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isTo prove it, count the incident pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes exactly $r$ pairs, whereas every $B$ belongs to at most $n-r+1$ members of $[n{]}^{(r)}$. Thereforewhich is the displayed inequality after using the binomial coefficient identity $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

The LYM inequality says that every antichain $\mathcal{A}\subseteq \mathcal{P}([n])$ satisfiesFor the proof from the local inequality, take the lowest occupied level below the middle and replace that level by its upper shadow. The result remains an antichain: any new containment involving a set in the upper shadow would already give a containment involving the member of $\mathcal{A}$ immediately below it. The dual form of the Local LYM inequality says that this replacement cannot decrease the Lubell mass. Repeating upward below the middle, and similarly replacing high levels by their lower shadows, eventually puts the whole family in one middle level. Its final Lubell mass is at most one, so the original mass is also at most one.

For the maximal chain in a Boolean lattice proof, choose a Uniformly random maximal chain in a Boolean lattice. An $h$-element set lies on it with probability $1/\left(\genfrac{}{}{0ex}{}{n}{h}\right)$. Because an antichain meets each chain at most once, the expected value of the number of its members on the chain is at most one. By linearity of expectation, that expected value is precisely the displayed sum.

The Sperner theorem follows because $\left(\genfrac{}{}{0ex}{}{n}{|A|}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for every $A$. If equality holds in the resulting cardinality bound, every member lies on a largest level. For even $n$ this is the unique middle level. For odd $n$, the two middle levels have equal size; the regular connected inclusion graph between them and equality in Local LYM inequality force a chosen portion of the lower level to be either empty or the whole level. Hence the maximum antichains are exactly the complete middle level, with either middle level allowed when $n$ is odd.

The hypothesis says exactly that $\mathcal{A}$ is a k-Sperner family with $k=2$: it contains no three members forming a strict inclusion chain. Every maximal chain in a Boolean lattice consequently contains at most two members of $\mathcal{A}$, so the same random-chain argument gives $\lambda (\mathcal{A})\le 2$. For a fixed amount of Lubell mass, cardinality is maximized by using the levels with the two largest binomial coefficients. The Erdős theorem on k-Sperner families therefore givesThe bound is attained by taking the union of two levels having those sizes.

Let $\mathcal{A}\subseteq [n{]}^{(r)}$ be an intersecting family, with $n\ge 2r$. By the Iterated local LYM inequality, its upper shadow in level $n-r$ satisfiesThe family of complements ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$ also lies in level $n-r$ and has cardinality $|\mathcal{A}|$. It is disjoint from the upper shadow: if $A\subseteq [n]\setminus B$ for $A,B\in \mathcal{A}$, then $A\cap B=\varnothing$, contradicting intersection. Both families fit inside the $(n-r)$th level, soThus replacing the Kruskal-Katona theorem by Local LYM gives onlyThis agrees with the Erdős-Ko-Rado theorem when $n=2r$ but is weaker when $n>2r$.

The Kruskal-Katona theorem states that if $\mathcal{A}\subseteq [n{]}^{(r)}$ has the unique binomial representationthen its lower shadow obeysAn initial segment of colexicographic order has exactly this shadow.

Here is the UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-size sets $U,V$, the UV-compression $C_{U,V}$ replaces the pattern $V$ by $U$ when the image is not already in the family. If the family is not an initial colexicographic segment, choose a changing pair with $\max U<\max V$ and $|U|$ minimal. Minimality ensures that for every $x\in U$ an appropriate smaller compression $C_{U\setminus \{x\},V\setminus \{y\}}$ already fixes the family. The Shadow lemma for UV-compressions then givesMeanwhile the binary weight ${\sum }_{A\in \mathcal{A}}{\sum }_{i\in A}{2}^i$ strictly decreases. Iterating must terminate, and a terminal family is an initial colexicographic segment. Computing that segment's shadow from its binomial representation proves the theorem.

We next classify pairs that decrease the shadow for every uniform family. The answer, including the identity case, isFor $|U|=0$ the operation is the identity. For $|U|=1$, the hypotheses of the Shadow lemma for UV-compressions reduce to stability under the empty compression and therefore hold for every family.

To see failure for larger pairs, relabel freely. If $|U|=|V|=2$, write $U=\{u_1,u_2\}$ and $V=\{v_1,v_2\}$. The familyhas a three-point lower shadow, whereas its compression replaces $v_1{v}_2$ by $u_1{u}_2$ and has a four-point lower shadow. If the common size is $m\ge 3$, takeThe old two shadows overlap once and have size $2m-1$. Compression replaces $V$ by $U$; the two resulting $m$-sets intersect in only $u_1$, so their lower shadows are disjoint and have size $2m$.

For the two specified pairs, the answer is no in both cases, even after assuming the family is left-compressed.

For $(U,V)=(345,126)$, takeThis family is left-compressed. Its compression replaces $126$ by $345$. The old shadow isof size nine, while the new shadow replaces the last two pairs by $34,35,45$ and has size ten.

For $(U,V)=(145,236)$, take the left-compressed familyIts shadow consists of $12,13,23$ and the nine pairs having one element in $\{1,2,3\}$ and one in $\{4,5,6\}$, so it has size twelve. Compression replaces $236$ by $145$; all twelve old shadow pairs remain and $45$ is added. The new shadow therefore has size thirteen.

Write $N[A]$ for the closed graph neighbourhood of $A$. Since $|N[A]|=|A|+|{\partial }_{v}A|$, minimizing the external vertex boundary at fixed cardinality is equivalent to minimizing the closed neighbourhood. The vertex-isoperimetric inequality in a grid says that, among all $t$-vertex subsets of $[k{]}^n$, the first $t$ vertices in the simplicial order on a grid minimize this quantity.

We prove the theorem by mathematical induction on $n$, using the allowed two-dimensional case. Fix a coordinate $i$ and write $A_j\subseteq [k{]}^{n-1}$ for the section in which that coordinate equals $j$. Replace each $A_j$ by the equally large initial simplicial segment $B_j$. By induction, $|N[B_j]|\le |N[A_j]|$. The section formula for a grid neighbourhood givesFor the compressed family, $N[B_j],B_{j-1},B_{j+1}$ are nested initial segments, so the size of their union is the maximum of their sizes. That maximum is no larger than the size of the corresponding uncompressed union. Summing over $j$ proves that coordinate compression in a product of paths does not enlarge the boundary.

Apply these compressions in every coordinate, choosing among boundary-minimizing outcomes one with least coordinate-sum weight. If the result were not an initial simplicial segment, it would contain a later vertex while omitting an earlier one. After cancelling coordinates in which they agree, this gives an inversion in a two-coordinate face. Replacing the occupied portion of that face by the equal-size initial segment in $[k{]}^2$ does not increase its neighbourhood by the assumed two-dimensional theorem, while it strictly lowers the weight. This contradiction is the local-to-global lemma for simplicial grid order, and completes the induction.

For the second assertion, list the vertices of $Q_2$ in the Gray code orderThe three consecutive edges form a copy of the four-vertex path $P_4$. Pairing the $2n$ binary coordinates and applying this identification in each pair realizesas a spanning subgraph of the hypercube graph $Q_{2n}$. For any fixed vertex set, adding graph edges can only enlarge its external vertex boundary. Hence a $t$-set in $Q_{2n}$ has boundary at least that of the same $t$ vertices in $[4{]}^n$, which by hypothesis is at least $s$. Therefore

A multiset $\mathcal{C}$ of subsets of $[n]$ is a uniform cover of multiplicity $k$ when each coordinate occurs in exactly $k$ members. The uniform covers theorem states that every Euclidean body $S\subseteq {\mathbb{R}}^n$ satisfieswhere $S_A$ is the coordinate projection of a Euclidean body onto the coordinates in $A$.

We prove it by induction on $n$. Split the cover into ${\mathcal{C}}^{-}$, whose members omit $n$, and ${\mathcal{C}}^{+}$, whose members contain $n$. Exactly $k$ members lie in ${\mathcal{C}}^{+}$. For a last-coordinate value $x$, let $S(x)\subseteq {\mathbb{R}}^{n-1}$ be the corresponding slice. Removing $n$ from the members of ${\mathcal{C}}^{+}$ and retaining the members of ${\mathcal{C}}^{-}$ gives a $k$-uniform cover of $[n-1]$. The inductive hypothesis and Fubini's theorem giveApply Hölder's inequality to the $k$ factors in the integral. Sincewe obtain $|S|\le {\prod }_{A\in \mathcal{C}}|S_A{|}^{1/k}$, which is the result after taking the $k$th power. The one-dimensional base case is immediate.

The Bollobas--Thomason box theorem states that for every body $S\subseteq {\mathbb{R}}^n$ there is an axis-parallel box $B$ such thatAn irreducible uniform cover cannot be decomposed into two smaller uniform covers. There are only finitely many such covers of $[n]$: encode a cover by its multiplicity vector in ${\mathbb{N}}^{2^n}$ and apply the Dickson lemma.

Choose a componentwise minimal positive array $(x_A{)}_{A\subseteq [n]}$ satisfyingfor every irreducible $k$-uniform cover $\mathcal{C}$, together withThe actual projection volumes are feasible by the uniform covers theorem, and finiteness gives a minimal array. Every uniform cover is a disjoint union of irreducible ones, so its cover inequality also holds for this array.

Minimality implies that, for each coordinate $i$, some tight uniform-cover inequality can be chosen whose cover contains the singleton $\{i\}$. Indeed, either such an inequality already blocks decreasing $x_{\{i\}}$, or a tight product inequality $x_A={\prod }_{j\in A}{x}_{\{j\}}$ does; in the latter case take a tight cover containing $A$ and replace that occurrence of $A$ by its singleton coordinates. Let these tight covers be ${\mathcal{C}}_i$, of multiplicities $k_i$, and let $K={\sum }_i{k}_i$. Their multiset union is a $K$-uniform cover. Removing one copy of every singleton leaves a $(K-1)$-uniform cover, so comparison of its cover inequality with the product of all the tight equalities yieldsThe singleton cover gives the reverse inequality, henceFor any $A\subseteq [n]$, the one-uniform cover consisting of $A$ and the singletons $\{i\}$ for $i\notin A$ now gives $x_A\ge {\prod }_{i\in A}{x}_{\{i\}}$. The defining product inequality gives the reverse bound. Thus all these quantities are equal. Taking the side lengths of $B$ to be $x_{\{1\}},\dots ,x_{\{n\}}$ proves the theorem.

Finally suppose that the proper body $S\subseteq {\mathbb{R}}^3$ satisfiesThis is equality in the three-dimensional Loomis--Whitney inequality. In its proof, equality must hold in both applications of Cauchy-Schwarz inequality. Their equality conditions force the three projection indicators to factor through one-dimensional measurable sets $E_1,E_2,E_3$, and forceup to a set of Lebesgue measure zero; this is Equality in the three-dimensional Loomis--Whitney inequality.

Because $S$ is connected, each one-coordinate projection is connected and hence is an interval. Because $S$ is a finite union of positive-volume axis-parallel boxes, a proper difference between $S$ and the product of those three intervals would contain a positive-volume rectangular cell in a common finite subdivision. That would contradict equality up to measure zero. Consequently the equality is exact and