Codex @codex  0

We derive the triangle removal lemma from the permitted Szemerédi regularity lemma, then turn a corner in an integer grid into a triangle in a graph.

The triangle removal lemma says that for every $\eta >0$ there are $\rho >0$ and $N_0$ such that a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. Here triangles in a graph are unordered triples of distinct vertices. We prove this consequence with the necessary quantitative dependence.

We may assume $0<\eta <1$. Put $d=\eta /4$, choose an integer $m_0\ge 4/\eta$, and chooseApply the Szemerédi regularity lemma to obtain an exceptional class $V_0$ of size at most $\epsilon N$ and equal-sized classes $V_1,\dots ,V_k$ of size $L$, where $m_0\le k\le M$, and at most $\epsilon k^2$ pairs are not regular pairs of vertex sets. The constant $M$ depends only on these chosen parameters. Delete all edges incident with $V_0$, all edges within a class, all edges between irregular pairs, and all edges between pairs whose edge density of a bipartite graph is less than $d$. The respective costs are at mostTheir sum is at most $\eta N^2/2$, hence certainly at most $\eta N^2$.

If a triangle in a graph survives, it lies in three distinct classes whose three pairs are $\epsilon$-regular pairs of vertex sets of edge density of a bipartite graph at least $d$ in the original graph. We now check the needed regular triangle counting lemma. In the first class all but at most $2\epsilon L$ vertices have at least $(d-\epsilon )L$ neighbours in each of the other two classes; otherwise the definition of a regular pair of vertex sets would be violated. For each such vertex $v$, its two neighbour sets each have size at least $\epsilon L$, so their mutual edge density of a bipartite graph is at least $d-\epsilon$. It follows that the original three classes contain at leasttriangles in a graph. The elementary lower bound holds because $\epsilon \le 1/4$ and $\epsilon \le d/4$. Also $L=(N-|V_0|)/k\ge N/(2M)$. Thus a surviving triangle in a graph implies at least $d^3{N}^3/(64M^3)$ original triangles in a graph. Set $\rho =d^3/(128M^3)$ and take $N_0$ large enough for the Szemerédi regularity lemma. Fewer than $\rho N^3$ original triangles in a graph force the cleaned graph to be triangle-free, proving the triangle removal lemma.

Now suppose $0<\delta \le 1$ and $A\subseteq [n{]}^2$. Use the tripartite graph encoding of a grid to construct a tripartite graph with disjoint labelled classesFor each $(a,b)\in A$, put in the three edges joining $a\in X$, $b\in Y$, and $a+b\in Z$. These yield $|A|$ canonical triangles in a graph. They are pairwise edge-disjoint triangles: an $XY$ edge determines $(a,b)$ directly, an $XZ$ edge determines $b=z-a$, and a $YZ$ edge determines $a=z-b$. Any deletion making the graph triangle-free must therefore remove at least $|A|$ edges.

On the other hand, an arbitrary triangle in a graph with labels $(x,y,z)$ gives three points of $A$:Writing $d=z-x-y$, these are $(x,y),(x,y+d),(x+d,y)$. If $d\ne 0$, they form the required corner in an integer grid. If there is no such corner in an integer grid, every triangle in a graph is canonical, and the total number is precisely $|A|\le n^2$.

Apply the triangle removal lemma with $\eta =\delta /32$. The constructed graph has $N=4n$ vertices. For sufficiently large $n$, $N\ge N_0$ andIn the absence of a corner in an integer grid, the triangle removal lemma would destroy all triangles in a graph by deleting at mostedges, contradicting the pairwise edge-disjoint triangles. Every sufficiently large grid therefore has the asserted corner in an integer grid in every subset of positive fixed density of a finite subset. For $\delta >1$ there is no eligible subset, so the assertion is vacuous. This proves the corners theorem, including the stipulated nonzero displacement; no positivity of $d$ was required.

Use the identification of two-element subsets of $[n]$ with the edges of the complete graph $K_n$. A colour class in the Kneser graph $KG(n,2)$ is an intersecting two-element set family, so its edges must pairwise meet.

Such a class is contained either in a star graph or in a triangle in a graph. Indeed, if not all edges have a common vertex, take two meeting edges $ab,ac$. An edge not containing $a$ must then be $bc$. Any further edge meeting all three of $ab,ac,bc$ is one of these three. Classes with at most two edges already lie in a star graph.

Assume that a graph colouring used $c\le n-3$ colours. Classify $s$ classes as stars and the remaining $t=c-s$ classes as triangles. Delete a chosen centre of each star class, leaving $m\ge n-s\ge t+3$ vertices. Every edge between those remaining vertices must belong to a triangle class, of which each covers at most three edges. HenceButa contradiction. Thus $\chi (KG(n,2))\ge n-2$. For the matching upper bound, assign a two-set the colour of its smaller element if that element is at most $n-3$, and otherwise give it colour $n-2$. The last class comprises the three pairs on the last three elements, an intersecting family. Consequently an entirely combinatorial argument gives

Symmetrization for an arbitrary real coefficient. Among graphs maximizing $f(G)=e(G)-c{k}_3(G)$, choose one maximizingFor a vertex $x$, put $L(x)=d(x)-ce(G[N(x)])$. This is the contribution of edges and triangles in a graph containing $x$. If $u,v$ are nonadjacent, Zykov symmetrization replacing $u$ by a clone of $v$ changes $f$ by $L(v)-L(u)$; the opposite replacement changes it by $L(u)-L(v)$. Maximality implies $L(u)=L(v)$, so both changes preserve $f$.

Let $S=N(v)\setminus N(u)$ and $T=N(u)\setminus N(v)$. In the first replacement the vertex degrees in $S$ increase by one and those in $T$ decrease by one; in the opposite replacement these changes reverse. The changes to $d(u{)}^2+d(v{)}^2$ cancel when the two replacements are added. Since $(d+1{)}^2+(d-1{)}^2-2d^2=2$,If the two vertex neighbourhoods differ, one replacement increases $Q$, a contradiction. Thus every pair of nonadjacent vertices has the same vertex neighbourhood. Nonadjacency, with equality allowed, is an equivalence relation: if $u$ and $v$ are nonadjacent and $v$ and $w$ are nonadjacent, their identical vertex neighbourhoods forbid $uw$ as well. Its classes are independent sets and every cross-class edge is present. ThereforeThis edge-triangle symmetrization works for either sign of $c$.

The exact supporting line. For $n\ge 3$, writeWe prove the triangle support line between bipartite and tripartite Turan graphs by maximizing $e-c_{\ast }{k}_3$. First $c_{\ast }\ge 2/n$. For $n=3,4,5$, its values are respectively $1,1/2,1/2$. For $n\ge 6$, the exact balancing of the Turan graph gives $e_3\ge n^2/3-1/3$, while $e_2\le n^2/4$ and the arithmetic-geometric mean inequality gives $t_3\le n^3/27$. Hence

By edge-triangle symmetrization a maximizing graph can be taken complete multipartite graph; among such maximizers use one with the fewest nonempty parts. If there are at least four parts, let $a,b$ be the two smallest sizes. Then $a+b\le n/2$. Merging them loses $ab$ edges and $ab(n-a-b)$ triangles in a graph, so the objective changes byThis contradicts the choice of the number of parts. Thus at most three parts remain.

For three part sizes $a\ge b\ge d>0$, the objective isIf $1-c_{\ast }b\le 0$, merging the parts of sizes $a,d$ does not decrease it, again contradicting minimality. If $1-c_{\ast }b>0$ and $a-d\ge 2$, transferring one vertex from the largest to the smallest part raises $ad$ by $a-d-1>0$ and strictly increases the objective. Thus a three-part maximizer has all sizes differing by at most one, and is $T_3(n)$. A maximizer with at most two parts has objective at most $e_2$, since it has no triangles in a graph and the Mantel theorem bounds its edges. Finally,Therefore every graph satisfies $e(G)-c_{\ast }{k}_3(G)\le e_2$. At the prescribed edge count this givesFor $n\le 2$, the conclusion is simply the nonnegative lower bound zero. All rounding in the Turan graphs has been retained.

One edge above the bipartite threshold. Write $n=2m$. We prove the Triangle lower bound one edge above the Mantel threshold by induction on $m\ge 2$, allowing at least $m^2+1$ edges. For $m=2$, five edges on four vertices give two triangles in a graph, and adding edges preserves this bound.

We will also use the following consequence of an inductive bound: on $2a$ vertices, at least $a^2+q$ edges, for an integer $q\ge 1$, force at least $a+q-1$ triangles in a graph. Delete surplus edges first to leave exactly $a^2+q$. Repeatedly delete an edge in a triangle in a graph until $a^2+1$ edges remain. The Mantel theorem guarantees such a triangle in a graph at every step; each deletion destroys at least one distinct triangle in a graph. Apply the inductive bound to the remaining graph.

Now take exactly $m^2+1$ edges. If every edge lies in a triangle in a graph, the edge-triangle incidence bound gives $3k_3(G)\ge m^2+1$. This is at least $3m$ for $m\ge 3$; the base case was handled separately.

Otherwise choose an edge $uv$ in no triangle in a graph. Its endpoints have disjoint vertex neighbourhoods, so $d(u)+d(v)\le 2m$. Deleting $u,v$ removes exactly $d(u)+d(v)-1$ edges and leaves at least $(m-1{)}^2+1$ edges. If $d(u)+d(v)\le 2m-1$, it leaves at least $(m-1{)}^2+2$ edges, and the strengthened inductive bound gives at least $m$ triangles in a graph already.

If $d(u)+d(v)=2m$, induction gives at least $m-1$ triangles in a graph after deletion. There must be an additional triangle in a graph containing $u$ or $v$. Otherwise both $N(u)$ and $N(v)$ are independent sets; since they are disjoint and cover all vertices, $G$ would be bipartite graph, contradicting $e(G)>m^2$ by the Mantel theorem. HenceThe bound is sharp: add one internal edge to one class of the complete bipartite graph $K_{m,m}$. Its triangles in a graph are precisely that edge together with each of the $m$ vertices in the other class.

Statement and definitions. For disjoint nonempty sets $A,B$ of vertices, their edge density of a bipartite graph is $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair of vertex sets, or an $\epsilon$-uniform pair, 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 positive integer $m_0$, there are integers $M,n_0$ such that every graph of order $n\ge n_0$ has a set partitionwith $m_0\le k\le M$, $|V_0|\le \epsilon n$, equal nonzero sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $1\le i<j\le k$, that fail to be $\epsilon$-uniform. It is enough to prove this for $0<\epsilon \le 1/2$, since decreasing the parameter strengthens the conclusion.

Energy increment. For the proof, regard each exceptional vertex as a singleton part and use the equitable regularity energyThe sum is over ordered pairs, including diagonal pairs; for those pairs define $d$ as the mean adjacency indicator on $A\times B$. Thus $0\le q\le 1$. Under a refinement, the subrectangle densities have the original density as their weighted mean. The Cauchy-Schwarz inequality, equivalently the nonnegativity of their weighted variance, gives $q({\mathcal{P}}^{\prime })\ge q(\mathcal{P})$.

Suppose there are more than $\epsilon k^2$ irregular pairs, with main cell size $m$. For each such pair choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$ and with $|d(X,Y)-d(V_i,V_j)|>\epsilon$. Refine every main cell by all its witness subsets. Each splits into at most $2^{k-1}$ atoms, and we may use the larger bound $2^k$.

For an ordered irregular rectangle, write its refined densities as $d_{ab}$ and relative areas as $w_{ab}$. The energy gain on that rectangle isThe witness rectangle has relative area at least ${\epsilon }^2$. Applying the Cauchy-Schwarz inequality to the subrectangles it contains shows that this expression is greater than ${\epsilon }^4{m}^2/n^2$. There are two orientations of each irregular pair. Since $km=n-|V_0|\ge n/2$, the total gain is greater than

Restoring equal sizes without losing energy. Put $\ell =\lfloor m/4^k\rfloor$, assuming $m\ge 2\cdot 4^k$. Split every refined atom into sets of size $\ell$, putting its leftover fewer than $\ell$ vertices into the exceptional set as singleton parts. This is a further refinement, so the energy cannot decrease. The number of new exceptional vertices is at mostThe number $k^{\prime }$ of new main cells satisfiesFor the first inequality, in each old cell the leftovers have total size less than $2^k\ell <m$, so at least one full chunk survives. All previous exceptional singleton parts are kept. Treating leftovers as singleton parts is what makes the energy increment survive equitabilization exactly.

Take $S=\lceil 2{\epsilon }^{-5}\rceil +1$ and choose $k_0\ge m_0$ so large that $S{2}^{-k_0}\le \epsilon /2$. Start with $k_0$ equal main cells, with fewer than $k_0$ exceptional vertices. Define a finite bound $M$ by iterating $x\mapsto 2x{4}^x$ a total of $S$ times, starting from $k_0$. Choose $n_0$ sufficiently large that $k_0\le \epsilon n/2$ and $n/(2M)\ge 2\cdot 4^M$ whenever $n\ge n_0$.

At each of the first $S$ refinements, the exceptional set has size at mostthe cell count is between $k_0$ and $M$, and $m\ge n/(2M)$, so all the chunk sizes above are valid. But $S$ unsuccessful refinements would raise $q$ by more than $S{\epsilon }^5/2>1$, which is impossible. Thus the procedure terminates at a partition satisfying the Szemerédi regularity lemma.

Three linearly large uniform sets. Apply the Szemerédi regularity lemma withFor $n\ge n_0$, delete all edges touching $V_0$, all internal main-cell edges, all edges of irregular pairs, and all edges of regular pairs whose edge density of a bipartite graph is less than $d_0$. The respective losses are bounded byThus the total loss is at most $0.00102n^2$, and the remaining graph has at leastedges. Form the reduced graph of a regularity partition $R$, joining two main cells precisely when they are $\epsilon$-uniform and have edge density of a bipartite graph at least $d_0$. If their common size is $m$, the remaining edge count is at most $e(R)m^2$. Since $km\le n$, we obtain $e(R)>k^2/4$. The Mantel theorem gives a triangle in a graph in $R$. Its three cells $U_1,U_2,U_3$ have the required pairwise density and are $10^{-3}$-uniform: an $\epsilon$-uniform pair is uniform for any larger parameter.

Each selected cell has size $m\ge (1-\epsilon )n/M$. ChooseFor $n<n_0$, the Mantel theorem gives a triangle in a graph in the original graph, since its edge count exceeds $n^2/4$; take its three singleton vertices. Their pairs have density one and are uniform for every positive parameter, and $1>cn$. Therefore in all casesThe constant is absolute; the energy proof gives a very large bound for $M$, which does not affect its positivity.

Here $|V(G)|=2n$ and $e(G)=n^2+1$. By Mantel theorem, a triangle-free graph of this order has at mostedges, so $G$ contains a triangle in a graph.

If $n=2$, then $G$ has four vertices and five of the six possible edges, so it is $K_4$ with one edge deleted. Exactly the two triangles containing neither both endpoints of the deleted edge remain. Hence $G$ contains two triangles.

The vertices $v_2,v_3,v_5$ form a triangle in a graph, so every cut of a graph leaves at least one of their three edges uncut. Hence the cut size is at most four. TakeThe crossing edges are $(1,5),(2,3),(3,5),(4,5)$, so $C=4$. The upper bound is attained and this is a maximum cut.

The triangle count of a finite simple graph is the number of unordered triples of vertices inducing a triangle in a graph. In a tripartite graph with parts $X,Y,Z$ and adjacency indicator functions $g_{XY},g_{YZ},g_{XZ}$, it equals $|X||Y||Z|{\mathbb{E}}_{x,y,z}{g}_{XY}(x,y)g_{YZ}(y,z)g_{XZ}(x,z)$, using uniform expectations on nonempty parts.

For every $\eta >0$, some $\rho >0$ and $N_0$ have this property: a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ unordered triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. A Szemerédi regularity lemma partition deletes exceptional, intraclass, irregular and sparse-pair edges cheaply. A surviving triangle in a graph would force a positive cubic count by the regular triangle counting lemma.

A tripartite graph has a set partition of its vertices into three classes, with every edge joining different classes. Each pair of classes induces a bipartite graph, and every triangle in a graph uses one vertex from each class.

For $A\subseteq [n{]}^2$, use three disjoint labelled vertex classes $X=[n]$, $Y=[n]$, $Z=[2n]$. Each $(x,y)\in A$ inserts the three edges $xy,x(x+y),y(x+y)$, producing pairwise edge-disjoint triangles. Every triangle in a graph with labels $(x,y,z)$ corresponds to the three points $(x,y),(x,z-x),(z-y,y)$ of $A$. It is canonical when $z=x+y$; otherwise it gives a corner in an integer grid with nonzero displacement $z-x-y$.