Past exam of the graph theory course of the University of Oxford / 2011 / 3

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.