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.

Uniform expectations require nonempty finite sets; assume this throughout the analytic argument. For real-valued functions on $X\times Y$, define the box norm byAll four variables are sampled as independent random variables with replacement, so repeated coordinates are included. The defining fourth power equalsIf it vanishes, every summand vanishes. In particular, the terms $y_0=y_1=y$ give ${\mathbb{E}}_{x}f(x,y{)}^2=0$ for each $y$, so $f=0$. Absolute homogeneity of a norm follows directly: $\Vert af{\Vert }_{\square }=|a|\Vert f{\Vert }_{\square }$.

For the triangle inequality, prove the mixed box Cauchy-Schwarz inequality. WriteSeparating the two $y$ averages and applying the Cauchy-Schwarz inequality in $(x_0,x_1)$ givesExpanding the square and reversing the order of finite sums,by a second Cauchy-Schwarz inequality. Thus $|\Lambda |\le {\prod }_{i,j}\Vert f_{ij}{\Vert }_{\square }$. Expand $\Lambda (f+g,f+g,f+g,f+g)$ into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to $(\Vert f{\Vert }_{\square }+\Vert g{\Vert }_{\square }{)}^4$. Taking fourth roots yields the triangle inequality. Together with definiteness of a norm and absolute homogeneity of a norm, this proves the box norm is a norm. Complex functions require conjugates and are outside the printed real-valued convention.

For the bilinear correlation bound for the box norm, use the normalized L2 norm: let $B={\mathbb{E}}_{x,y}f(x,y)u(x)v(y)$ and $\Vert u{\Vert }_2^2={\mathbb{E}}_{x}u(x{)}^2$, $\Vert v{\Vert }_2^2={\mathbb{E}}_{y}v(y{)}^2$. The Cauchy-Schwarz inequality in $y$ givesThe remaining factor is ${\mathbb{E}}_{x,x^{\prime }}u(x)u(x^{\prime }){\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. By the Cauchy-Schwarz inequality in $(x,x^{\prime })$, its magnitude is at mostTaking square roots proves

For the tripartite graph, assume its parts are nonempty and write $g_{XY},g_{YZ},g_{XZ}$ for its adjacency indicator functions. Let $f=g_{XY}-\alpha$, so $\Vert f{\Vert }_{\square }\le c$. The normalized triangle count isThe constant-degree hypothesis is exactly ${\mathbb{E}}_y{g}_{YZ}(y,z)=\beta$ for each $z$. Therefore the contribution of the constant $\alpha$ isFor fixed $z$, apply the bilinear correlation bound for the box norm with $u_z(x)=g_{XZ}(x,z)$ and $v_z(y)=g_{YZ}(y,z)$. Since these are indicator functions, $\Vert v_z{\Vert }_2^2=\beta$ and $\Vert u_z{\Vert }_2^2=d_X(z)$, the fraction of $X$ adjacent to $z$. Averaging and applying the Cauchy-Schwarz inequality in $z$ gives the sharper triangle counting with one box-uniform pair and constant opposite degree estimateMultiplying by $|X||Y||Z|$ yieldsThe middle bound also handles $\beta =0$ or $\gamma =0$, when the triangle count is zero.

To connect explicitly with the suggested expansion, put $f_2=g_{YZ}-\beta$, $f_3=g_{XZ}-\gamma$. Both have overall mean zero, and ${\mathbb{E}}_y{f}_2(y,z)=0$ for every $z$. Consequently ${\mathbb{E}}_{x,y,z}{f}_2(y,z)f_3(x,z)=0$; all terms with constant $\alpha$ reduce to $\alpha \beta \gamma$. The terms containing $f$ combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the triangle count itself is zero, but the printed uniform expectations and edge density of a bipartite graph values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.

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.

Let a tripartite graph have nonempty parts $X,Y,Z$, pair edge density of a bipartite graph values $\alpha ,\beta ,\gamma$ on $XY,YZ,XZ$, and $\Vert G(X,Y)-\alpha {\Vert }_{\square }\le c$. If every $z\in Z$ has exactly $\beta |Y|$ neighbors in $Y$, its normalized triangle count $\tau$ obeysThe constant-degree assumption makes the contribution of the constant $\alpha$ exactly $\alpha \beta \gamma$. For each fixed $z$, apply the bilinear correlation bound for the box norm to the indicator functions of its two vertex neighbourhoods. Their squared $L^2$ norms are $\beta$ and the relative $X$-degree of $z$. Average over $z$ and use the Cauchy-Schwarz inequality to bound the mean square root of that degree by $\sqrt{\gamma }$.