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

Write $D={\sum }_{i=1}^n{b}_i$ and let $\lambda$ denote Lebesgue measure. Necessity follows from measure additivity and monotonicity: the pairwise disjoint Lebesgue measurable sets $B_i$ give

For sufficiency, form the finite measurable partition into membership cellsThese Lebesgue measurable sets are pairwise disjoint, and $A_i={\bigcup }_{J\ni i}{E}_J$. Empty cells may be retained. Construct a flow network with a source, one vertex for each index $i$, one vertex for each cell $E_J$, and a sink. Give the source-to-$i$ edge capacity $b_i$, the $i$-to-$J$ edge capacity $D$ whenever $i\in J$, and the $J$-to-sink edge capacity $\lambda (E_J)$.

Consider any cut of a flow network, and let $I$ be its index vertices on the source side. If an index-to-cell edge crosses the cut of a flow network, its capacity alone is $D$. Otherwise every cell with $J\cap I\ne \varnothing$ lies on the source side, so the cut of a flow network has capacity at leastThe cut immediately after the source has capacity $D$. The max-flow min-cut theorem, valid for finite flow networks with real capacities, therefore supplies a flow of value $D$. Its cell allocations $f_{iJ}\ge 0$ satisfy

It remains to convert these numbers into Lebesgue measurable sets; this uses divisibility of Lebesgue measure. Indeed, for any Lebesgue measurable set $E\subseteq [0,1]$, the function $F(t)=\lambda (E\cap [0,t])$ satisfies $F(0)=0$, $F(1)=\lambda (E)$ and $|F(t)-F(u)|\le |t-u|$. Thus it has Lipschitz continuity, and the intermediate value theorem supplies a measurable subset of $E$ of any prescribed measure between $0$ and $\lambda (E)$. Successively apply this to the remaining portion of each $E_J$, choosing disjoint pieces $E_{iJ}$ of measure $f_{iJ}$; choose the empty set when $f_{iJ}=0$. ThenThis proves the measurable Hall theorem. The splitting step is essential: an arbitrary measure with an atom of a measure would not support the same conclusion. Here inclusion allows equality; even if strict inclusion is required, deleting one point of each nonempty $A_i$ from every $B_j$ preserves all measures and ensures $B_i\ne A_i$.

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

The printed inclusion symbol here means non-strict inclusion: the PDF explicitly excludes a common member of the two set families. We use $\subseteq$ throughout. Thus a cross-Sperner family pair need not consist of internal antichains; the restriction is between the two families.

Give the Boolean lattice the uniform probability measure, and write $N=2^n$. Form the upward closure of a set family and downward closure of a set family of $\mathcal{A}$:These are respectively an increasing event and a decreasing event. We have $\mathcal{A}\subseteq U\cap D$, whereas the cross-Sperner family condition gives $\mathcal{B}\subseteq U^c\cap D^c$. Set $u=\mathbb{P}(U)$ and $d=\mathbb{P}(D)$. By negative correlation of increasing and decreasing events, first for $U,D$ and then for $U^c,D^c$,Apply the Cauchy-Schwarz inequality to the unit vectors $(\sqrt{u},\sqrt{1-u})$ and $(\sqrt{d},\sqrt{1-d})$. It yieldsTherefore the Cross-Sperner inequality isIf the printed inclusion symbol were read as strict inclusion while the explicit exclusion of common members were discarded, this conclusion would fail, for example with both families equal to the middle uniform set family when $n=2$. The PDF's parenthetical clause fixes the intended convention.

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k$ and let $R=[n]\setminus (K_1\cup K_2)$. The two-block extremisers for the cross-Sperner inequality areFor $A\in \mathcal{A}$ and $B\in \mathcal{B}$, some point of $K_1$ belongs to $A$ but not $B$, so $A⊈B$. Some point of $K_2$ belongs to $B$ but not $A$, so $B⊈A$. Thus these form a cross-Sperner family pair.

An element of $\mathcal{A}$ fixes its intersections with both blocks and freely chooses its subset of $R$. An element of $\mathcal{B}$ chooses any proper subset of $K_1$, any nonempty subset of $K_2$, and any subset of $R$. HenceThe hypotheses ensure that the blocks exist and both set families are nonempty, including when $n=2k$. Moreover,so this construction attains equality in the Cross-Sperner inequality.

Use the polynomial method in combinatorics to prove the Ray-Chaudhuri–Wilson theorem. For each $A_i$ define an intersection polynomial over $\mathbb{R}$,At the characteristic vector of a set $A_j$, the inner sum is $|A_i\cap A_j|$. ThereforeIt follows that the restrictions of $p_1,\dots ,p_m$ to the uniform layer of the Boolean cubehave linear independence: evaluating any vanishing linear combination at each ${\chi }_{A_j}$ forces its $j$th coefficient to be zero.

Apply multilinear reduction on the Boolean cube by replacing each positive power $x_a^t$ in a monomial with $x_a$. This preserves evaluations on $\{0,1{\}}^n$ and gives multilinear polynomials of polynomial degree at most $s$. Counting all monomials of degrees up to $s$ would give only ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, which is too weak. Instead use homogenisation on a uniform layer.

Because $L$ has $s$ distinct integers in $\{0,\dots ,r-1\}$, we have $s\le r$. For $T\subseteq [n]$ with $|T|=j\le s$, write $x_T={\prod }_{a\in T}{x}_a$, with $x_{\varnothing }=1$. On ${\Omega }_r$,Indeed, at ${\chi }_A$ both sides vanish if $T⊈A$; otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands equal $1$. The denominator is positive since $j\le s\le r$. Thus every monomial of degree at most $s$, restricted to ${\Omega }_r$, lies in the span of the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ degree-$s$ monomials. This vector space consequently has dimension at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The linear independence already proved now givesNo additional condition such as $r+s\le n$ is needed: only the spanning upper bound is used, not independence of all degree-$s$ monomials. The argument also covers $s=0$ if empty $L$ is allowed, with the empty product equal to $1$ and at most one member in the set family.