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

Graph Theory and Probabilistic Combinatorics, Mathematics Part C and the corresponding joint schools; Friday 30 May 2008, 9.30am–12.30pm. The full six-page source, including both sections, its intact cover and the printed illustration, is privately transcribed from original Part C bundle pages 190–195, 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$ if and only if $|N(U)|\ge |U|$ for every $U\subseteq L$. Here $N(U)$ is the set of vertices of $R$ adjacent to at least one member of $U$. Necessity follows because matched partners of $U$ are distinct members of $N(U)$.

For sufficiency induct on $|L|$; zero or one vertex is immediate. If a nonempty proper $U\subset L$ has $|N(U)|=|U|$, Hall's condition holds within the graph on $U,N(U)$. It also holds on the remaining classes: for $T\subseteq L\setminus U$,Induction gives matchings in these two disjoint subgraphs, and their union covers $L$. Otherwise every nonempty proper $U$ has $|N(U)|\ge |U|+1$. Choose any edge $lr$ and delete its two endpoints. Every nonempty subset of the remaining left class was a proper subset of $L$, so deleting $r$ leaves at least as many neighbours as vertices. Induction gives a matching there, and adjoining $lr$ completes the matching. This proves sufficiency in all cases.

Make a bipartite graph whose two classes index the two partitions, joining $i$ on the left to $j$ on the right exactly when $A_i\cap B_j\ne \varnothing$. For a subset $U$ of left indices, its union of blocks contains $2008|U|$ elements. They all lie in the blocks indexed by $N(U)$, whose union has $2008|N(U)|$ elements. Thus $|N(U)|\ge |U|$. Hall's theorem gives a matching covering all $n$ left vertices, hence also all $n$ right vertices. Its partner map is the required permutation $\pi$.

In the vertex form of Menger's theorem, for distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of pairwise internally vertex-disjoint $s$–$t$ paths equals the minimum size of an $s$–$t$ vertex separator. A separator is a subset of vertices other than $s,t$ whose deletion leaves no $s$–$t$ path; internally disjoint paths may share their endpoints but no other vertices. Equivalently, between disjoint vertex sets the maximum number of mutually vertex-disjoint connecting paths equals the minimum size of a separating vertex set, where endpoints may be deleted in that set version.

Add $s$ adjacent to every vertex of $V_1$ and $t$ adjacent to every vertex of $V_2$. Suppose an $s$–$t$ separator $C$ has fewer than $n$ vertices. It cannot contain all of either class. Choose $x\in V_1\setminus C$ and $y\in V_2\setminus C$. No edge can join the remaining two classes, since it would give a three-edge $s$–$t$ path. Hence every neighbour of $x$ lies in $C\cap V_2$, and every neighbour of $y$ lies in $C\cap V_1$. The minimum-degree bound impliesa contradiction. Menger's theorem therefore gives $n$ internally vertex-disjoint $s$–$t$ paths. Each uses at least one vertex of each original class, and only $n$ vertices are available in each class. Every path must consequently use exactly one of each. Their middle edges form a perfect matching.

The Turán graph $T_r(n)$ is the complete $r$-partite graph whose nonempty part sizes differ by at most one. Write $n=qr+s$, $0\le s<r$: it has $s$ parts of size $q+1$ and $r-s$ parts of size $q$.

Turán's theorem states that every simple $n$-vertex graph with no $K_{r+1}$ has at most $e(T_r(n))$ edges, with equality precisely for a graph isomorphic to $T_r(n)$. Its edge number is half of $n^2$ minus the sum of the squared part sizes.

For a positive integer $x$, $p_G(x)$ counts proper vertex colorings using a labelled palette of $x$ colors. Choose an edge $e=uv$. Proper colorings of $G-e$ divide into those in which $u,v$ have different colors, counted by $p_G(x)$, and those in which they have the same color, counted by $p_{G/e}(x)$. Thuswhere parallel edges after contraction are suppressed. Induction, using $p_G(x)=x^{|V(G)|}$ for an edgeless graph, produces a polynomial agreeing with every integer coloring count. The polynomial is unique because two polynomials agreeing at infinitely many integers are identical.

Deletion-contraction also proves the alternating-sign form with nonnegative coefficients. If $G$ has $n$ vertices, $G/e$ has $n-1$, so subtracting its alternating expansion adds its coefficient at each succeeding index:Starting from an edgeless graph gives $a_0=1$ and no constant term when $n>0$.

For the first coefficients, inclusion-exclusion over the forbidden monochromatic edges gives the precise expressionwhere $c(F)$ counts components of the spanning graph $(V(G),F)$, including isolated vertices. Only $F=\varnothing$ gives $x^n$. A rank-one edge set is a single edge, giving coefficient $-m$ at $x^{n-1}$. Rank two comes from every two-edge subset, each with positive sign, and every triangle, each with negative sign. No other simple edge set has rank two: its nontrivial components must be a three-vertex component or two separate edges. ThusThe displayed $a_2$ assertion concerns $n\ge 3$; below this degree the corresponding coefficient is absent and its expression is zero.

The degree of a chromatic polynomial is the number of vertices and the negative of its next coefficient is the number of edges. Equality with $p_{K_n}$ therefore forces $n$ vertices and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. A simple graph on those vertices with that many edges contains every possible edge, so $\boxed{G\cong K_n}$.

The chromatic number is the smallest positive integer $q$ for which $p_G(q)>0$. Thus equality of the polynomials implies $\chi (G)=r$, as well as $|V(G)|=n$ and $e(G)=e(T_r(n))$. In particular $G$ contains no $K_{r+1}$, since such a clique requires $r+1$ colors. The equality case in Turán's theorem now gives $\boxed{G\cong T_r(n)}$. This uses more than equality of triangle counts: the polynomial also determines colorability.

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves

The five-cycle and its complement both have no triangle, so $R(3,3)>5$. In a six-vertex graph, any vertex has at least three neighbours or three nonneighbours. In the first triple an edge completes a triangle with the chosen vertex, while no edges give an independent triple. The complementary argument handles three nonneighbours. Hence $R(3,3)=6$.

Now suppose a nine-vertex graph contains no triangle and no independent four-set. Each vertex has at most three neighbours, since its neighbourhood is independent. It cannot have at most two neighbours: its at least six nonneighbours contain, by the result just proved, either a triangle or an independent triple; the former is forbidden and the latter joins the vertex to give an independent four-set. Every degree must therefore equal three. But nine vertices of degree three have odd total degree, contradicting the handshake lemma. Thus $R(3,4)\le 9$.

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

Assume the usual nontrivial case $\chi (G)\ge 2$ and $|H|\ge 2$. On $(\chi (G)-1)(|H|-1)$ vertices partition into $\chi (G)-1$ equal classes of size $|H|-1$. Color all edges between distinct classes red and all edges within a class blue. The red graph is $(\chi (G)-1)$-colorable, so it contains no copy of $G$. Every blue connected component has only $|H|-1$ vertices, so connectedness prevents a blue copy of $H$. Therefore one more vertex is necessary:If $G$ is edgeless or $H$ has one vertex, the displayed lower bound is just one and holds directly.

For nonempty disjoint vertex sets, the edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. A pair is $ϵ$-uniform, also called $ϵ$-regular, if every $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfiesIt says that restricting to reasonably large subsets does not noticeably change the edge density.

In the standard regularity-partition convention, the vertex sets form a disjoint partition, the nonexceptional sets $V_1,\dots ,V_k$ are nonempty and have a common size, $|V_0|<ϵ|V(G)|$, and at most $ϵk^2$ unordered nonexceptional pairs fail to be $ϵ$-uniform. One can instead use weak inequality for the exceptional-set bound without affecting the argument below once the size bound is strict. The exceptional set absorbs the rounding remainder when the graph order is not divisible by $k$.

Write $N=|G|$ and $D(U)=e(G[U])-p\left(\genfrac{}{}{0ex}{}{|U|}{2}\right)$. For disjoint sets $U,W$ of size at least ${ϵ}^{2}N$, the given identity and the corresponding binomial identity giveIn the nonvacuous regularity range $0<ϵ<1$, the original sets therefore satisfy $|d(X,Y)-p|<{ϵ}^3/3$. Their allowed subsets have size at least ${ϵ}^{2}N$, so $|d(X^{\prime },Y^{\prime })-p|<ϵ/3$. The triangle inequality givesThus the pair is uniform. For $ϵ\ge 1$, the definition is vacuous or immediate; the subsequent positive-integer condition $k<1/ϵ$ has no solutions.

For the partition deduction, choose $k$ equal classes of size $q=\lfloor N/k\rfloor$, putting the remainder into $V_0$. For fixed $k<1/ϵ$ and sufficiently large $N$, $q\ge ϵN$ and $|V_0|<k<ϵN$. Every class pair is uniform by what was just proved, which is stronger than the required condition. For example, it suffices thatA graph-size qualification is necessary if the printed deduction is read literally for every graph order. Under the standard nonempty-class definition, a one-vertex graph satisfies the discrepancy hypothesis for every $p$ and positive $ϵ$, but cannot be partitioned into two nonempty classes even when $2<1/ϵ$. The source omits this small-order qualification. If $k$ divides $N$, no rounding is needed and $N\ge k$ already suffices, since $N/k>ϵN$.

For $k\ge 1$, monotonicity of the logarithm givesThus $k!\ge (k/e{)}^k$. Bounding the numerator of the binomial coefficient by $n^k$ yields

The function $x-\log (1+x)$ has derivative $x/(1+x)$, is zero at zero, and is nonnegative for every $x>-1$. Therefore $\log (1+x)\le x$. Multiplying by $m>0$ and exponentiating givesEquality occurs at $x=0$.

Each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered vertex pairs has two independent choices of orientation. Hence the number of tournaments on the specified labelled vertex set is

Orient each edge independently and uniformly. Fix a $k$-set $A$. An outside vertex beats every member of $A$ with probability $2^{-k}$. For different outside vertices these events depend on disjoint sets of edges, so they are independent. ThusA union bound over all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible sets givesThe complementary event has positive probability, proving a tournament with the required domination property exists. This applies in the intended nonvacuous range $n\ge k$; the asymptotic construction below has $n>k$.

For large $k$, chooseUsing the two inequalities proved in part (a), the logarithm of the union bound is at mostNow ${\log }_e(en/k)=k{\log }_{e}2+{\log }_{e}k+O(1)$, whereas $(n-k)2^{-k}=k^2{\log }_{e}2+2k{\log }_{e}k+o(1)$. Their difference isfor all sufficiently large $k$. The existence criterion therefore applies. Since the chosen $n$ satisfieswe obtain $\boxed{f(k)\le k^2{2}^k({\log }_{e}2)(1+o(1))}$, with the usual convention that the tournament has at least $k$ vertices. If orders below $k$ were permitted, the property would be vacuous there; the same upper bound remains valid but the extremal definition would be uninteresting.

Explore the individuals one at a time, maintaining the number of discovered but unprocessed individuals. It starts at $S_0=1$. Processing one individual removes it and adds its offspring, soThe offspring choices make these increments independent. Exploration stops when the queue first becomes empty; every processed individual has then been counted exactly once. Hencewith $K=\infty$ if the walk never hits zero. The increment sequence can be extended independently beyond the stopping time for probability estimates.

The event $K=k$ implies $S_k=0$. If $B_k$ counts the positive increments, then $B_k\sim \mathrm{Bin}(k,p)$ and $S_k=1+2B_k-k$. Let $\delta =|p-1/2|>0$.

For $p>1/2$, $S_k=0$ forces $B_k=(k-1)/2\le k/2$, so the lower-tail Hoeffding form of the Chernoff bound givesFor $p<1/2$ and $k\ge 1/\delta$, the required value is at least $kp+\delta k/2$. The upper-tail bound gives $\mathbb{P}(K=k)\le e^{-{\delta }^{2}k/2}$.

To include all smaller positive integers, note that each finite-time atom has probability strictly less than one: at $k=1$ its probability is $1-p<1$, while for $k>1$ immediate extinction already has positive probability and excludes $K=k$. Over the finitely many small $k$ with nonzero atom, take the minimum of $-k^{-1}\log \mathbb{P}(K=k)$ and the applicable tail constant. This minimum is positive, and zero atoms impose no restriction. Thus for both cases there is $c>0$ such thatIn the supercritical case this bounds the finite atoms, not the positive probability of $K=\infty$.

Let $Z_r$ be the size of generation $r$, with $Z_0=1$. Its offspring mean is $2p$, so conditioning on the previous generation gives $\mathbb{E}{Z}_r=(2p{)}^r$. At $p=1/2$,The interchange uses Tonelli's theorem for nonnegative variables. Critical extinction is nevertheless almost sure: its probability is the smallest root in $[0,1]$ of $s=(1+s^2)/2$, whose only root is one. Hence $K$ is finite almost surely. If all its finite atoms had the exponential bound, then $\mathbb{E}K\le {\sum }_{k\ge 1}k{e}^{-ck}<\infty$, a contradiction.

For $p>1/2$ the extinction probability is $(1-p)/p<1$. There is positive mass at $K=\infty$, so the mean is infinite even if every finite atom decays exponentially. This is precisely why the critical contradiction does not extend to the supercritical case.

The general Lovász local lemma concerns events $A_1,\dots ,A_m$ with a dependency graph: each $A_i$ is independent of the sigma-algebra generated by all nonneighbouring events other than itself. If numbers $x_i\in [0,1)$ satisfythen $\mathbb{P}({\bigcap }_i{A}_i^c)\ge {\prod }_i(1-x_i)>0$.

Its symmetric form states that if $\mathbb{P}(A_i)\le q$, every dependency degree is at most $d$, and $eq(d+1)\le 1$, then there is positive probability that no event occurs. For $d\ge 1$, set all $x_i=1/(d+1)$. Sincewe have $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log (1+1/d)\le 1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.

Each row sum is a sum of $k$ independent random signs. For $s>0$, its moment generating function isFor example, $\log \cosh s\le s^2/2$ follows by integrating $\tanh s\le s$ for $s\ge 0$. Markov's inequality yields $\mathbb{P}(Y_j\ge t)\le \exp (-st+k{s}^2/2)$. Choosing $s=t/k$ gives $e^{-t^2/(2k)}$ for $t>0$. The distribution is symmetric, so the same bound applies to its negative tail. A union bound provesfor $t\ge 0$, including the trivial endpoint $t=0$.

Let $t=\sqrt{2k{\log }_e(6kr)}$ and define $A_j=\{|Y_j|\ge t\}$. The preceding estimate gives $\mathbb{P}(A_j)\le 1/(3kr)$. An event depends only on the $k$ signs in that row. Each such column occurs in at most $r-1$ other rows, so its dependency degree is at most $d=k(r-1)$. Events on disjoint sets of signs are independent even jointly, giving the required dependency graph.

For positive $k,r$,The symmetric Lovász local lemma therefore gives positive probability that no $A_j$ occurs. Such a sign vector satisfiesThe positive-parameter assumption is implicit in the printed square-root expression. If all rows are zero, all row sums vanish and no probabilistic construction is needed.

Chebyshev's inequality says that for a random variable $Z$ with finite mean and variance, and every $t>0$,

For each cyclic starting position $i$, let $I_i$ indicate that the next $k$ entries are all one. Then $X={\sum }_i{I}_i$ and $\mathbb{E}{I}_i=p^k$, hence $\mathbb{E}X=n{p}^k$.

For two starts separated by $j\in \{1,\dots ,k-1\}$ along either direction, their runs overlap in $k-j$ positions, so $\mathbb{E}(I_i{I}_{i+j})=p^{k+j}$. All other distinct starts use disjoint entries and are independent. Since $k\le n/2$, the two directions' overlap ranges do not intersect. Summing the variances and covariances givesIn particular, dropping negative terms and summing a geometric series yieldswhen $p\le 1/2$. The formula also covers $k=1$ with an empty covariance sum.

For $p=1/2$ and $k={\log }_{2}n+\omega (n)$,If $\omega (n)\to \infty$, the mean tends to zero. Markov's inequality gives $\mathbb{P}(X\ge 1)\le \mathbb{E}X\to 0$, so $\boxed{\mathbb{P}(X=0)\to 1}$.

Now $\omega (n)\to -\infty$ makes $\mathbb{E}X=2^{-\omega (n)}\to \infty$. Chebyshev's inequality and the variance bound giveFor every fixed $ϵ>0$, they likewise giveThus the count is concentrated about its growing mean, despite the overlapping runs.

For $p=1/4$, use $k={\log }_{4}n+\omega (n)$. Then $\mathbb{E}X=4^{-\omega (n)}$, so its limits are exactly those needed for the same two arguments.

For $p=1/{\log }_{e}n$, a convenient definition that also accounts for the varying probability isIt makes $\mathbb{E}X=e^{-\omega (n)}$. Thus $\omega \to +\infty$ gives no runs with high probability, and $\omega \to -\infty$ gives runs and relative concentration. For sufficiently large $n$, $p\le 1/2$, so the same uniform variance bound applies. Definitions are made from the actual integer $k$; no continuous rounding assumption is required. These conclusions retain the stipulated range $1\le k\le n/2$.