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

Expose the vertices in order, revealing at step $i$ every edge from vertex $i$ to an earlier vertex. With the resulting filtration ${\mathcal{F}}_i$, putThis is the vertex exposure for chromatic number martingale. Its increments $D_i=M_i-M_{i-1}$ have conditional mean zero and satisfy $|D_i|\le 1$, by the permitted Lipschitz condition.

Here is the required exponential-moment proof of the Azuma-Hoeffding inequality. More generally, suppose $|D_i|\le c_i$ for deterministic $c_i$. Convexity of the exponential function gives, for $-c_i\le d\le c_i$,Taking conditional expectation and using the zero conditional mean yieldsFor the last inequality, integrate $(\log \cosh u{)}^{\prime }=\tanh u\le u$ for $u\ge 0$, and use evenness. A zero $c_i$ simply means a zero increment. Iterated conditional expectation now givesFor $s,t>0$, the strict Markov bound on the event $M_n-M_0>s$ givesThe strict inequality follows directly by integrating $e^{t(M_n-M_0)}>e^{ts}$ on that event; it is also immediate if the event is empty. Optimize at $t=s/{\sum }_i{c}_i^2$ and apply the same argument to the negative increments. For $c_i=1$ and $s=\lambda \sqrt{n}$, the union bound proves, for every $\lambda >0$,At $\lambda =0$ the displayed strict bound is trivial.

For the second conclusion write $a_n=n/\log n$ and choose a fixed $C>\sqrt{2\log 10}$. If $\mu \ge a_n+C\sqrt{n}$, then $\{\chi (G)<a_n\}\subseteq \{\chi (G)-\mu <-C\sqrt{n}\}$, whose probability is less than $e^{-C^2/2}<1/10$. Thus the given positive probability forces $\mu <a_n+C\sqrt{n}$. For sufficiently large $n$,Here the non-strict one-sided bound follows by the usual non-strict Markov inequality. Consequently the asserted upper bound holds with high probability, uniformly over any sequence $p=p(n)$ satisfying the stated assumption.

We use the random alteration method, controlling large hypergraph independent sets and then removing the few forbidden overlaps. Fix $k=2005$, let $n$ tend to infinity, and independently include each three-element subset of an $n$-vertex set as an hypergraph edge with probability $p=n^{-7/4}$. Call the resulting three-uniform hypergraph $H_0$, and let $s=\lceil n/(2k)\rceil$.

For any prescribed $s$-vertex set, the probability that it is a hypergraph independent set is $(1-p{)}^{\left(\genfrac{}{}{0ex}{}{s}{3}\right)}$. Hence the union bound givesbecause $p\left(\genfrac{}{}{0ex}{}{s}{3}\right)$ has order $n^{5/4}$, with a positive constant depending only on $k$.

Let $Y$ count unordered pairs of distinct hypergraph edges meeting in two vertices. Each potential pair consists of its common pair and two distinct additional vertices, soThe Markov inequality implies $\mathbb{P}(Y\ge n/2)=O(n^{-1/2})$. We may therefore fix one realization for which $Y<n/2$ and no $s$-vertex hypergraph independent set exists. For each offending hypergraph edge pair choose one vertex from its union, and let $D$ be the set of all chosen vertices. Delete $D$, together with all incident hypergraph edges, and call the induced hypergraph $H$. Then $|D|\le Y<n/2$, so $N=|V(H)|>n/2$. The next two parts verify both desired properties of this same $H$.

Every hypergraph independent set in the induced hypergraph $H$ is also a hypergraph independent set in $H_0$. Thus its maximum independent-set size is at most $s-1<n/(2k)<N/k$. In any proper hypergraph colouring with at most $k$ colours, one colour class would have at least $N/k$ vertices, contradicting that bound. ThereforeThis is the weak hypergraph colouring convention: an hypergraph edge may use two colours, but it may not be monochromatic.

If two distinct hypergraph edges survived in $H$ and shared two vertices, they were an offending pair in $H_0$. The deletion set $D$ contains a chosen vertex from their union, so at least one of those hypergraph edges could not have survived. This contradiction proves that $H$ is a linear hypergraph. Deleting vertices leaves every surviving hypergraph edge of size three, so the construction meets the uniformity requirement as well as the chromatic-number requirement.

Colour every vertex independently red or blue, each with probability $1/2$. A fixed $r$-element hypergraph edge is monochromatic with probability $2^{1-r}$. If there are $m<2^{r-1}$ hypergraph edges, the expected number of monochromatic hypergraph edges is $m{2}^{1-r}<1$. Equivalently, the union bound says that the probability of even one monochromatic hypergraph edge is less than one. A proper two-colouring therefore exists.

For the converse, suppose $r\ge 2$, put $N=2r^2$, and sample $m$ independent uniformly random $r$-subsets of an $N$-vertex set. Initially this is a multihypergraph. For a fixed two-colouring with $a$ red vertices, a sampled hypergraph edge is monochromatic with probabilityThe numerator is minimized by $a=N/2=r^2$. To see this discretely, use $\left(\genfrac{}{}{0ex}{}{a+1}{r}\right)-\left(\genfrac{}{}{0ex}{}{a}{r}\right)=\left(\genfrac{}{}{0ex}{}{a}{r-1}\right)$: the successive difference of the numerator is $\left(\genfrac{}{}{0ex}{}{a}{r-1}\right)-\left(\genfrac{}{}{0ex}{}{N-a-1}{r-1}\right)$, negative up to the middle and positive afterwards. Binomial coefficients with an upper index below $r$ are understood as zero.

For this balanced colouring,The elementary inequality ${\prod }_j(1-u_j)\ge 1-{\sum }_j{u}_j$, valid for $0\le u_j\le 1$, givesThus any fixed colouring is proper for all the sampled hypergraph edges with probability at most $e^{-m{2}^{-r}}$. There are $2^N$ colourings, so chooseA union bound makes the probability that any proper colouring exists at most $2^N{e}^{-m{2}^{-r}}\le e^{-1}<1$. Some sampled multihypergraph is consequently not two-colourable. Remove repeated copies of its hypergraph edges: this changes neither which colourings are proper nor non-two-colourability, and leaves at most $m$ distinct hypergraph edges. We have provedFor $r=1$, one singleton hypergraph edge is already not two-colourable, so that endpoint causes no exception.

Let $Y$ be the number of isolated vertices and set $\lambda =e^{-c}$. For fixed $k\ge 1$, the falling factorial $(Y{)}_k$ counts ordered $k$-tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are $k(n-k)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ such edges, soSince $np=\log n+c$ and $n{p}^2=o(1)$, taking logarithms givesThus every fixed factorial moment tends to ${\lambda }^k$. We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to ${\lambda }^k$ converge in distribution to $\mathrm{Poisson}(\lambda )$. Consequently $Y$ has that limiting distribution, and its mass at each fixed integer converges. In particular,This establishes the limiting probability of at least one isolated vertex, rather than merely a bound based on its expectation.

The factorial-moment argument above gives $Y\Rightarrow \mathrm{Poisson}(\lambda )$ with $\lambda =e^{-c}$. Because $Y$ is integer-valued, apply convergence in distribution at the continuity points $3/2$ and $5/2$ and subtract. This proves

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

For the unheaded degree-one continuation, write $X={\sum }_{v=1}^n{I}_v$, where $I_v$ indicates that vertex $v$ has degree one. Withwe haveFor distinct vertices $u,v$, separate the cases where their connecting edge is present or absent. If it is present, all their other incident edges must be absent. If it is absent, each vertex chooses its unique neighbour among the other $n-2$ vertices; those two neighbours may coincide. The respective edge constraints are independent even in that case. ThusDividing by $q^2$ gives the exact ratioThe first term tends to zero because $(n-1{)}^{2}p$ has order $n\log n$; the second tends to one. Consequently its variance satisfiesThe Chebyshev inequality now yields $\mathbb{P}(X=0)\le \mathrm{Var}X/(\mathbb{E}X{)}^2\to 0$. A vertex of degree one exists with high probability, even though the limiting probability of having an isolated vertex is strictly between zero and one.

The general, or asymmetric Lovász local lemma, is as follows. Let $E_1,\dots ,E_m$ be events, with a dependency graph of events having neighbour sets $N(i)$. Each $E_i$ must be independent of the sigma-algebra generated by all the events indexed by its nonneighbours. If numbers $0\le x_i<1$ satisfythenFor completeness, the key inductive bound is $\mathbb{P}(E_i\mid {\bigcap }_{j\in S}{E}_j^c)\le x_i$ whenever $i\notin S$. Split $S$ into neighbours $S_1$ of $i$ and nonneighbours $S_2$. If $S_1$ is empty, the dependency condition gives the bound directly. Otherwise,The denominator bound follows by exposing the exclusions in $S_1$ one at a time and using the induction hypothesis with strictly fewer conditioning events. The same induction ensures that all conditioning events have positive probability. Finally multiply the successive conditional probabilities of avoiding $E_1,\dots ,E_m$ to obtain the stated lower bound.

For the symmetric form, suppose each event has probability at most $q$ and the dependency graph has maximum degree $D\ge 1$. Choose $x_i=1/(D+1)$. ThenThe final inequality follows from $(1+1/D{)}^D\le e$. Thus $eq(D+1)\le 1$ suffices for positive probability that no bad event occurs. If $D=0$, the dependency condition gives joint independence and the same criterion implies $q<1$, so the conclusion follows directly.

Apply this to a fair independent two-colouring of the hypergraph vertices, with $E_W$ the event that hypergraph edge $W$ is monochromatic. Its probability is $q=2^{1-r}$. Events on disjoint hypergraph edges use disjoint independent variables, giving a dependency graph by joining intersecting hypergraph edges. Each hypergraph edge meets at mostother hypergraph edges; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\le r(\Delta +1)$ is enough for the printed condition. Indeed,The symmetric Lovász local lemma therefore gives a proper two-colouring. A hypergraph with no hypergraph edges is trivially colourable and needs no dependency calculation.

Let $S$ be the number of red vertices in $W$. It has a binomial distribution with parameters $r$ and $1/2$, so independence givesFor $t=1$, the strict inequality $\log \cosh (1/2)<1/8$ follows by integrating $\tanh u<u$ for $u>0$. Hence the exponential Markov bound yieldsThereforeThis supplies the tail estimate directly, including the strict constant in the requested bound.

For each hypergraph edge $W$, let $B_W$ be the event that one of its two colours occupies more than $3r/4$ vertices. By colour symmetry and the union bound, the preceding calculation givesAgain the dependency graph joins intersecting hypergraph edges and has $D+1\le r(\Delta +1)$. The assumed degree bound impliesThe symmetric Lovász local lemma gives positive probability that no $B_W$ occurs. Thus there is a two-colouring in which each colour occupies at most $3r/4$ vertices of every hypergraph edge. Equivalently, both colour counts in every hypergraph edge lie between $r/4$ and $3r/4$; no rounding difficulty arises because the counts are integers and the bad events use strict inequalities.

We prove both inequalities, including the BK inequality, for the inhomogeneous product measure in the question. Identify a configuration with its set of coordinates equal to one. An up-set is then an increasing event. For an increasing event $A$, a set $S$ of open coordinates is a witness if the configuration with precisely $S$ open belongs to $A$: upward closure ensures that those coordinates alone force $A$, whatever the remaining coordinates do. The event $A\square B$ means that there are disjoint open witnesses $S,T$ for $A,B$ respectively.

First prove the Harris' inequality by induction on the number of coordinates. For the last coordinate, of parameter $p$, write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for the two sections in the remaining coordinates, and put $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$. Induction applied to each section givesSubtract the product of the marginal probabilities from the right-hand side:The base case of zero coordinates is immediate. Thus

For disjoint occurrence, first assume every coordinate parameter is at most $1/2$, and again use induction. Put $c_{ij}=\mathbb{P}(A_i\square B_j)$ on the remaining coordinates. The zero-section of $A\square B$ is exactly $A_0\square B_0$. The one-section is exactlyIndeed, the last open coordinate can belong to at most one of two disjoint witnesses. Assigning it to the $A$ witness leaves a witness for $A_1$ and a witness for $B_0$; assigning it to the $B$ witness gives the other event. If neither witness uses it, both descriptions still hold. Conversely, witnesses for either displayed event lift to disjoint witnesses by adding the last coordinate only to the appropriate one.

The intersection of the two displayed events contains $A_0\square B_0$, because the sections are increasing. ThereforeThe coefficient $1-2p$ is nonnegative. Applying the induction hypothesis to each term givesThe product of the marginal probabilities is exactly this last expression plusThis proves the desired inequality whenever every parameter is at most $1/2$.

To remove that restriction, suppose first $p_i<1$ for every coordinate. Replace coordinate $i$ by the logical disjunction of $m_i$ independent Bernoulli bits, each with parameterChoose $m_i$ large enough that $q_i\le 1/2$. Different blocks are independent, and their OR values have exactly the original distribution. Let $\tilde{A},\tilde{B}$ be the inverse images of $A,B$ under this block-OR map; they are increasing events. If the OR configuration has disjoint witnesses $S,T$, choose one open bit from each block indexed by $S$ or $T$. The bits chosen for $S$ force $\tilde{A}$, those for $T$ force $\tilde{B}$, and the two bit sets are disjoint. Thus the inverse image of $A\square B$ is contained in $\tilde{A}\square \tilde{B}$. The small-parameter result provesParameters equal to one follow by a limit: probabilities of any fixed event on a finite cube are polynomials in the coordinate parameters, hence continuous. Zero parameters already cause no difficulty. We have obtained

For the graph application, take coordinates to be the edges of the complete graph. Let $A$ be the increasing event that $x$ is connected by a graph path to $U$, and $B$ the corresponding event for $W$. Their probabilities are $\alpha ,\beta$. A simple graph path from $U$ to $W$ through $x$ splits at $x$ into two graph paths with disjoint edge sets. Those sets witness $A$ and $B$, so this graph path event is contained in $A\square B$. The BK inequality givesOn the other hand, if both $A$ and $B$ occur, concatenate an $x$-to-$U$ graph path and an $x$-to-$W$ graph path to obtain a walk from $U$ to $W$. Removing loops yields a simple graph path, although it need not pass through $x$. Thus $A\cap B$ is contained in the unrestricted connection event, and the Harris' inequality givesThe distinction between a simple graph path through $x$ and an unrestricted connection is essential: a walk may revisit an edge, so a through-$x$ walk would not in general provide disjoint witnesses.