Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 9 (Extremal Graph Theory)

Write $K_s(t)$ for a balanced complete multipartite blow-up with $s$ classes of size $t$. In the nonvacuous range $0<\epsilon <1/r$, the answer isWe prove both bounds, including the quantitative lower bound.

First, suppose a bipartite graph with parts $A,B$, of sizes $m,N$, has at least $pmN$ edges. For any integer $s\le pm/2$, counting pairs consisting of an $s$-subset of $A$ and a common neighbour in $B$ givesThe inequality follows from discrete convexity: $\left(\genfrac{}{}{0ex}{}{x+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{x}{s}\right)=\left(\genfrac{}{}{0ex}{}{x}{s-1}\right)$ is nondecreasing, so balancing integer degrees of vertices minimizes their sum. Consequently some $S$ hasThe product estimate uses $\lfloor pm\rfloor -j\ge pm-s$ for $0\le j<s$. This is a common neighbourhood from bipartite density bound.

We next prove by induction on $q\ge 1$ that, for every fixed $\alpha >0$, a graph $J$ of order $N$ with minimum degree at least $(1-1/q+\alpha )N$ contains $K_{q+1}(\lfloor c\log N\rfloor )$, for some $c=c(q,\alpha )>0$ and all sufficiently large $N$. Impossible minimum-vertex degree parameters need no argument. For $q=1$, take two copies of $V(J)$ with adjacency given by $J$. The preceding count with $p=\alpha$ and $s=\lfloor c\log N\rfloor$, where $c\log (2/\alpha )<1/2$, gives at least $\sqrt{N}$ common neighbours. The selected vertices and their common neighbours are disjoint in $J$, since a vertex is not its own neighbour. Selecting $s$ common neighbours gives $K_2(s)$.

For $q\ge 2$, the minimum degree hypothesis implies the induction hypothesis for $q-1$, for example with excess $1/[q(q-1)]$. Thus $J$ contains $K_q(m)$ with $m=\lfloor a\log N\rfloor$ for a positive constant $a$. Pair the vertices in its classes into $m$ disjoint transversal cliques $C_1,\dots ,C_m$, each of order $q$. By the union bound, every $C_i$ has at leastcommon neighbours. Form an auxiliary bipartite graph between these $m$ cliques and the $N$ vertices, using common-neighbour incidence, and put $p=q\alpha$. Choose $c>0$ small enough that $c<pa/3$ and $c\log (2/p)<1/2$. The count above, with $s=\lfloor c\log N\rfloor$, gives $s$ cliques with at least $\sqrt{N}$ simultaneous common neighbours. Their vertices form $q$ classes of size $s$, and $s$ of those common neighbours form the last class. None of the common neighbours belongs to a selected clique, because that would require a loop. This proves the logarithmic clique blow-up from minimum degree assertion.

To pass from an edge count to minimum degree, put $b=1-1/r+\epsilon$ and $a=b-\epsilon /2$. Repeatedly remove a vertex whose current degree of a vertex is below $a$ times the current order. If the process reaches order $m$, its deleted edges and remaining edges giveThus $(1-a)m^2\ge (\epsilon /2)n^2-O(n)$. In particular, for a fixed sufficiently small $\gamma >0$, the process cannot reach $m=\lfloor \gamma n\rfloor$: the displayed inequality would fail. It stops earlier with a subgraph of order $N\ge \gamma n$ and minimum degree at least $(1-1/r+\epsilon /2)N$. The induction just proved supplies $K_{r+1}(\lfloor c\log N\rfloor )$, hence a lower bound $c^{\prime }\log n$ on $t(r,\epsilon ,n)$. In particular, the guaranteed part size tends to infinity.

For the upper bound, choose a fixed $p$ with $b<p<1$ and take a binomial random graph $G(n,p)$. Its edge count has expectation $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and variance $p(1-p)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. The Chebyshev inequality shows that $e(G)\ge b\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ with probability tending to one. The expected number of labeled copies of $K_{r+1}(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/[r\log (1/p)]$, this tends to zero. The Markov inequality therefore shows that with positive probability both the required edge density holds and there is no such copy. This proves $t(r,\epsilon ,n)=O(\log n)$ and completes the random obstruction to larger clique blow-ups argument.

There is a necessary qualification to the density parameter. If $\epsilon =1/r$, the only eligible graph is the complete graph, and $t(r,1/r,n)=\lfloor n/(r+1)\rfloor$. If $\epsilon >1/r$ and $n\ge 2$, there are no eligible simple graphs; the universal assertion is vacuous for every $t$, so the printed maximum has no finite value in that range.

Each vertex of a bipartite graph has a strict preference ordering of its neighbours; every neighbour is preferred to being unmatched. A stable matching in a bipartite graph is a matching in a graph with no blocking edge: an unused edge blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any neighbour. Stability does not require a perfect matching in a graph.

For existence, run the Gale-Shapley algorithm. Whenever a vertex in the first part is unmatched and has an untried neighbour, it proposes to its most preferred untried neighbour. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a matching in a graph. Suppose an edge $bg$ blocked this final matching in a graph. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the edge is in the matching in a graph. Both alternatives contradict blocking. Every finite bipartite preference instance therefore has a stable matching.

For the mutual-worst edge in stable matchings, let $M,N$ be stable matchings with $bg\in M$ and $bg\notin N$. We give the argument using alternating graph components including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next vertex to have and prefer an $N$-partner. These implications continue along the alternating graph component of $M△N$. They cannot stop, because at a missing next edge the preceding edge would block the appropriate matching in a graph. They also cannot close into a cycle in a graph, since the graph component already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.

Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating graph component, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next vertex in $b$'s part to prefer its $N$-partner, and so on. A graph path graph component is impossible by the same endpoint argument, so this is a cycle in a graph. Thus throughout this cycle in a graph the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence an edge ranked last by both endpoints, if present in one stable matching, is present in every stable matching.

For the list edge coloring assertion, let $\Delta$ be the maximum degree. We first prove that the chromatic index is $\Delta$. Use induction on the number of edges, with a proper $\Delta$-edge coloring of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the edges of colors $a,b$ form alternating graph paths and even cycles in a graph. The graph component containing $u$ cannot contain $v$: an alternating graph path from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the graph component containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound ${\chi }^{\prime }(G)\ge \Delta$ is immediate at a vertex of vertex degree $\Delta$.

Fix such a proper coloring $c:E(G)\to \{1,\dots ,\Delta \}$. Orient the line graph toward the smaller color at vertices in the first part of $G$, and toward the larger color at vertices in the second part. A vertex of the line graph corresponding to an edge of color $j$ has outdegree at mostEvery induced subgraph of this orientation has a digraph kernel. Indeed, restrict to its edge set in the original bipartite graph, give first-part vertices a preference for smaller colors and second-part vertices a preference for larger colors, and choose a stable matching. Its edges form an independent set in the line graph. Every edge outside the matching in a graph has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing edge to the independent set. This proves that the orientation is a kernel-perfect directed graph.

Here is the kernel list-coloring lemma with its proof. If a kernel-perfect directed graph $D$ has lists satisfying $|L(v)|\ge d_D^{+}(v)+1$, choose any color $a$ appearing in a list and a digraph kernel $K$ of the induced subgraph on vertices whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining vertex that loses a color had an outgoing neighbour in $K$, so its outdegree decreases by at least one; the list inequality persists. Vertices not losing a color also retain the inequality. Induction on the number of vertices completes a proper list coloring.

Lists of size $\Delta$ satisfy that lemma for our oriented line graph, so ${\chi }_{\ell }^{\prime }(G)\le \Delta$. Identical lists show ${\chi }_{\ell }^{\prime }(G)\ge {\chi }^{\prime }(G)$. Consequently the Galvin theorem for bipartite list edge coloring givesThe empty graph is immediate; if parallel edges are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The outdegree bound still holds, and the same stable matching and digraph kernel proof applies with preferences on incident edges.

A linked graph is $k$-linked if it has at least $2k$ vertices and, for every choice of distinct terminals $s_1,\dots ,s_k,t_1,\dots ,t_k$, it has pairwise vertex-disjoint graph paths joining $s_i$ to $t_i$ for all $i$. The pairing is prescribed, which is stronger than the unpaired conclusion of the Menger theorem.

We prove the rooted dense minor linkage step carefully. We first prove the rooted branch-set reduction. Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs exactly the desired family, contradicting minimality and proving the branch-set reduction.

Return to the given $22k$-connected graph. By the allowed assumption it has a graph minor $H$ with $2\delta (H)\ge h+4k-1$, where $h=|H|$. Put $d=h-1-\delta (H)$. ThenTake a branch-set model of $H$ and the $2k$ prescribed terminals as $S$. The branch sets are connected and each misses at most $d$ of the others. The separation hypothesis holds with $q=2k$: a separation of order below $2k$ avoiding a branch set would separate a surviving terminal from that set, contrary even to $2k$-connectivity. Since $h\ge d+3k$, the reduction applies. It produces $m=h-k$ sets with $s_i\in D_i$, $t_i\in D_{k+i}$, each terminal set missing at most $d$ of the $m-2k$ nonterminal sets. For each pair $D_i,D_{k+i}$ at leastnonterminal sets are adjacent to both. Choose different such sets for the $k$ pairs successively. The connected graph property inside the three sets and the two joining edges give a graph path from $s_i$ to $t_i$; take a simple graph path within their union. Different graph paths use disjoint sets. We have provedIn fact the argument proves the stronger transfer statement with $2k$-connectivity and the stated dense graph minor.

For the negative assertion, it suffices to give a value of $k$ for which the proposed general implication fails. Take $k=2$ and the graph on cyclic indices $0,\dots ,7$ in which two indices are adjacent when their cyclic distance is one or two. This is the four-connected planar obstruction to two-linkage. Draw the even cycle in a graph $0,2,4,6$ as the outer square, the odd cycle in a graph $1,3,5,7$ as an inner square rotated by $45$ degrees of vertices, and join each odd vertex to the two neighbouring even vertices; the annulus is triangulated without crossings. The outer face has vertices $0,2,4,6$ in this order.

Deleting at most three vertices leaves the graph connected. In cyclic order, consecutive surviving vertices are joined unless separated by a run of at least two deleted vertices. Disconnection requires two distinct such runs, hence at least four deletions. Conversely deleting the four neighbours of a vertex isolates it, so the vertex connectivity is exactly four. Disjoint graph paths joining $0$ to $4$ and $2$ to $6$ cannot exist: both would lie in the closed disk complementary to the outer face, and their endpoints alternate on its boundary. A first such graph path is a crosscut of the disk; the Jordan curve theorem puts the other two endpoints on opposite sides, forcing the second graph path to meet it. ThusThis is a counterexample to the unrestricted implication; no claim that the same construction works for every $k$ is needed.

We use the following precise form of the Szemerédi regularity lemma. For every $0<\eta <1/2$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith at most $\eta k^2$ irregular unordered pairs among the nonexceptional classes. Here $d(A,B)=e(A,B)/(|A||B|)$ for disjoint nonempty sets, and $(A,B)$ is an $\eta$-regular pair ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \eta |A|$, $|Y|\ge \eta |B|$.

For the proof, let $f(x,y)$ be the adjacency indicator, including $f(x,x)=0$, and define $d(A,B)$ by averaging $f$ on $A\times B$ even for diagonal cells. The regularity energy of a partition $\mathcal{P}$ isEvery exceptional vertex is represented by its own singleton cell in this energy. If a rectangle $A\times B$ is refined into smaller rectangles with densities $d_{ij}$ and weights $w_{ij}=|A_i||B_j|$, expanding the square gives the refinement variance identity for regularity energyThus refinement never decreases energy.

Suppose an equitable partition with $k$ classes of size $L$ fails the desired conclusion. For every irregular pair choose witness subsets $X\subseteq V_i$, $Y\subseteq V_j$, each of size at least $\eta L$, whose density differs from $d(V_i,V_j)$ by more than $\eta$. Split each class by all witness subsets involving it. Each class has at most $2^{k-1}$ atoms. On a witness rectangle, the weighted mean of $d_{ab}-d(V_i,V_j)$ is $d(X,Y)-d(V_i,V_j)$. The Cauchy-Schwarz inequality therefore bounds the energy increment on this rectangle below byThe different original cell pairs have disjoint rectangles. More than $\eta k^2$ irregular unordered pairs, with both orientations counted in the energy, thus increase it by more than $2{\eta }^5{k}^2{L}^2/n^2$. As long as $|V_0|\le \eta n<n/2$, this is greater than ${\eta }^5/2$, and in particular greater than ${\eta }^5/4$.

Restore equitability by dividing each atom into pieces of common size $\ell =\lfloor L/4^k\rfloor$, moving each leftover vertex into the exceptional set as a singleton energy cell. This remains a refinement, so the energy gain persists. There are at most $k{2}^k$ atoms, so the additional exceptional vertices number at mostIf $L\ge 2\cdot 4^k$, then $\ell \ge L/(2\cdot 4^k)$, and the new number $k^{\prime }$ of equal cells satisfies $k\le k^{\prime }\le 4k{4}^k$. For the lower bound, within each old class the leftover count is at most $2^k\ell <L$, so at least one full new cell survives. For the upper bound, $n/\ell \le 2(n/L)4^k\le 4k{4}^k$, using $kL\ge n/2$. This proves equalization with a controlled exceptional set without any energy loss.

Put $T=\lceil 4{\eta }^{-5}\rceil +1$. Choose $k_0\ge m_0$ with $T{2}^{-k_0}\le \eta /2$. Start with $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Iterate the bounded recurrence $k\mapsto 4k{4}^k$ $T$ times to obtain a bound $M$. Choose $n_0$ so large that the initial remainder is at most $\eta n/2$ and, for every $k\le M$, $(1-\eta )n/k\ge 2\cdot 4^k$. The total exceptional set remains at most $\eta n$, since at most $T$ rounds each add at most $n{2}^{-k_0}$. Each failing round raises an energy in $[0,1]$ by more than ${\eta }^5/4$, so fewer than $T$ rounds can fail. This proves the lemma with all constants independent of the input graph.

For the application, write $h=|V(F)|$ and $\chi (F)=r+1$. We may replace the given tolerance by a smaller one, so assume $0<\epsilon <1$. Set $d=\epsilon /4$, take $m_0\ge 8/\epsilon$, and chooseApply the lemma and delete all edges incident with $V_0$, all edges inside a class, all edges across irregular pairs, and all edges across regular pairs of density below $d$. The resulting spanning subgraph $H$ loses at mostLet $R$ be the reduced graph of a regularity partition, whose edges represent the surviving regular pairs of density at least $d$. We show that a copy of $K_{r+1}$ in $R$ forces a copy of $F$ in $G$.

Choose a proper $(r+1)$-coloring of $F$ and assign its color classes to the corresponding clusters. Embed its vertices one at a time. For each unembedded vertex maintain the candidate set in its cluster consisting of unused vertices adjacent to all already embedded neighbours. After at most $h$ restrictions its size is at least $(d-\eta {)}^{h}L-h\ge (d/2{)}^{h}L-h$. This last quantity is at least $2h\eta L$ when $L$ is large, so every such candidate set is large enough for regularity. In an $\eta$-regular pair of density $p\ge d$, fewer than $\eta L$ vertices on one side have fewer than $(p-\eta )|Y|$ neighbours in any fixed set $Y$ on the other side of size at least $\eta L$: otherwise these vertices and $Y$ violate regularity. For the vertex currently being embedded, there are at most $h$ relevant future candidate sets. At most $h\eta L$ vertices are bad for one of them. Its own candidate set has at least $2h\eta L$ vertices, so an unused good vertex can be chosen. All future candidate sets shrink by at most the factor $d-\eta$, apart from the removal of a used vertex; the stated size bound follows inductively, since the accumulated removals are at most $h$. This completes the graph embedding lemma for regular pairs in the form needed here.

Since $G$ is $F$-free, $R$ is $K_{r+1}$-free. Any $K_{r+1}$ in $H$ would use distinct clusters, because intraclass edges were deleted, and project to a $K_{r+1}$ in $R$. ThereforeThe required threshold on $n$ depends only on $F$ and $\epsilon$, since $k\le M$ makes every nonexceptional cluster sufficiently large.