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

Graph Theory and Probabilistic Combinatorics, Trinity Term; Friday 5 June 2009, 9.30am–12.30pm. This combined Part C paper was shared by Mathematics, Mathematics and Computer Science, and Mathematics and Statistics. Both sections and all six questions are covered below; the complete four-page source is retained in a private editable transcription. The source was supplied through the past-papers disclosure, in original Part C bundle pages 286–289. No exact worked-answer advertisement was found in the bounded check.

Hall's marriage theorem says that a finite bipartite graph with parts $L,R$ has a matching covering $L$ if and only if $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because matching edges send the vertices of $S$ to distinct neighbours.

For sufficiency, choose a maximum matching $M$. If it misses $a\in L$, explore all alternating paths from $a$, taking unmatched edges from left to right and matched edges from right to left. Let $S\subseteq L$ and $T\subseteq R$ be the reached vertices. No vertex of $T$ can be unmatched, since flipping the edges along the resulting augmenting path would enlarge $M$.

Every neighbour of a reached left vertex is reached on the right: unmatched edges are exploration steps, and a matched edge leads back to an already reached matching partner. Thus $T=N(S)$. Each right vertex in $T$ is matched to a reached left vertex other than $a$, and every reached left vertex other than $a$ arose this way. These matching partners give a bijection $T\leftrightarrow S\setminus \{a\}$. Hence $|N(S)|=|S|-1$, contradicting the assumed inequality. Therefore the maximum matching covers $L$.

Write the bipartition as $L,R$. Counting edges by their left and right ends gives $2009|L|=2009|R|$, so the parts have equal size. Put $H=G-F$. If some $S\subseteq L$ violated Hall's marriage theorem in $H$, let $T=N_H(S)$, so $|T|\le |S|-1$.

There are $2009|S|$ edges of $G$ incident with $S$, of which at most $2009|T|$ can end in $T$. Thus at least $2009(|S|-|T|)\ge 2009$ end in $R\setminus T$. All those edges must have been deleted, by the definition of $T$. This contradicts $|F|=2008$. Hence $H$ has a matching covering $L$, and equal part sizes make it a perfect matching avoiding every edge of $F$.

False. The path graph on four vertices is bipartite and its first and last edges form a perfect matching. It has no cycle at all, so it has no Hamiltonian cycle. This counterexample is connected as well.

True. Every cycle in a bipartite graph has even length because its vertices alternate between the two parts. On a Hamiltonian cycle, choose every other edge. These edges are disjoint and cover every vertex exactly once, so they form a perfect matching.

False. The complete bipartite graph $K_{2009,2010}$ is $2009$-connected. Deleting fewer than $2009$ vertices leaves at least one vertex in each part and therefore a connected complete bipartite graph; deleting the smaller part disconnects the larger independent set. But its two parts have unequal sizes, so a matching cannot cover them both. Equivalently it has an odd number of vertices. Thus it has no perfect matching.

For a finite simple loopless graph, $p_G(q)$ counts proper vertex colorings with $q$ labelled available colors, initially for nonnegative integer $q$. For an edge $e=uv$, proper colorings of $G-e$ split into those with different endpoint colors, counted by $p_G(q)$, and those with equal endpoint colors, counted by the contracted graph. Hence the deletion-contraction recurrence for the chromatic polynomial isParallel edges created by contraction can be suppressed since they impose the same coloring constraint. A graph with no edges has $p_G(q)=q^{|V(G)|}$. Induction by this recurrence therefore gives a polynomial agreeing with the counting function on all nonnegative integers. That polynomial is unique because two distinct polynomials cannot agree at infinitely many points.

Induct using the same deletion-contraction recurrence for the chromatic polynomial. The edgeless graph has polynomial $x^n$, so its leading coefficient is one and the others are zero. All nonempty-vertex chromatic polynomials have zero constant term, since no coloring uses zero colors.

For an existing edge, write the alternating coefficient lists of the deletion and simplified contraction as $a_i^{\prime }$ and $a_i^{\prime \prime }$. The contraction has $n-1$ vertices, so subtracting its polynomial changes its leading sign by one place. Thuswith nonexistent indices understood as zero. Both summands are nonnegative by induction. The leading coefficient is $a_0=1$, and the next isThis proves the alternating expansion and nonnegativity of every $a_i$. The coefficient assertion for $a_1$ is relevant when $n\ge 2$; the one-vertex graph simply has polynomial $x$.

Set $t=-x>0$. The coefficient formula givesEvery summand is nonnegative and the leading term is $t^n>0$, since $a_0=1$. Therefore

For the complete graph, $p_{K_n}(x)=x(x-1)\cdots (x-n+1)>0$ whenever $x>n-1$.

Use induction on the number of vertices, and for fixed $n$ on the number of missing edges. If $G$ is not complete, choose a missing edge $e$ and put $H=G+e$. The recurrence rearranges asThe first term is positive by the missing-edge induction. The second graph has $n-1$ vertices, so the vertex induction makes its polynomial positive for $x>n-2$, in particular for the present range. The one-vertex base case is $x>0$. Thus $p_G(x)>0$ for all $x>n-1$, including noninteger $x$; counting colorings alone would not establish that real-variable claim.

For disjoint nonempty vertex sets, their edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is epsilon-regular or epsilon-uniform if for all $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$,It controls density on every sufficiently large subpair, rather than merely on average over chosen subpairs.

An epsilon-uniform partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering the vertex set, with $|V_0|\le ϵ|V(G)|$, equal nonexceptional class sizes $|V_1|=\cdots =|V_k|$, and at most $ϵk^2$ unordered pairs of distinct nonexceptional classes failing epsilon-uniformity. The exceptional set need not have the common size.

Szemerédi regularity lemma states that for every $ϵ>0$ and positive integer $m_0$, there is $M=M(ϵ,m_0)$ such that every sufficiently large finite graph, for example every graph of order at least $M$ after enlarging $M$ if needed, has such a partition with $m_0\le k\le M$. The bound depends only on the accuracy and minimum class count, not on the graph's order.

Let $S\subseteq X$ be the vertices with fewer than $dn/2$ neighbours in $Y$. If $|S|>ϵn$, its density to all of $Y$ is below $d/2$. But epsilon-uniformity applies to $(S,Y)$ and requiresa contradiction. Therefore $|S|\le ϵn$.

Apply part (c) to the pairs $(X_1,X_2)$ and $(X_1,X_3)$. Outside a union of at most $2ϵn$ exceptional vertices, every $v\in X_1$ has sets $Y=N(v)\cap X_2$ and $Z=N(v)\cap X_3$ of size at least $dn/2$.

These sets are large enough for epsilon-uniformity of $(X_2,X_3)$, because $d/2>ϵ$. HenceEvery such edge completes a distinct triangle through $v$. Thus at most $2ϵn$ vertices of $X_1$ fail the claimed triangle count. Summing these triangles over the good vertices counts each triangle with one vertex in each class exactly once. Since $d\le 1$ and $ϵ<d/4\le 1/4$,

Chebyshev's inequality states that if $X$ has finite mean $\mu$ and variance ${\sigma }^2$, then for $t>0$,Indeed $(X-\mu {)}^2\ge t^2{1}_{\{|X-\mu |\ge t\}}$ pointwise. Taking expectations proves the result, including the zero-variance case.

The assumptions implyEventually ${\mu }_n>0$, and $X_n=0$ implies $|X_n-{\mu }_n|\ge {\mu }_n$. Thus Chebyshev's inequality givesNo independence between the different $X_n$ is needed; this is a second moment method.

For each cyclic starting position let $I_i$ indicate that its length-$k$ block is increasing. All $k!$ relative orders of its distinct entries are equally likely, so $\mathbb{E}{I}_i=1/k!$. By linearity of expectation,The indicators need not be independent for this calculation.

Write $X_k={\sum }_i{I}_i$. For two disjoint blocks, their relative orders are independent and each is increasing with probability $1/k!$, giving joint probability $1/(k!{)}^2$. If their cyclic starting positions differ by $s$, with $1\le s<k$, and $k\le n/2$, they overlap in just one interval. Both blocks increasing is then equivalent to their entire length-$k+s$ union increasing, so the joint probability is $1/(k+s)!$.

For each $s$ there are $2n$ ordered overlapping pairs, while there are $n(n-2k+1)$ ordered disjoint pairs and $n$ diagonal pairs. Thus for $k\ge 2$,The tail is bounded using $(k+s)!\ge k!(k+1{)}^s$:Dropping the negative correction in the disjoint term provesFor $k=1$, $X_1=n$ deterministically and the same bound is immediate.

Take $k=k_0=\min \{j:j!\ge n\}$. Then $k\to \infty$ and $(k-1)!<n\le k!$. Also $k=O(\log n)$, because $j!\ge 2^{j-1}$, so the needed block lengths are below $n/2$ for large $n$.

If $L\ge k+1$, then $X_{k+1}\ge 1$. Markov's inequality givesFor $j=k-2$, the expected count satisfies $\mu =n/j!>k-1\to \infty$. Part (ii) bounds its variance by $2\mu$, so Chebyshev's inequality givesCombining the tails provesThe blocks are consecutive in the cyclic order throughout; this is not the longest increasing subsequence with arbitrary omitted positions.

This establishes the longest increasing cyclic run of a random permutation concentration bound.

Let $I_i=1_{A_i}$ and $X={\sum }_i{I}_i$. DefineThe dependency sum is over ordered pairs, so each unordered overlapping pair is counted twice. Disjoint prescribed edge sets give independence.

Order the events. For each $i$, let $B_i$ be the event that all earlier events fail. Split it as $B_i=C_i\cap D_i$, where $C_i$ excludes earlier events with edge sets disjoint from $E_i$, and $D_i$ excludes the overlapping earlier events. These are down-sets. The event $A_i$ is a principal up-set, and it is independent of $C_i$ since their determining edge sets are disjoint.

If some $B_i$ has probability zero the desired zero-event bound is immediate. Otherwise the allowed conditional correlation inequality givesSince $\mathbb{P}(B_i)\le \mathbb{P}(C_i)$, it follows thatThe last step is the union bound under conditioning on $A_i$. Zero-probability events may simply be omitted, and a certain event makes the target probability zero. Finally the sequential product and $1-u\le e^{-u}$ giveThis proves the first Janson inequality with the dependency-sum convention explicit.

Independently retain each event with probability $t$, using a fresh Bernoulli mark for every index. Its retained occurrence is the original principal up-set together with its mark being one, so the first proof applies in the enlarged independent product space. The new parameters are ${\mu }_t=t\mu$ and ${\Delta }_t=t^2\Delta$: distinct retained events have independent marks, and pairs of disjoint original supports remain independent.

If no original event occurs, no retained event occurs. ThusWhen $\Delta \ge \mu >0$, choose $t=\mu /\Delta$ to minimize this quadratic exponent. It givesIf $\mu =0$, the appropriate trivial bound is one, rather than an undefined zero-over-zero exponent. The argument is the Janson lower-tail bound by independent thinning.

Count one copy for each four-element vertex set. It requires six independent edges, soDistinct copies share an edge exactly when their vertex intersection has size two or three. For each first copy, their numbers are $6\left(\genfrac{}{}{0ex}{}{n-4}{2}\right)$ and $4(n-4)$, respectively. The required union then has eleven or nine edges. Hence the ordered Janson dependency sum isFor large $n$, $\mu =\Theta (n^4)$ and $\Delta =\Theta (n^6)$, so $\Delta \ge \mu$ and ${\mu }^2/(2\Delta )\ge a{n}^2$ for some constant $a>0$. The second Janson inequality therefore givesThis is the asserted asymptotic bound. It can also be made valid for every $n\ge 4$ by decreasing $a$ to cover the finitely many smaller values, since each then has probability strictly below one of containing no copy. For $n<4$ the event has probability one and no positive exponential bound of this form can hold.

A dependency graph of events, written here as a loopless directed graph $D$ on the event indices, must satisfy a joint independence condition: for each $i$, $A_i$ is independent of the sigma-algebra generated by all $A_j$ with $j\ne i$ and no arc $i\to j$. In particular this means independence from every Boolean combination of those non-neighbour events, not merely pairwise independence. The outgoing neighbours list the events for which that independence is not required.

The asymmetric Lovász local lemma states that if there are numbers $0\le x_i<1$ withfor every index, thenFor maximum out-degree $d\ge 1$, take every $x_i=1/(d+1)$. Sinceone has $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge p$. Fewer than $d$ outgoing neighbours only increases the product, so the hypothesis is satisfied whenever $ep(d+1)\le 1$.

If $d=0$, take $x_i=p<1$; the neighbour products are empty and equal one. This separately covers the case in which $1/(d+1)$ would equal the forbidden value one. Thus the symmetric local lemma follows in every case.

For distinct indices put arcs in both directions whenever $S_i\cap S_j\ne \varnothing$. If $j$ is not an outgoing neighbour of $i$, every variable determining $A_j$ lies outside $S_i$. The entire family of such events is measurable with respect to variables outside $S_i$, whose sigma-algebra is independent of the variables inside $S_i$. Thus $A_i$ is independent of their whole generated sigma-algebra, establishing the required dependency graph of events. This justifies joint independence rather than just checking each pair.

Color every edge independently and uniformly with one of $k$ colors. For each unoriented simple four-edge path $P$, let $A_P$ be its repetition event. Its four distinct edges must satisfy two prescribed color equalities, so $\mathbb{P}(A_P)=k^{-2}$.

Events with edge-disjoint paths depend on disjoint random variables. A fixed edge lies on at most $4{\Delta }^3$ unoriented four-edge paths: count its four possible positions and two orientations, bound the remaining choices by ${\Delta }^3$, then divide the oriented path count by two. Thus the union of all paths sharing any of $P$'s four edges has size at most $16{\Delta }^3$. This union includes $P$ itself, so a dependency graph has $d+1\le 16{\Delta }^3$.

For $k\ge 8{\Delta }^{3/2}$,The symmetric Lovász local lemma yields positive probability of avoiding every event. Therefore such an edge coloring exists. If there are no four-edge paths the conclusion is immediate.

Use the same independent coloring, now with events indexed by unoriented six-edge paths. A repetition fixes the second three-edge color block to equal the first, so each event has probability $k^{-3}$. A fixed edge belongs to at most $6{\Delta }^5$ such paths, and a six-edge path has at most $36{\Delta }^5$ events in its closed dependency neighbourhood. Thus $d+1\le 36{\Delta }^5$.

For $k\ge 5{\Delta }^{5/3}$,The symmetric Lovász local lemma again guarantees a coloring avoiding all six-edge repetition events. Thus the required coloring exists, with the empty event family handled trivially.

Use both families of bad events in one asymmetric Lovász local lemma application. Give every four-edge event parameter $x_4$ and every six-edge event parameter $x_6$. A path of length $\ell$ shares edges with at most $4\ell {\Delta }^3$ four-edge paths and $6\ell {\Delta }^5$ six-edge paths. It therefore suffices to verifyThese slightly excessive exponents are safe even though they may count the event itself. Choose $x_4=2/k^2$ and $x_6=2/k^3$. For $k\ge C{\Delta }^{5/3}$, the sums of exponents times their parameters are bounded by constants times $C^{-2}{\Delta }^{-1/3}+C^{-3}$, uniformly in $\Delta \ge 1$. Taking $C$ sufficiently large makes each product of factors at least $1/2$, for example using $(1-x{)}^r\ge 1-rx$ and multiplying the two factors. Both displayed inequalities then hold. Positive probability of no bad event gives simultaneous avoidance of both lengths. Keeping two event parameters avoids replacing the rarer six-edge events by the larger four-edge probability.

These are the avoiding short repetitions in an edge coloring bounds, for repetitively colored paths.