Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B (Probabilistic Combinatorics)

For events $A_i$ with a dependency graph, assume each event is independent of the sigma-algebra generated by its nonneighbours. If numbers $x_i\in [0,1)$ satisfy $P(A_i)\le x_i{\prod }_{j\in \Gamma (i)}(1-x_j)$, the general Lovász local lemma givesThe symmetric version says that if every event has probability at most $q$, the dependency graph has maximum degree at most $d$, and $eq(d+1)\le 1$, then none occurs with positive probability. For $d\ge 1$, set $x_i=1/(d+1)$. Since $(1-1/(d+1){)}^d\ge e^{-1}$, the general condition follows from the symmetric numerical hypothesis. The logarithmic inequality $\log (1+1/d)\le 1/d$ proves that estimate. When $d=0$, the events are mutually independent and each has probability below one, so the conclusion is immediate. This is the intended implication from the general to the symmetric form; the source repeats the word symmetric in its final clause.

Assign each vertex a color independently and uniformly from the five available residues. Let $A_v$ be the event that none of its neighbours has the successor color. Conditional on the color of $v$, its $r$ neighbours all avoid that color with probability $(4/5{)}^r$, so $P(A_v)=(4/5{)}^r$.

The event only uses colors in the closed neighbourhood of $v$. Events based on disjoint such sets are jointly independent. A closed neighbourhood can intersect another only when the two centres are at distance at most two, giving dependency degree at most $r+r(r-1)=r^2$. For sufficiently large $r$,The symmetric local lemma therefore supplies a color assignment with no bad event, proving every vertex has a neighbour of the successor color. As defined in the question, this is a five-color assignment; it is not required to be a proper vertex coloring of every edge, which would be impossible for some large regular graphs.

The construction generalizes to cyclic successor colorings of regular graphs.

From every vertex choose one neighbour of the successor color and follow these choices. The finite directed graph with one chosen outgoing edge per vertex contains a directed cycle. Its vertices are distinct until the first repeated vertex. Each step increases the color by one modulo five, so returning to the starting vertex requires the cycle length to be divisible by five. It therefore has length at least five and is also a cycle in the underlying graph. This proves a cycle of length a positive multiple of five exists.

For a variable $Z$ of finite variance and $t>0$, Chebyshev's inequality isOn that event, $(Z-EZ{)}^2\ge t^2$. Thus $t^{2}P(|Z-EZ|\ge t)\le E[(Z-EZ{)}^2]$, proving the assertion. Equivalently apply Markov's inequality to the squared deviation.

Assume $EX>0$, as required by the denominators. Since each indicator has variance at most its expectation, and independent event pairs have zero covariance,The sum uses ordered pairs, matching the covariance expansion. Chebyshev's inequality now givesIf $EX=0$, $X=0$ almost surely and the divided expression is not the useful form of the bound.

Let $X$ count the four-vertex sets spanning a clique. Its expectation is $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^6$. If $p\ll n^{-2/3}$, then $\mu \to 0$ and Markov's inequality gives $P(X>0)\to 0$.

Now suppose $p\gg n^{-2/3}$. Then $\mu \to \infty$. Two distinct clique indicators are independent unless their vertex sets share at least two vertices. An overlap of two vertices gives $O(n^6)$ ordered pairs requiring eleven distinct edges; an overlap of three gives $O(n^5)$ pairs requiring nine edges. ConsequentlyThe preceding second-moment bound therefore gives $P(X=0)\to 0$. Thusis a threshold for the appearance of a four-clique. Sharing just one vertex creates no dependence because the two edge sets are disjoint.

Realize the random graph process by giving every edge an independent uniform arrival time. For a fixed four-set $S$, only its six internal edges and its $4(n-4)$ outgoing edges affect whether it is an isolated clique. It is an isolated clique at some time exactly when all six internal edges arrive before every outgoing edge.

The relative ordering of these $4n-10$ edges is uniform. The chance that the first six are exactly the six internal edges is ${\left(\genfrac{}{}{0ex}{}{4n-10}{6}\right)}^{-1}$. A union bound over the possible vertex sets givesEdges entirely outside $S$ are irrelevant. Counting the whole arrival-order event avoids an invalid union over continuously many times.

This is an example of isolated clique appearance in a uniform random graph process.

Explore the component of one vertex by processing discovered vertices in order. At each step, the number of newly discovered neighbours is a binomial variable with at most $n$ trials and success probability $1/(2n)$, on previously unexposed independent edges. Pad each step with independent dummy trials. This couples the exploration below independent offspring variables ${\xi }_i\sim \mathrm{Bin}(n,1/(2n))$, each of mean one half.

If the component has at least $k\ge 2$ vertices, after $k-1$ vertices have been processed at least $k-1$ offspring must have been found. HenceThe sum is binomial with mean $\mu =(k-1)/2$. The multiplicative Chernoff inequality $P(B\ge 2\mu )\le (e/4{)}^{\mu }$ therefore givesA union bound over all vertices bounds the probability of any component of size at least $k$ by $n{e}^{-c(k-1)}$. Taking $k=\lceil \alpha {\log }_{e}n\rceil$ with any $\alpha >1/c$, for example ten, makes this tend to zero. Thus the largest component is at most a constant times $\log n$ with high probability.

Every vertex in the component can be reached from $v$ by a simple path. The number of potential length-$\ell$ simple paths beginning at $v$ is at most $n^{\ell }$, and each has probability $(1/(2n){)}^{\ell }$ of being present. Counting such paths may count a vertex more than once, so it gives an upper bound on the expected number of reached vertices:Thus $\boxed{K=2}$ works for every $n$. Equivalently the dominating branching process has mean offspring one half and expected total progeny two.

On this product, use the Hamming metric $d(x,y)=|\{i:x_i\ne y_i\}|$. The relevant Lipschitz condition is $|f(x)-f(y)|\le d(x,y)$, equivalently changing any one coordinate changes the function by at most one. More generally an $L$-Lipschitz function has bound $Ld(x,y)$. The unit version is the bounded-differences condition used below.

Azuma's inequality states that if $(M_i{)}_{i=0}^m$ is a martingale with $|M_i-M_{i-1}|\le 1$ almost surely, then for $t\ge 0$,For independent product coordinates $Z_1,\dots ,Z_m$, expose them successively and set $M_i=E[f(Z)\mid Z_1,\dots ,Z_i]$. If changing one coordinate changes $f$ by at most one, the possible conditional means at that exposure have diameter at most one, by averaging the same remaining independent coordinates. Therefore the martingale increments have absolute value at most one. It follows thatFor coordinate bounds $c_i$, the same argument gives denominator $2{\sum }_i{c}_i^2$. The argument extends to arbitrary independent measurable coordinates for an integrable function with these bounds, rather than requiring finite state sets.

The union area is a bounded measurable function of the centres, with $0\le X\le n\pi$. Fix all centres except one, and let $B$ be the union of the fixed disks. Replacing the remaining disk $D$ changes the area to $|B|+|D\setminus B|$. The second term always lies in $[0,\pi ]$, so the area changes by at most $\pi$, not merely by the weaker bound $2\pi$.

Thus $X/\pi$ has coordinate differences at most one for the $n$ independent centres. The preceding martingale bound givesOne may take $c=1/(2{\pi }^2)$, independently of all centre distributions. Boundedness of the area ensures the conditional expectations exist even when the centre locations have no finite moments.

For $i=1,\dots ,n-1$, make one block from the edge weights $\{X_{ij}:j>i\}$. These $n-1$ blocks are independent because they contain disjoint edges. Changing one whole block only changes weights of edges incident with vertex $i$. Every matching contains at most one such edge, so its total weight changes by at most one. Comparing an old optimal matching in the new weights and a new optimal matching in the old weights proves that the maximum matching weight also changes by at most one.

Apply the bounded-differences martingale argument to these $n-1$ blocks, givingExposing each edge separately would give a weaker quadratic-in-$n$ denominator. The grouped exposure is what supplies the requested linear denominator. The proof needs only independent weights in $[0,1]$, not identical uniform laws. For $n=1$, the matching weight is deterministically zero; the divided formula is intended for $n\ge 2$.

The general grouping argument is vertex-block concentration of maximum matching weight.