Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford

Source paper: FOI request thread. The intact cover identifies Graph Theory and Probabilistic Combinatorics, C11.1, Friday 10 June 2011, 9.30am to 12.30pm. The private bundle contains this five-page paper at original pages 461–465. Its Graph Theory questions are also issued separately as C11.1a, with a distinct cover and formal identifiers.

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

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

The vertex version of Menger's theorem states that for two distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of internally vertex-disjoint $s$-$t$ graph paths equals the minimum size of a set $S\subseteq V\setminus \{s,t\}$ whose deletion separates $s$ from $t$.Internally disjoint graph paths may share their endpoints but no other vertex. The nonadjacency hypothesis is needed in this separator formulation, since an edge $st$ cannot be destroyed by deleting other vertices.

Let the bipartition be $L\cup R$. Form an auxiliary graph by adding a new vertex $s$ adjacent to every vertex of $L$ and a new vertex $t$ adjacent to every vertex of $R$. The vertices $s,t$ are nonadjacent, so Menger's theorem applies.

A matching of size $m$ gives $m$ internally disjoint graph paths $s\ell rt$, one for each matching edge $\ell r$. Conversely, every $s$-$t$ graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.

An $s$-$t$ separator contained in $L\cup R$ is exactly a vertex cover of the original graph. Indeed, an uncovered edge $\ell r$ would leave the graph path $s\ell rt$, while removing a vertex cover removes every edge between $L$ and $R$ and hence every $s$-$t$ graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.

Hall's marriage theorem says that a bipartite graph with parts $L,R$ has a matching saturating $L$ if and only ifNecessity follows because the matched neighbours of vertices of $S$ are distinct and belong to $N(S)$.

For sufficiency, assume these inequalities. Let $K=U\cup W$ be any vertex cover, with $U\subseteq L$ and $W\subseteq R$. Every neighbour of $S=L\setminus U$ must belong to $W$, since otherwise its edge from $S$ is uncovered. Therefore $|W|\ge |N(S)|\ge |S|$, and $|K|\ge |U|+|S|=|L|$. The whole part $L$ is itself a vertex cover of size $|L|$. Part (ii) now gives a matching of size exactly $|L|$, so it saturates $L$.

Choose a spanning tree of the connected graph and root it at $x$. List vertices in nonincreasing order of their distance from $x$ in this tree, breaking ties arbitrarily. The root has distance zero and is last, so $v_n=x$.

Every other vertex has a parent one step closer to the root. That parent is adjacent to it and appears later in the ordering. HenceFor a graph of one vertex the condition is vacuous and the same ordering works.

Write $\Delta =\Delta (G)$, which is at least two because $x$ has the two specified neighbours. Give $y$ and $z$ the same colour, say colour one; this is proper because they are nonadjacent.

Apply part (i) to the connected graph $G\setminus \{y,z\}$, with $x$ last. Colour its vertices greedily in the resulting order using a palette of $\Delta$ colours. Every vertex before $x$ has a neighbour later in this order, so at most $\mathrm{deg}(v)-1\le \Delta -1$ of its neighbours have already received colours. At least one palette colour is available.

When $x$ is reached, all its neighbours are coloured, but the two neighbours $y,z$ have the same colour. Thus there are at most $\mathrm{deg}(x)-1\le \Delta -1$ distinct forbidden colours. Colour $x$ with a remaining one. This constructs a proper colouring withThe common colour on the two initial vertices replaces the usual need for an uncoloured neighbour at the last greedy step.

This is greedy colouring with two precoloured neighbours.

Take a proper colouring $c:V(G)\to \{1,\dots ,k\}$ and orient every edge from its lower-coloured endpoint towards its higher-coloured endpoint. Along a directed path the colour strictly increases, so such a graph path has at most $k$ vertices. A directed cycle is impossible for the same reason. Thus

For each vertex $v$, let $c(v)$ be the maximum number of vertices in a directed path ending at $v$. These numbers lie between one and $\ell$.

If $u\to v$ is an edge, a longest graph path ending at $u$ cannot already contain $v$, since that would give a directed cycle on appending $u\to v$. Appending it therefore creates a graph path ending at $v$, so $c(v)\ge c(u)+1$. Adjacent vertices consequently receive different colours. HenceAcyclicity is exactly what justifies extending the graph path without repeating a vertex.

Part (ii) shows that $\chi (G)\le \lambda (D)$ for every acyclic orientation $D$, so $\chi (G)$ is at most their minimum. Part (i), applied to an optimal colouring, supplies an acyclic orientation with $\lambda (D)\le \chi (G)$. Combining the inequalities givesThe parameter counts vertices on a graph path; if graph path length were instead counted in edges, the corresponding minimum would be $\chi (G)-1$.

These constructions prove chromatic number from acyclic longest paths.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.

For disjoint nonempty sets $X,Y$, let $e(X,Y)$ count edges between them. Their edge density isThe pair is $\epsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\ge \epsilon |X|$, $|B|\ge \epsilon |Y|$ satisfies $|d(A,B)-d(X,Y)|\le \epsilon$.

An $\epsilon$-regular partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering $V(G)$, with $|V_0|\le \epsilon |V(G)|$, equal positive sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\le i<j\le k$ that are not $\epsilon$-regular. The set $V_0$ is exceptional and its pairs need not satisfy regularity.

Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0\ge 1$, there are integers $M,n_0$ such that every graph with $n\ge n_0$ vertices has such a partition withThe bounds depend on $\epsilon ,m_0$, not on the graph order. Using a strict regularity inequality or a slightly different constant in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.

Let $B\subseteq X$ be the vertices with fewer than $(d/2)|Y|$ neighbours in $Y$. If $|B|\ge \epsilon |X|$, regularity applies to the pair $(B,Y)$ and givesBut averaging the defining strict degree inequality over $B$ gives $d(B,Y)<d/2$, a contradiction. ThereforeRegularity controls the neighbourhood of almost every vertex because a large set of exceptional low-degree vertices would itself witness an irregular density.

Apply part (b) to $(X_1,X_2)$ and $(X_1,X_3)$. Fewer than $2\epsilon |X_1|$ vertices fail at least one of the degree bounds. For any remaining vertex $v$, put $N_2=N(v)\cap X_2$ and $N_3=N(v)\cap X_3$. ThenRegularity of $(X_2,X_3)$ gives $d(N_2,N_3)\ge d-\epsilon \ge d/2$. Every edge between $N_2$ and $N_3$ makes a distinct triangle containing $v$. Hence $v$ belongs to at leastsuch triangles. This proves the asserted bound on exceptional vertices.

There are at least $(1-2\epsilon )|X_1|\ge |X_1|/2$ good vertices. Summing their triangle counts counts each triangle with one vertex in each cluster exactly once, at its $X_1$ vertex. ThereforeThere is no factor of three to divide out in this cross-cluster count.

This is the regular triangle counting lemma with explicit coarse constants.

Choose a small density threshold $d>0$, then $\epsilon \le \min (d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large thatApply the regularity lemma. Delete all edges incident with $V_0$, all edges within a class $V_i$, all edges between irregular pairs, and all edges between regular pairs of density below $d$. Their total is at mostIf a triangle remains, its vertices lie in three distinct nonexceptional classes, all whose pairs were regular with original density at least $d$. Part (c) then forces at least $(d^3/16)t^3$ triangles in the original graph, where $t$ is the common class size. Since $k\le M$ and $\epsilon \le 1/4$, we have $t\ge n/(2M)$, so this is at least $d^3{n}^3/(128M^3)$.

Choose $c=d^3/(256M^3)$ and take $n_0$ large enough for the regularity lemma. An original graph with at most $c{n}^3$ triangles cannot leave any triangle after these deletions. Thus deleting at most $\eta n^2$ edges makes the graph triangle-free. This is the triangle removal lemma; boundedly many large regular clusters turn any surviving triangle into a positive-density family of original triangles.

Markov's inequality states that for $Y\ge 0$ and $t>0$, $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$. It follows by taking expectations in $Y\ge t{1}_{\{Y\ge t\}}$.

If $X$ has finite mean $\mu$ and variance ${\sigma }^2$, apply Markov to $(X-\mu {)}^2$ to obtain Chebyshev's inequality:For the first moment method, assume ${\mu }_n=\mathbb{E}{X}_n\to 0$. Nonnegative integer values give $\{X_n>0\}=\{X_n\ge 1\}$, soFor a standard second moment method, suppose ${\mu }_n>0$ eventually, the second moments are finite, and $\mathbb{E}{X}_n^2/{\mu }_n^2\to 1$. Equivalently, $\mathrm{Var}(X_n)/{\mu }_n^2\to 0$. The zero event is contained in $\{|X_n-{\mu }_n|\ge {\mu }_n\}$, soHence $\boxed{\mathbb{P}(X_n>0)\to 1}$. The second-moment condition controls the fluctuations relative to the mean; a large mean alone is insufficient.

Let $X$ count the four-vertex sets spanning all four of their possible triples. For each such set $S$, write $I_S$ for its indicator. Independence of the four hyperedges givesIf $np\to 0$, then $\mu \le (np{)}^4/24\to 0$, and the first moment method shows that the probability of a four-clique tends to zero.

For the other direction, consider two distinct four-sets. If they meet in at most two vertices, they have no possible triple in common, so their indicators are independent. If they meet in three vertices, they share exactly one triple, so $\mathbb{E}(I_S{I}_T)=p^7$ and their covariance is at most $p^7$. There are $O(n^5)$ ordered pairs of this latter type. The diagonal variances sum to at most $\mu$, henceFor large $n$, $\mu$ is a constant multiple of $n^4{p}^4$, and consequentlyIf $np\to \infty$, the first term tends to zero, and so does the second since $n^{3}p=n^2(np)\to \infty$. The second moment method proves that a four-clique exists with probability tending to one. Therefore a threshold function isThe shared-triple overlap, rather than overlaps in one or two vertices, is the only off-diagonal dependence that affects this computation.

This is the four-clique threshold in a binomial 3-uniform hypergraph.

The requested scale is $\boxed{k=\Theta (\sqrt{\log n})}$. To see its first-moment origin, the number $X_k$ of $k$-cliques has expectationFor $k$ on the proposed scale, taking base-two logarithms givesThe leading terms balance at $k\approx \sqrt{6{\log }_{2}n}$. In particular, for any fixed $c>\sqrt{6}$, taking $k$ near $c\sqrt{{\log }_{2}n}$ makes the expectation tend to zero, so such cliques are absent with probability tending to one.

Thus the first-moment estimate places the largest-clique scale at a constant multiple of $\sqrt{\log n}$, as requested. A diverging expectation below that balance does not itself prove existence; a corresponding probabilistic lower-bound proof would require an additional argument and is not part of the requested first-moment estimate.

A dependency digraph has vertices $1,\dots ,n$ and no loops. For each $i$, the event $A_i$ must be independent of the sigma-algebra generated jointly by all $A_j$ with $j\ne i$ for which there is no edge $i\to j$. Joint independence from that collection is required; pairwise independence alone does not suffice.

Write ${\Gamma }^{+}(i)$ for the outneighbours of $i$, and $B_S={\bigcap }_{j\in S}{A}_j^c$. We prove by induction on $|S|$ that $B_S$ has positive probability and, when $i\notin S$,For $S=\varnothing$, the asserted conditional bound follows from the hypothesis, since its product factors are at most one. For the induction step, positivity for a set of size $r$ follows by writing its avoidance probability as a chain product: all preceding conditioning sets have size below $r$, so each factor is at least $1-x_j>0$.

Now take $|S|=r$, split $S_1=S\cap {\Gamma }^{+}(i)$ and $S_2=S\setminus {\Gamma }^{+}(i)$, and condition first on $B_{S_2}$. Independence gives $\mathbb{P}(A_i\mid B_{S_2})=\mathbb{P}(A_i)$. Moreover, order the elements of $S_1$ and use the inductive conditional bounds on the successive avoidance factors. Their conditioning sets have size at most $r-1$, soThis remains true when $S_1$ is empty, with both sides one. ThereforeThe induction is complete. Finally expand the probability of avoiding all events in the order $1,\dots ,n$:This proves the asymmetric Lovász local lemma, including the positivity needed to make every conditioning step legitimate.

The symmetric Lovász local lemma states: if each bad event has probability at most $p$, each event is independent of the collection of all but at most $d$ other events, andthen the probability that none of the bad events occurs is positive. Independence is from the sigma-algebra generated by the indicated nonneighbours, as in part (a). A sufficient sharper parameter condition is $p\le x(1-x{)}^d$ for some $x\in (0,1)$; taking $x=1/(d+1)$ gives the displayed standard bound when $d\ge 1$. When $d=0$, mutual independence directly gives the conclusion under the displayed bound.

If there are no triangles, any edge colouring works. Otherwise $\Delta \ge 2$. Put $q=\lceil 3\sqrt{\Delta }\rceil$ and colour each edge independently and uniformly from $q$ colours. For each triangle $T$, let $A_T$ be the event that its three edges have one colour. ThenEvents for triangles sharing no edge depend on disjoint edge-colour variables, so each event is jointly independent of the collection of all such nonneighbours. Each edge of a triangle lies in at most $\Delta -2$ other triangles: a common neighbour of its endpoints must be one of at most $\Delta -1$ neighbours besides the other endpoint, and one of these is the third vertex of $T$ itself. Thus the dependency degree is at most $d=3(\Delta -2)$.

Because $q^2\ge 9\Delta$,The symmetric local lemma gives positive probability of avoiding every monochromatic triangle. HenceFor an edgeless graph the empty colouring handles even the zero-colour case $\Delta =0$.

A Galton-Watson process starts with one ancestor, $X_0=1$. Given generation size $X_r$, definewhere all offspring variables are independent with common distribution $Z$. The empty sum is zero, so zero is absorbing. Its extinction probability isFor the probability generating function $f(s)=\mathbb{E}[s^Z]$, the allowed fixed-point characterization isFor binomial offspring, $f(s)=(1-p+ps{)}^k$, with $f(1)=1$, $f^{\prime }(1)=kp$, and $f$ convex on $[0,1]$.

First assume $0<p<1$. If $k=0$, extinction occurs immediately. For $k=1$, $f(s)-s=(1-p)(1-s)>0$ for $s<1$, so the only fixed point is one. For $k\ge 2$, strict convexity givesIf $kp\le 1$, the right-hand side is at least $s$, so no fixed point below one exists and $\eta =1$. If $kp>1$, $f(s)-s<0$ for $s$ just below one, whereas $f(0)>0$. Continuity supplies a fixed point in $(0,1)$; hence $\eta <1$. Thus in the nondegenerate parameter range,For completeness, if binomial endpoint parameters are allowed, $p=0$ or $k=0$ gives $\eta =1$, while $p=1$ and $k\ge 1$ gives deterministic positive offspring and $\eta =0$. In particular $(k,p)=(1,1)$ survives forever despite mean one. Over $k\in \{0,1,\dots \}$ and $p\in [0,1]$, the full condition is

Explore the family tree one individual at a time, maintaining a queue of individuals not yet explored. Initially its size is $Y_0=1$. Exploring individual $t$ removes it and adds its independent offspring $Z_t$, so before the queue empties,One may define the independent increments indefinitely, but the tree exploration stops at $T=\inf \{t:Y_t=0\}$. This hitting time is the total progeny, including the ancestor. Since each increment is at least $-1$, a queue cannot jump below zero before hitting zero. If it never hits zero, the family has infinitely many individuals.

Suppose $kp<1$. A Chernoff bound in moment-generating-function form says that for independent $W_j$ and $\theta >0$,Here take $W_j=Z_j-1$, withWe have $M(0)=1$ and $M^{\prime }(0)=kp-1<0$, so some $\theta >0$ has $M(\theta )<1$. Let $c=-\log M(\theta )>0$. If $T>n$, the queue is still positive after $n$ explorations; its integer value is at least one, giving ${\sum }_{j=1}^n(Z_j-1)\ge 0$. ThereforeThis proves the claimed bound without appealing to a general branching-process tail theorem.

The argument proves the more general exponential total progeny tail for bounded subcritical offspring.

First take $0<p<1$ and $kp>1$. Part (a) gives an extinction probability $\eta \in (0,1)$. Write $p_j=\mathbb{P}(Z=j)$. Conditional on the ancestor having $j$ children, extinction requires extinction of all $j$ independent descendant trees and has probability ${\eta }^j$. Bayes' rule therefore gives the conditional offspring lawIts sum is $f(\eta )/\eta =1$. Conditional on extinction of all descendant trees, those trees remain independent, each with its own extinction-conditioned law. Thus the entire conditioned process is a Galton–Watson process with offspring generating functionFor binomial offspring, using $\eta =(1-p+p\eta {)}^k$ givesIts mean is $k\tilde{p}=f^{\prime }(\eta )<1$. Indeed, $f(s)-s$ is strictly convex and has its two zeros at $\eta$ and one, so its derivative at the first zero is strictly negative. This proves subcriticality directly from the generating function.