Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 (C11.1, DMAC 2485, DMCO 2485, DMPC 2485, DMSU 2485)

Graph Theory and Probabilistic Combinatorics, Friday 4 June 2010, 9.30am–12.30pm. This combined Part C paper was supplied through the past-papers disclosure, in original Part C bundle pages 378–381. Both printed sections are covered here; the private editable transcription retains all four pages and the complete cover. No exact worked-answer advertisement was found in the bounded availability check.

For a nonnegative integer $q$, the chromatic polynomial $p_G(q)$ counts the proper vertex colourings of $G$ using a fixed set of $q$ colours. In a proper colouring, the endpoints of every edge have different colours. The counting function extends uniquely to a polynomial, as follows either from the recurrence below with the edgeless base case $p_G(x)=x^{|V(G)|}$ or from inclusion-exclusion.

Let $e=uv$. Every proper colouring of $G-e$ falls into exactly one of two classes. If $u$ and $v$ have different colours, it is a proper colouring of $G$. If they have the same colour, identifying $u$ and $v$ gives a proper colouring of the contracted graph $G/e$, and this correspondence is bijective. Parallel edges produced by contraction impose identical conditions and can be suppressed. Hence, at every nonnegative integer $q$,Since polynomials agreeing at infinitely many values agree identically, the deletion-contraction recurrence for the chromatic polynomial isThroughout, the graphs are finite and simple, as in the usual convention for these statements.

Induct on the number of edges, allowing coefficients outside the displayed degree range to be zero. An edgeless graph has $p_G(x)=x^n$, so its leading coefficient is $1$ and all others are zero. For an edge $e$, write the alternating coefficients of $G-e$ as $b_i$ and those of the simplified contraction $G/e$ as $c_i$. The deletion-contraction recurrence for the chromatic polynomial giveswith $c_{-1}=0$. Both smaller graphs have fewer edges, so induction gives nonnegative coefficients $b_i,c_i$. Thus $a_i=b_i+c_{i-1}\ge 0$. Moreover $a_0=b_0=1$ andFor a graph with at least one vertex, $p_G(0)=0$, so the constant term vanishes. ThereforeIn the one-vertex case, the coefficient of $x^{n-1}$ is simply zero; this is the same $a_1=m=0$ convention beyond the written summation range.

An inclusion-exclusion proof gives the coefficients directly. For an edge set $F\subseteq E(G)$, let $c(F)$ be the number of connected components of the spanning graph $(V(G),F)$, including isolated vertices. Requiring the two endpoints of every edge of $F$ to have the same colour leaves exactly $x^{c(F)}$ colourings. Thus the chromatic polynomial inclusion-exclusion formula isConsider a term with $n-c(F)=i\le k-2$. If $(V(G),F)$ contained a cycle, that cycle would have length at least $k$. The component containing it would have at least $k$ vertices and hence contribute at least $k-1$ to $n-c(F)$, a contradiction. Therefore $F$ is a forest. For a forest, $n-c(F)=|F|$, so necessarily $|F|=i$.

Conversely, every $i$-element edge set with $i\le k-2$ is a forest, since a cycle would require at least $k$ edges. Thus exactly $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ edge sets contribute to the coefficient of $x^{n-i}$, and they all have sign $(-1{)}^i$. ConsequentlyThis proves girth determines initial chromatic coefficients without requiring the suggested double induction.

The Ramsey number $R(s,t)$ is the smallest integer $N$ such that every red-blue colouring of the edges of $K_N$ has a red $K_s$ or a blue $K_t$. Equivalently, every graph on $N$ vertices contains a clique of size $s$ or an independent set of size $t$.

Set $R(1,t)=R(s,1)=1$. For $s,t\ge 2$, let $N=R(s-1,t)+R(s,t-1)$ and fix a vertex $v$ in a red-blue colouring of $K_N$. Among the remaining $N-1$ vertices, either at least $R(s-1,t)$ are red neighbors of $v$, or at least $R(s,t-1)$ are blue neighbors. In the first case their induced colouring gives a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. This proves the Ramsey number recursionInduction on $s+t$, using the boundary values and Pascal's identity, now gives the binomial upper bound for a Ramsey number:In particular this induction proves that the required Ramsey number exists.

Colour the edge $ij$ of the complete graph on $\{1,\dots ,6\}$ by the class containing $|j-i|$. Part (a) gives $R(3,3)\le 6$, so there is a monochromatic triangle with vertices $i<j<k$. Its three edge differences areThey are positive integers in one class. Hence every two-colouring of the positive integers has a monochromatic solution of $x+y=z$. This is the two-colour Schur theorem. The two summands need not be distinct.

No. Colour the positive integers by alternating dyadic blocks:Every positive integer $x$ and its double $2x$ have opposite colours. A nonempty set closed under addition contains both $x$ and $x+x=2x$, so no such set can lie in one class. In particular there is no infinite monochromatic additive subsemigroup.

The suggested arithmetic-progression argument gives another way to see the obstruction. If $a\in S$ and $S$ is closed under addition, then $a,2a,3a,\dots$ all lie in $S$. But every infinite arithmetic progression of positive step $d$ meets every sufficiently long dyadic block, because a block of at least $d$ consecutive integers contains a representative of the progression's residue class. Both colours contain arbitrarily long blocks, so neither colour contains an infinite arithmetic progression.

Hall's marriage theorem states that a finite bipartite graph with vertex classes $X,Y$ has a matching covering $X$ if and only ifNecessity follows because the matched neighbors of the vertices in $S$ are distinct members of $N(S)$.

For sufficiency, induct on $|X|$. The empty case is immediate. First suppose there is a nonempty proper subset $S\subset X$ with $|N(S)|=|S|$. The induced graph between $S$ and $N(S)$ satisfies Hall's condition, so induction matches $S$. In the remaining graph between $X\setminus S$ and $Y\setminus N(S)$, every $T\subseteq X\setminus S$ satisfiesInduction matches the rest, and the two matchings are disjoint.

Otherwise every nonempty proper $S\subset X$ has $|N(S)|\ge |S|+1$. Choose any edge $xy$, which exists by Hall's condition if $X$ is nonempty. Delete $x$ and $y$. Every nonempty subset of $X\setminus \{x\}$ loses at most one neighbor and therefore still satisfies Hall's condition. Induction provides a matching of this smaller graph; append $xy$. If $|X|=1$, choosing its neighbor already completes the argument. This proves the theorem.

For disjoint nonempty vertex sets $X,Y$, let $e(X,Y)$ count edges with one endpoint in each. Their density isFor $0<ϵ<1$, the pair is a regular pair of vertex sets if all $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfyUsing the convention with a strict bound less than $ϵ$ instead gives the same argument below; the assumed density is strictly larger than $ϵ$.

Verify Hall's marriage theorem. Let $S\subseteq X$; the empty case is immediate. If $0<|S|\le ϵn$, any $x\in S$ has at least $ϵn$ neighbors in $Y$, so $|N(S)|\ge |S|$.

Next suppose $ϵn<|S|\le (1-ϵ)n$. If $|N(S)|<|S|$, then $T=Y\setminus N(S)$ has $|T|>n-|S|\ge ϵn$. There are no edges between $S$ and $T$, so $d(S,T)=0$. But the regularity assumption impliesa contradiction.

Finally, if $|S|>(1-ϵ)n$, then $|X\setminus S|<ϵn$. Every $y\in Y$ has at least $ϵn$ neighbors in $X$, so at least one of them lies in $S$. Thus $N(S)=Y$ and $|N(S)|=n\ge |S|$.

All possible sizes of $S$ are covered, even if the middle range is empty. Hall's condition holds, so there is a perfect matching between $X$ and $Y$. This is the perfect matching criterion for a regular pair with minimum degree.

For a nonnegative random variable $Y$ and $a>0$, Markov inequality statesFor a random variable $X$ of finite mean $\mu$ and variance ${\sigma }^2$, Chebyshev inequality states that for every $t>0$,To prove it, apply Markov inequality to the nonnegative variable $(X-\mu {)}^2$ at threshold $t^2$:

For an indicator $I_i$, $\mathrm{Var}(I_i)=P(A_i)(1-P(A_i))\le P(A_i)$. Covariances vanish for independent pairs. For dependent distinct pairs,Expanding the variance, with ordered pairs as in the definition of $\Delta$, givesFor sufficiently large $n$, ${\mu }_n>0$. By Chebyshev inequality,This is the second moment method: a vanishing relative variance makes a zero count unlikely.

A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.

Start the Galton-Watson process with one ancestor, $Z_0=1$, and let every individual independently have a number of offspring distributed as $Z$. With independent copies $Z_{t,j}$,where an empty sum is zero. Extinction is the event that some generation is empty; zero is then absorbing. Write $q$ for its probability and $1-q$ for the survival probability.

Set $q_t=P(Z_t=0)$, with $q_0=0$. Conditional on the ancestor's number of children, extinction by generation $t+1$ requires independent extinction by generation $t$ in every child subtree. ThusThe events $\{Z_t=0\}$ increase, so $q_t\uparrow q$. The probability generating function is continuous on $[0,1]$, by domination of $s^Z$ by $1$, giving $q=f_Z(q)$. If $r\in [0,1]$ is any fixed point, then $q_0=0\le r$ and monotonicity of $f_Z$ inductively gives $q_t\le r$. Taking limits proves the Galton-Watson extinction fixed point characterization:In particular it is the smallest nonnegative fixed point wherever the generating series is defined, since it already lies in $[0,1]$.

Let $m=\mathbb{E}Z=f_Z^{\prime }(1-)$, allowing $m=\infty$. The probability generating function is increasing and convex, with $f_Z(1)=1$. If $m<1$, its tangent inequality gives $f_Z(s)\ge 1+m(s-1)>s$ for $s<1$, so $q=1$. If $m=1$ and $P(Z=1)\ne 1$, there is positive mass at both zero and some integer at least two; strict convexity gives $f_Z(s)>s$ for $s<1$, again $q=1$. The exceptional case $Z=1$ almost surely has one individual forever, so $q=0$ despite $m=1$.

If $m>1$, the left derivative at $1$ gives $f_Z(s)-s<0$ for $s<1$ sufficiently close to $1$. Since $f_Z(0)\ge 0$, continuity supplies a fixed point below $1$, possibly $0$. Thus survival has positive probability precisely when $m>1$, apart from deterministic one-child reproduction.

For the random bipartite graph, early exploration of a component alternates between the two vertex classes. Before many vertices are exposed, each discovered vertex has approximately $\mathrm{Poisson}(c)$ new neighbors in the other class, since $\mathrm{Bin}(n-O(1),c/n)$ tends to that distribution. The two-type mean offspring matrix iswith spectral radius $c$; equivalently, the mean growth over two generations is $c^2$. The branching-process comparison therefore predicts a giant component exactly whenFor $c\le 1$, the local process dies out almost surely, so no linear-sized component is expected; $c=1$ is the critical case, not a positive-survival exception. For $c>1$, the symmetric survival probability is $1-q>0$, where $q=e^{c(q-1)}$, predicting approximately $2n(1-q)$ vertices in the giant. This last passage from local survival to a unique giant is the usual random-graph exploration argument; the branching-process reasoning here supplies the requested threshold explanation rather than a proof of that global theorem.

First take $0<p<1$. For $X\sim \mathrm{Bin}(n,p)$, independence of the Bernoulli trials givesFor $x\ge p$ and $t>0$, Markov inequality yieldsDifferentiate the logarithm of the right-hand side to minimize it. The stationary point satisfieswhich is at least $1$ when $x\ge p$. Substitution givesWhen $x=p$, use the limit $t_{\ast }\to 0$, giving the trivial bound $1$.

For $x\le p$, take $t<0$. On $\{X\le nx\}$ we have $e^{tX}\ge e^{tnx}$, so the same Markov inequality gives the same expression. Its minimizing $t_{\ast }$ is now nonpositive, yielding the stated lower-tail bound. No rounding of $nx$ is needed, because the exponential event inclusion holds for real thresholds. The cases $p=0$ and $p=1$ are deterministic and follow directly, or by the corresponding limits.

Write the bound in part (a) as $e^{-nD(x\Vert p)}$, where the Bernoulli Kullback-Leibler divergence with natural logarithms isFor fixed $p\in (0,1)$, $D(p\Vert p)=0$, its first derivative with respect to $x$ vanishes at $p$, andIntegrating this lower bound twice, on either side of $p$, gives the Bernoulli relative entropy lower bound $D(x\Vert p)\ge 2(x-p{)}^2$. Apply the two tails from part (a) at $x=p+h$ and $x=p-h$ and use the union bound:A tail with threshold outside $[0,1]$ is empty; thresholds at the endpoints follow by continuity of the bound. For $h=0$ the right-hand side is $2$, so the assertion is immediate. This is the binomial form of Hoeffding inequality.

The sum of the first $n/2$ variables has distribution $\mathrm{Bin}(n/2,1/2)$. For any fixed half-circle interval $I$, putThe $n$ terms defining $Z_I$ are independent Bernoulli variables of parameter $1/2$, so $Z_I\sim \mathrm{Bin}(n,1/2)$ and $D_I=Z_I-n/2$. Part (b), with $h=w/n$, givesThere are at most $n$ cyclic intervals of length $n/2$; this also covers the non-wrapping interpretation in the question. They need not be independent, since the union bound always applies. HenceWith $w=c\sqrt{n\log n}$ and natural logarithms, this becomes $2n^{1-2c^2}$, which tends to zero for every $c>1/\sqrt{2}$. In particular,The argument proves uniform half-circle balance for independent Bernoulli variables. It improves on separately bounding the two half sums by recognizing the difference as one centered binomial variable.