Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 (Extremal and Probabilistic Combinatorics)

Let $e(A)$ count internal edges of the hypercube graph. Since each vertex has degree $n$, its edge boundary is $b_e(A)=n|A|-2e(A)$. The edge-isoperimetric inequality in the discrete cube gives $e(A)\le |A|{\log }_2|A|/2$, hence $b_e(A)\ge |A|(n-{\log }_2|A|)$.

For completeness, the entropy proof of cube edge-isoperimetry splits the final coordinate into sections of sizes $a,b$. Their internal edges contribute at most $(a{\log }_{2}a+b{\log }_{2}b)/2$ by induction, and their crossing edges at most $\min (a,b)$. For $m=a+b$ and $t=\min (a,b)/m$, the binary entropy function satisfies $H_2(t)\ge 2t$, so $a{\log }_{2}a+b{\log }_{2}b+2\min (a,b)\le m{\log }_{2}m$. The convention is $0{\log }_{2}0=0$.

A $k$-dimensional coordinate subcube has $2^k$ vertices and $k{2}^{k-1}$ internal edges, attaining the bound. Therefore

A down-set in the Boolean lattice is a family closed under taking subsets. Restricting the minimization to down-sets cannot decrease the minimum from the edge-isoperimetric inequality in the discrete cube.

The coordinate subcube consisting of all subsets of a fixed $k$-element set is itself a down-set and attains that minimum. Thus

Identify cube vertices with subsets of $[n]$. In a down-set $D$, every $A\in D$ has all its $|A|$ immediate lower neighbors in $D$. Counting each internal edge by its upper endpoint gives the edge boundary of a down-set in a cubeTo maximize it, minimize the sum of set sizes. Among all families of $m$ sets, the minimum is obtained by taking the smallest ranks first. This choice is a down-set: take every set of size below $r$, followed by any required selection of $r$-sets.

Write $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, with $M_{-1}=0$, and choose $r$ such that $M_{r-1}\le m\le M_r$. The largest edge boundary of a down-set is thereforeEquivalently, it is ${\sum }_{j<r}(n-2j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)+(n-2r)(m-M_{r-1})$. This includes $m=0$ and $m=2^n$, with boundary zero. If $m$ is exactly a complete-level size, either adjacent choice of $r$ gives the same value.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, an intersecting family $\mathcal{F}$ of $r$-subsets of $[n]$ satisfiesThe bound is sharp: take all $r$-sets containing one fixed element.

Use the Katona circle method. In any cyclic ordering of $[n]$, the cyclic interval intersection bound permits at most $r$ members of $\mathcal{F}$ to appear as length-$r$ intervals. To see the bound directly, rotate a chosen interval so that it ends at $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints except $n$ as $(j,j+n-r)$, $1\le j\le r-1$; the two intervals in each pair are disjoint, so at most one is chosen. Including the fixed interval gives at most $r$.

There are $(n-1)!$ oriented cyclic orders. A fixed $r$-set appears consecutively in $r!(n-r)!$ of them: collapse it to a block, cyclically order that block with the other $n-r$ elements, and order its members internally. Double counting the compatible family-member/order pairs gives $|\mathcal{F}|r!(n-r)!\le r(n-1)!$, proving the theorem.

Form the family $\mathcal{F}=\{A\subseteq [n]:{\sum }_{i\in A}{c}_i>1/2\}$. The nonnegative weights make it an up-set. It is an intersecting family, since two disjoint members would have combined weight exceeding one. The no-tie hypothesis makes it a self-dual set family: exactly one of $A,A^c$ belongs.

Let $a_j=|\mathcal{F}\cap (\genfrac{}{}{0ex}{}{[n]}{j})|/(\genfrac{}{}{0ex}{}{n}{j})$. Self-duality gives $a_{n-j}=1-a_j$. The Erdős-Ko-Rado theorem gives $a_j\le j/n$ for $j<n/2$; at $j=0$ this is immediate. If $n$ is even, $a_{n/2}=1/2$.

The biased measure of a set family is ${\mu }_p(\mathcal{F})={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)a_j{p}^j(1-p{)}^{n-j}$. By independence of the Bernoulli random variables, it equals $\mathbb{P}(Z\ge 1/2)$, since equality is excluded. Subtract $p={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)(j/n)p^j(1-p{)}^{n-j}$ and pair complementary levels. The complementary-layer bound for biased measure givesBoth factors are nonnegative for $p\ge 1/2$. The endpoints $p=1/2,1$ also follow directly, or by continuity. Thus the weighted Bernoulli majority bound is

The Ahlswede–Daykin inequality, also called the four functions theorem, concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on $\mathcal{P}([n])$. IfthenProve it by induction on $n$. The case $n=0$ is the single assumed inequality. For the induction step, sum each function over the last coordinate to obtain ${\alpha }^{\prime },{\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$ on $\mathcal{P}([n-1])$. For fixed $A,B$ in this smaller cube, set $a_i=\alpha (A\cup i\{n\})$, $b_i=\beta (B\cup i\{n\})$, $c_i=\gamma ((A\cup B)\cup i\{n\})$, and $d_i=\delta ((A\cap B)\cup i\{n\})$, where $i\{n\}$ is empty for $i=0$ and $\{n\}$ for $i=1$.

The hypotheses give $a_0{b}_0\le c_0{d}_0$, $a_1{b}_1\le c_1{d}_1$ and $a_0{b}_1,a_1{b}_0\le c_1{d}_0$. The two-point four-functions inequality shows that these imply $(a_0+a_1)(b_0+b_1)\le (c_0+c_1)(d_0+d_1)$. Here is its key algebra: put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $N=c_0{d}_1$. Then $x,y\le M$ and $xy\le MN$. If $M>0$, $(M-x)(M-y)\ge 0$ gives $x+y\le M+xy/M\le M+N$; if $M=0$, both cross terms vanish. Adding the two diagonal bounds proves the claim.

Thus the primed functions satisfy the same hypothesis, and the induction hypothesis applies. Their totals equal the original totals, completing the proof.

In the four functions theorem, take $\alpha =1_{\mathcal{A}}$, $\beta =1_{\mathcal{B}}$, $\gamma =1_{\mathcal{A}\vee \mathcal{B}}$ and $\delta =1_{\mathcal{A}\wedge \mathcal{B}}$, where the union and intersection of set families are the collections of all pairwise unions and intersections.

If $\alpha (A)\beta (B)=1$, then $A\cup B\in \mathcal{A}\vee \mathcal{B}$ and $A\cap B\in \mathcal{A}\wedge \mathcal{B}$, so the pointwise hypothesis holds. Otherwise its left side is zero. Summing these indicator functions gives

Complement the members of $\mathcal{B}$ in the fixed ground set: $\mathcal{C}=\{[n]\setminus B:B\in \mathcal{B}\}$, so $|\mathcal{C}|=|\mathcal{B}|$. The set difference identitiesshow that $\mathcal{A}\wedge \mathcal{C}=\mathcal{A}-\mathcal{B}$, while complementation bijects $\mathcal{A}\vee \mathcal{C}$ with $\mathcal{B}-\mathcal{A}$. Applying the four functions theorem to $\mathcal{A},\mathcal{C}$ therefore givesThe products count distinct resulting sets, with repeated pairwise differences included only once.

An independence graph of events, also called a dependency graph of events, has one vertex for each event $E_i$, with $E_i$ independent of the entire family of events indexed by its nonneighbors. Precisely, $E_i$ is independent of the sigma-algebra generated by those events. Pairwise independence alone is insufficient.

The asymmetric Lovász local lemma says that if numbers $0\le x_i<1$ satisfythen $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$ for a finite family. In the commonly used symmetric Lovász local lemma, if each probability is at most $q$ and the maximum graph degree is at most $d$, the sufficient condition is

Color each integer independently and uniformly with one of $k$ colors. For a translate $S+t$, let $E_t$ be the event that some color is missing. The union bound givesJoin two events in the dependency graph of events when their translates overlap. Nonneighbors depend on disjoint sets of independent colors, giving the required joint independence. Overlap occurs only if $u-t\in S-S$, so the maximum degree is at most $s(s-1)$.

With natural logarithms, $s\ge 6k\log k$ and $k\ge 20$ implyThe middle estimate uses that $s^2{e}^{-s/k}$ is decreasing for $s\ge 2k$, and the next uses $\log k\le \sqrt{k}$. Therefore the Lovász local lemma supplies a coloring avoiding every bad event in any specified finite family of translates.

To obtain one coloring for all translates, use the compactness extension of the Lovász local lemma. At level $N$, consider colorings of $[-N,N]\cap \mathbb{Z}$ satisfying every constraint whose translate is contained in that interval. There are finitely many constraints, and the preceding argument makes the level nonempty. Restrictions connect these colorings into a finitely branching tree. The König infinity lemma gives an infinite branch, hence a coloring of all integers. Every translate eventually lies in a level of this branch, so it contains every color.

Thus there exists a $k$-coloring of $\mathbb{Z}$ in which every translate of $S$ contains all $k$ colors. This is a polychromatic coloring of integer translates; the compactness step establishes existence of one simultaneous coloring.