Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 4

For disjoint nonempty vertex sets $A,B$, writeThe pair $(A,B)$ is $\epsilon$-uniform ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$, and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0$ there are $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, equal sizes $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ pairs $(V_i,V_j)$ that are not $\epsilon$-uniform.

The triangle embedding lemma for regular pairs states that if $0<\epsilon <1/2$, the three pairs among disjoint nonempty sets $A,B,C$ are $\epsilon$-uniform, and all three densities are at least $2\epsilon$, then the graph contains a triangle with one vertex in each set.

In an $\epsilon$-uniform pair $(A,B)$ of density $d$, fewer than $\epsilon |A|$ vertices of $A$ have fewer than $(d-\epsilon )|B|$ neighbours in $B$; otherwise those vertices and $B$ would violate uniformity. Apply this observation to $(A,B)$ and $(A,C)$. Since $2\epsilon <1$, choose $a\in A$ that is typical for both pairs. Thensatisfy $|B^{\prime }|\ge \epsilon |B|$ and $|C^{\prime }|\ge \epsilon |C|$. Uniformity of $(B,C)$ givesThus some $bc$ joins $B^{\prime }$ to $C^{\prime }$, and $abc$ is the required triangle.

For fixed disjoint $A,B$, the random variable $e(A,B)$ has the binomial distribution $\mathrm{Bin}(|A||B|,p)$. A two-sided Chernoff bound givesWhen $|A|,|B|\ge n/\log n$, this is at mostThere are at most $3^n$ ordered disjoint pairs $(A,B)$, since each vertex can lie in $A$, in $B$, or in neither. The union bound therefore makes the probability of any failure at mostwhich proves the simultaneous estimate.

Fix the requested $\epsilon >0$ and choose much smaller constants $\eta ,\delta ,\rho >0$ in that order. Apply the Szemerédi regularity lemma with regularity parameter $\rho$ and a sufficiently large lower bound $m_0$ to a largest triangle-free subgraph $F\subseteq G$. Letbe the resulting equitable partition, and form the reduced graph of a regularity partition $R$ on $[m]$ by joining $i$ and $j$ when $(V_i,V_j)$ is $\rho$-uniform in $F$ and has $F$-density at least $\delta$.

Choose $\rho <\delta /2$. If $R$ contained a triangle, the triangle embedding lemma for regular pairs would give a triangle in $F$. Thus $R$ is triangle-free, and Turan theorem gives

Part (c), with error $\eta$, holds simultaneously for every pair of sets of size at least $n/\log n$. Since $m$ is bounded independently of $n$, all regularity classes and their halves satisfy this size condition for large $n$. It follows that every cross-pair contains at most $(p+\eta )|V_i||V_j|$ edges of $G$. It also givestake a bipartition of $V_i$ carrying at least half its internal edges and apply the cross-pair estimate.

Now count the edges of $F$. Pairs represented in $R$ contribute at mostThe exceptional set, the at most $\rho m^2$ irregular pairs, pairs of $F$-density below $\delta$, and edges inside classes together contribute at mostChoose $\eta$, then $\delta ,ho$, and finally $m_0^{-1}$ small enough in terms of $p\epsilon$. The total is at mostwith high probability, as required.