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

Use $I_i=1_{A_i}$ and interpret the printed overlap term as $2\Delta ={\sum }_i{\sum }_{j\in J_i}\mathrm{Pr}(A_i\cap A_j)$; its unindexed $A,B$ are a typographical slip. Take $i\notin J_i$, as usual. If necessary, deleting $i$ from its own neighbourhood gives the proof below with a smaller nonnegative right-hand side, so the stated bound still follows.

If $\lambda =0$, every indicator is zero almost surely and the Poisson distribution with parameter zero is the same point mass. Suppose $\lambda >0$. For any $B\subseteq {\mathbb{Z}}_{\ge 0}$, put $h_B(k)=1_{k\in B}$ and let $Z$ have Poisson distribution with mean $\lambda$. Solve the Poisson Stein equationFor example, for $k\ge 1$ one can takeThe full weighted sum is zero, so using its complementary tail also shows this solution is bounded. The allowed Stein factor is $\Vert \Delta g{\Vert }_{\infty }\le \min (1,{\lambda }^{-1})$, where $\Delta g(k)=g(k+1)-g(k)$.

DefineJoint independence of $A_i$ from all events outside its neighbourhood makes $I_i$ independent of $W_i$, so $p_i\mathbb{E}g(W_i+1)=\mathbb{E}{I}_{i}g(W_i+1)$. Adding and subtracting those terms givesA difference over $m$ integer steps has magnitude at most $m\Vert \Delta g{\Vert }_{\infty }$. In the first sum the step count is $I_i+V_i$; in the second, on $I_i=1$, it is $V_i$. Consequently the absolute value is at mostThe Stein equation identifies the left side with $|\mathrm{Pr}(W\in B)-\mathrm{Pr}(Z\in B)|$. Taking the supremum over $B$ is the definition of total variation distance, proving the Stein-Chen bound with the Poisson Stein factor:

For the random uniform hypergraph, index indicators by four-vertex sets. Each such set is a hypergraph clique exactly when its four triples are all present, so its probability is $p^4$. Distinct sets use disjoint triple indicators unless their intersection has size three; disjoint underlying trials give the required joint independence. A fixed four-set has $d=4(n-4)$ dependent others, and each overlapping pair requires seven distinct triples, with joint probability $p^7$. Thus, with $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ and $\lambda =N{p}^4$, the bracket isSince $\lambda \min (1,{\lambda }^{-1})\le 1$,This calculation applies for $n\ge 4$ and $p>0$; if $p=0$ or $n<4$, the count and its Poisson parameter are zero and the conclusion is immediate.

The asymmetric Lovász local lemma says the following. For finitely many bad events with a dependency graph of events, if $0\le x_i<1$ satisfythenHere independence from nonneighbors is independence from their whole generated system, not just pairwise independence.

Prove by induction on $|S|$ that $\mathrm{Pr}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le x_i$ whenever $i\notin S$, with all conditioning probabilities positive. At $S=\varnothing$, the hypothesis gives $\mathrm{Pr}(A_i)\le x_i$. Split $S$ into its neighbor part $S_1$ and nonneighbor part $S_2$. ThenThe numerator uses joint nonneighbor independence. The denominator is exposed one event at a time; every conditional bad-event probability involves fewer than $|S|$ conditioning events, so induction supplies the product lower bound. The same product argument gives positivity of the conditioning events before using the fraction. Finally expose all complements in any order and multiply their conditional probabilities to obtain the claimed lower bound.

For maximum dependency degree $d\ge 1$ and event probabilities at most $p$, choose $x_i=1/(d+1)$. Since $(1+1/d{)}^d\le e$, the symmetric Lovász local lemma follows fromFor $d=0$, the events are jointly independent and avoidance has positive probability whenever $p<1$, so the displayed sufficient criterion also holds.

To obtain the local lemma Ramsey lower bound, colour the edges of $K_N$ independently with two equally likely colours. For every $k$-set $S$, the event that it is monochromatic has probability $p=2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events with intersections of size at most one depend on disjoint edge trials. Counting potentially shared pairs givesThe Lovász local lemma excludes all monochromatic $K_k$ if $ep(d+1)\le 1$. For $N\le ck{2}^{k/2}$, Stirling's approximation and $\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)\le N^{k-2}/(k-2)!$ give, uniformly for $c$ bounded above and away from zero,For a concrete approach to the limiting constant, choose $c_k=(\sqrt{2}/e)(1-3\log k/k)$ and take the integer part of $c_{k}k{2}^{k/2}$. Then $(e{c}_k/\sqrt{2}{)}^k\le k^{-3}$ for all sufficiently large $k$, so the criterion holds. Such a colouring shows $R(k)>N$, and thereforeThe undefined $o(i)$ printed in the PDF is read as the intended $o(1)$, with $k\to \infty$.

For the cycle, independently choose one of the twelve vertices in each part. Ignore cycle edges whose endpoints lie in the same part, since both endpoints cannot be selected. Every other edge defines a bad event of probability $1/144$. It uses just the choices in its two endpoint parts. A part's twelve vertices meet at most twenty-four cycle edges, so a bad event has at most $48-1=47$ neighbors in a dependency graph of events. Since $e(47+1)/144=e/3<1$, the Lovász local lemma gives a selection with no selected adjacent pair. Thus an independent transversal of size $n$ exists, for every stated partition.

Expose the independent coordinates in order and let $M_i=\mathbb{E}[f\mid X_1,\dots ,X_i]$, $M_0=\mathbb{E}f$. This is the Doob exposure martingale. For fixed earlier coordinates, write $h_i(x)=\mathbb{E}[f\mid X_i=x,\text{earlier coordinates}]$. The remaining coordinates have the same distribution for all $x$, and the coordinate-change hypothesis gives $|h_i(x)-h_i(y)|\le c_i$. Thus the conditional range of $M_i-M_{i-1}$ has length at most $c_i$, and its conditional mean is zero.

Here is the Hoeffding lemma needed for the sharp constant. If a mean-zero random variable $Y$ lies in an interval of length $c$, set $\psi (s)=\log \mathbb{E}{e}^{sY}$. Its second derivative is the variance under the exponentially tilted law. Under any such law, variance is at most $c^2/4$, by comparison with squared distance from the interval midpoint. Since $\psi (0)={\psi }^{\prime }(0)=0$, integration gives $\psi (s)\le s^2{c}^2/8$ for all real $s$. Applying this conditionally and iterating the tower property yieldsThe exponential Markov bound now givesFor $C>0$ choose $s=4t/C$. Apply the same argument to $-f$ and add the two tails, proving the McDiarmid inequalityFor $C=0$, $f$ is constant almost surely, and every positive-deviation probability is zero.

For the neighbourhood application, the ambient points must be elements of $\mathcal{P}[n]$, equivalently binary strings; the printed $y\in [n]$ is a type error. An $n$-element ambient set could not generally satisfy the stated exponential-size lower bound. Use the uniform product probability space on the Boolean cube and set $F(y)=d(y,A)$. Flipping one coordinate changes this Hamming distance by at most one, so $C=n$. Put $\mu =\mathbb{E}F$. Since $\mathrm{Pr}(F=0)=|A|/2^n\ge \epsilon$, the proved two-sided inequality gives, for $\mu >0$,Consequently $\mu \le \sqrt{(n/2)\log (2/\epsilon )}=t/2$; the same bound is immediate if $\mu =0$. ThereforeThis proves the Boolean cube expansion from bounded differences:The meaningful range is $0<\epsilon \le 1$; real radii are interpreted by the inequality on the integer-valued Hamming distance. The converted TeX's final $2^{2n}$ is another corruption: the original PDF has $2^n$.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

For $x\in \Omega$ and nonempty $A$, letThe Talagrand convex distance isEquivalently,For completeness, let $v_{\ast }$ be a closest point of the finite convex hull to zero. If $v_{\ast }\ne 0$, minimality gives $v_{\ast }\cdot (v-v_{\ast })\ge 0$ for every $v\in V$. Taking $\alpha =v_{\ast }/\Vert v_{\ast }\Vert$ proves that the supremum is at least $\Vert v_{\ast }\Vert$. Conversely each permitted $\alpha$ has ${\inf }_{v\in V}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }\Vert$ by Cauchy-Schwarz. The weights are nonnegative because the hull has nonnegative coordinates. If $v_{\ast }=0$, both sides are zero. This proves the dual definition used below.

We prove Talagrand's convex distance inequality by induction on the number of factors. Write $\Omega ={\Omega }^{\prime }\times X_n$, with measure $\mu \otimes \nu$, and $F_A=d_T(\cdot ,A{)}^2$. For a last-coordinate value $z$, let $A_z=\{y^{\prime }:(y^{\prime },z)\in A\}$. Choose a section $B=A_b$ of largest probability $m=\mu (B)>0$, and put $a_z=\mu (A_z)/m\in [0,1]$. The total event probability is $p=\mathrm{Pr}(A)=m{\sum }_z\nu (z)a_z$.

If $A_z$ has positive probability, combine mismatch vectors from $A_z$ and from $B$. A weight $t$ on the second section contributes at most $t$ in the last coordinate. Convexity of the squared Euclidean norm gives, for every $0\le t\le 1$,The last-coordinate contribution is actually zero if $z=b$, so the displayed upper bound remains valid. Hölder's inequality and the induction hypothesis yieldFor a zero-probability section use $t=1$ directly, so no division by zero or exponent of an infinite quantity is needed.

The scalar estimate for Talagrand product induction isHere is its proof. For $a>0$ set $L=-\log a$. If $L\le 1/2$, take $t=2L$; the logarithm of the left expression is $L-L^2$. Put $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ andsince $(2u-1{)}^2-u=(4u-1)(u-1)\ge 0$ for $u=e^L\ge 1$. Thus $h\ge 0$. If $L\ge 1/2$, choose $t=1$. The already proved boundary case gives $e^{1/4}\le 2-e^{-1/2}\le 2-a$. The same direct choice covers $a=0$.

Average the resulting section bounds over $z$:where the last inequality is equivalent to $(m-p{)}^2\ge 0$. The induction starts on the zero-coordinate singleton, where every positive-probability event is the whole space and the moment is one. HenceWe assume $\mathrm{Pr}(A)>0$; a zero-probability event has no finite right-hand bound to prove. Markov's inequality also gives

For the subsequence application, let $L(x)$ be the longest increasing subsequence length for independent sequence coordinates. A witness of length $\ell$ uses only $\ell$ positions. If $L(x)=\ell \ge b$ and $y$ satisfies $L(y)\le a<b$, at least $\ell -a$ witness positions must change: all unchanged witness positions remain in increasing order. Put weights $1/\sqrt{\ell }$ on the witness and zero elsewhere. The dual distance definition giveswhere the latter expression increases with $\ell$ for $a\ge 0$. Therefore the increasing-subsequence certificate concentration bound isIf the lower event has probability zero the conclusion is immediate.

Let $m$ be an integer median, so $\mathrm{Pr}(L\le m),\mathrm{Pr}(L\ge m)\ge 1/2$. Taking the two thresholds in the bound gives, for $t>0$,For $t>m$ the lower event is empty. In a nonempty sequence $m\ge 1$. Integration of these tails gives an explicit mean-median estimate: use $m+t\le 2m$ for $t\le m$ and $m+t\le 2t$ for $t\ge m$, obtainingWriting $\mu =\mathbb{E}L$, the median property also gives $m\le 2\mu$. Consequently, for a universal constant $C$, all $u\ge 0$ satisfyThus the subsequence length is concentrated near its mean on the scale $\sqrt{\mu }$, rather than the generic coordinate-exposure scale $\sqrt{n}$. This argument applies directly to finite-valued independent sequences. Independent continuous samples follow by refining finite coordinate discretizations; the strict-order pattern stabilizes almost surely when ties have probability zero. A uniform random permutation is the rank sequence of independent continuous samples, so it has the same subsequence-length concentration. Arbitrarily dependent random sequences are not covered by the product-space assumption.

Use discrete Shannon entropy with base-two logarithms. The standard facts needed are the chain rule for information entropy, conditioning reduces entropy, nonnegativity of conditional entropy, and the fact that a uniform distribution on $M$ outcomes has Shannon entropy ${\log }_{2}M$.

Order the coordinates by their indices and put $h_j=H(X_j\mid X_1,\dots ,X_{j-1})\ge 0$. Applying the chain rule within a coordinate subset $A$ and then adding the missing earlier conditioning coordinates givesOn summing over the family, coordinate $j$ occurs at least $k$ times. Since each $h_j$ is nonnegative,This proves Shearer's inequality without any independence assumption on the coordinates. For countable alphabets, apply the finite-valued assertion to refining finite coordinate partitions; the standard monotone approximation of Shannon entropy gives the same result with extended values. Differential entropy is not the Shannon entropy intended here.

For the graph application, let its bipartition be $U,V$, with degrees $a$ on $U$ and $b$ on $V$, where $a,b\ge 1$. Choose an independent set uniformly from all $i(G)$ such sets, and let $X$ be its vertex-indicator vector. Then $H(X)={\log }_{2}i(G)$. For $v\in V$ put $Y_v=X_{N(v)}$ and $q_v=\mathrm{Pr}(Y_v=0)$.

Each vertex of $U$ belongs to exactly $a$ of these neighbourhoods. Shearer's inequality therefore gives $H(X_U)\le a^{-1}{\sum }_{v\in V}H(Y_v)$. Conditional on $X_U$, a vertex of $V$ is forced absent if any neighbor was selected, and otherwise is a free fair binary choice. There are no edges within $V$, and the conditional independent-set distribution is uniform on all these free choices. Henceand

There are $2^b$ possible neighborhood patterns. Give the zero pattern weight $w_0=2^a$ and every other pattern weight one. For its distribution $(p_y)$, concavity of the logarithm, or Jensen's inequality, givesThis establishes the local weighted-entropy estimate rather than just counting neighborhood patterns.

Edge counting gives $a|U|=b|V|$; together with $|U|+|V|=n$, it yields $|V|/a=n/(a+b)$. Exponentiating the Shannon entropy estimate proves the independent-set bound for biregular graphs:The complete bipartite graph $K_{b,a}$ has exactly $2^a+2^b-1$ independent sets, since one chooses a subset of one side and subtracts the double-counted empty set. Disjoint unions of such components attain equality. If exactly one degree parameter is zero, edge counting forces the graph to be edgeless and the displayed bound equals $2^n$, so it remains valid. If $a=b=0$, the denominator is undefined; the edgeless graph has exactly $2^n$ independent sets.