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

Graph Theory and Probabilistic Combinatorics, Mathematics Part C and Mathematics and Statistics Part C; Friday 1 June 2007, 9.30am–12.30pm. The full five-page source and both sections are privately transcribed from original Part C bundle pages 81–85, supplied through the past-papers disclosure. No exact worked-answer advertisement was found in the bounded availability check.

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because the distinct matched partners of $S$ belong to $N(S)$.

For sufficiency take a maximum matching. If it leaves $x\in L$ unmatched, explore alternating paths starting at $x$, traversing unmatched edges from left to right and matched edges back to the left. No reached right vertex can be unmatched, since flipping the edges of such an alternating path would augment the matching. Let $S,T$ be the reached left and right sets. Every neighbour of $S$ lies in $T$: unmatched edges are explored, and a matched edge from a reached left vertex leads to its already reached predecessor. Conversely every member of $T$ is a neighbour of $S$. Their matched partners are exactly $S\setminus \{x\}$, so $|N(S)|=|T|=|S|-1$, contradicting the hypothesis. Thus a matching covering $L$ exists.

If no complete matching exists, Hall's theorem gives a nonempty $S\subseteq V_1$, of size $k$, with $|N(S)|\le k-1$. The pairs between $S$ and $V_2\setminus N(S)$ must be nonedges, so there are at leastmissing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore a complete matching exists.

The strictness is necessary: isolate one vertex of $V_1$ and put all edges between the remaining $n-1$ left vertices and all $n$ right vertices. There are exactly $n(n-1)$ edges and no matching can cover the isolated vertex. This also handles $n=1$.

First the graph is connected: every component has at least $\delta (G)+1>n/2$ vertices, so two components cannot fit. Take a longest path $v_1,\dots ,v_k$. Every neighbour of either endpoint lies on that path. In the index set $\{1,\dots ,k-1\}$ defineTheir sizes sum to $d(v_1)+d(v_k)\ge n>k-1$, so they share an index $i$. The edges at that index give the cyclecontaining every vertex of the path. The minimum-degree assumption and $n\ge 3$ ensure the resulting cycle is nondegenerate. If it omitted any graph vertex, connectedness would supply an edge from outside it to the cycle. Starting with that outside vertex and then following the cycle without closing it gives a path with $k+1$ vertices, contradicting maximality. Thus the cycle is Hamiltonian. This proves Dirac's theorem in the required case.

For a positive integer $x$, the chromatic polynomial $p_G(x)$ counts proper vertex colorings from a palette of $x$ labelled colors, where adjacent vertices must have different colors. The counting function agrees with a polynomial, as proved by deletion-contraction in the next part.

For an edge $e=uv$, colorings of $G-e$ divide into those giving $u,v$ different colors, counted by $p_G$, and those giving them the same color, counted by $p_{G/e}$. Parallel edges produced by contraction may be suppressed. ThusFor an edgeless graph on $n\ge 1$ vertices, $p_G=x^n$. Induct on the number of edges, allowing smaller vertex counts for contractions. If both smaller expansions have alternating nonnegative coefficients, the contraction's leading degree is one lower, so subtracting it giveswith absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion isThis induction simultaneously proves the counting function is a polynomial.

For a triangle, $p_{C_3}=x(x-1)(x-2)=(x-1{)}^3-(x-1)$. For $n\ge 4$, deleting an edge leaves a path with polynomial $x(x-1{)}^{n-1}$, and contracting it leaves $C_{n-1}$. Deletion-contraction and induction giveThe path formula chooses its first color freely and each succeeding color in $x-1$ ways.

Choose the central vertex's color in $x$ ways. Every rim vertex must avoid that color, so the rim is a cycle colored using the remaining $x-1$ colors. Hence

The Ramsey number $R(k,l)$ is the least $N$ such that every graph on $N$ vertices has a $k$-clique or an independent set of size $l$. Choose a vertex in a graph of order $R(k-1,l)+R(k,l-1)$. It has either at least $R(k-1,l)$ neighbours or at least $R(k,l-1)$ nonneighbours. In the first set, a $(k-1)$-clique extends with the vertex to a $k$-clique, while an independent $l$-set already suffices. The complementary argument handles the second set. ThusThe boundary values are $R(k,2)=k$ and $R(2,l)=l$. Induction on $k+l$, using Pascal's identity, therefore gives

The graph Ramsey number $R(G,H)$ is the smallest $N$ such that every red-blue coloring of the edges of $K_N$ has a red copy of $G$ or a blue copy of $H$. These copies are subgraphs, not necessarily induced. Equivalently every graph on $N$ vertices contains $G$ or its complement contains $H$.

For $s,t\ge 2$, split $(s-1)(t-1)$ vertices into $s-1$ classes of size $t-1$, coloring edges between classes red and edges inside classes blue. The red graph has no $K_s$, and every blue component is too small for the connected tree. This proves the lower bound.

For the upper bound let $N=(s-1)(t-1)+1$ and suppose the blue graph contains no copy of the tree. By the permitted chromatic-number statement, its chromatic number is at most $t-1$. A graph of larger chromatic number would have a subgraph of chromatic number exactly $t$, obtained by deleting vertices until that number is reached. A proper blue coloring with at most $t-1$ classes puts no blue edges within any class, so each class is a red clique. If there is no red $K_s$, each class has at most $s-1$ vertices, contradicting $N>(s-1)(t-1)$. ThereforeThe one-vertex boundary cases give one directly.

A vertex with at least $R(t,t)$ neighbours has either a $t$-clique among them, producing $K_{t+1}$ with the vertex, or an independent $t$-set among them, producing an induced star with that centre.

For the second assertion put $D=R(t,t)-1$. If either of those two outcomes is absent, the preceding result forces maximum degree at most $D$. In a connected graph of this maximum degree, a ball of radius $t-1$ has at most $1+D+\cdots +D^{t-1}$ vertices, using the rough bound on walks at each distance. If the graph has more vertices, some vertex lies at distance at least $t$ from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first $t$ edges give an induced path of the required length. Thus a sufficiently large connected graph has one of the three listed configurations.

The extremal number $\mathrm{ex}(n;H)$ is the maximum number of edges in a simple graph on $n$ vertices containing no subgraph isomorphic to $H$. For a fixed graph with $\chi (H)=r\ge 2$, the Erdős-Stone theorem givesEquivalently, the ratio to $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ tends to $1-1/(r-1)$. The bipartite case has limiting density zero.

An even cycle is bipartite and has chromatic number two. An odd cycle has chromatic number three. The extremal-density theorem therefore givesFor odd cycles the complete balanced bipartite graph also exhibits the matching asymptotic lower density one half.

For nonempty disjoint vertex sets define $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is $ϵ$-uniform, also called regular, if whenever $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ have sizes at least $ϵ|X|$ and $ϵ|Y|$,Thus reasonably large relative subsets retain almost the same edge density.

Let $S$ be the vertices of $X$ with fewer than $d|Y|/2$ neighbours in $Y$. If $|S|>ϵn$, it is a permissible subset in the regularity test, and averaging those degrees gives $d(S,Y)<d/2$. But $d(X,Y)\ge d$, socontradicting regularity. Therefore there are at most $ϵn$ such vertices. The same argument in fact rules out $|S|\ge ϵn$ when that threshold is integral and nonzero.

Retain $0<ϵ<d/2$ from the preceding part. In $X_1$, at most $ϵn$ vertices have too few neighbours in $X_2$, and at most $ϵn$ have too few in $X_3$. Since $d\le 1$, $2ϵ<1$, so some $x\in X_1$ is good for both. Put $Y_2=N(x)\cap X_2$ and $Y_3=N(x)\cap X_3$. Their sizes are at least $dn/2>ϵn$. Regularity of $(X_2,X_3)$ therefore givesThere is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form a triangle. The nonempty equal classes ensure this counting argument also covers small integer sizes.

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.