三角形除去補題

$\varepsilon>1$ なら、すべての辺を除けば $\lvert E\rvert\le n^2/2<\varepsilon n^2$ なので、どの $\delta$ でもよい。以下 $0<\varepsilon\le1$ とし、$M:=M(\varepsilon/4)$ として
$$ \delta:=\frac16\Bigl(1-\frac\varepsilon2\Bigr)\Bigl(\frac\varepsilon4\Bigr)^3\Bigl(\frac{\varepsilon}{4M}\Bigr)^3 $$
とおく。$G$ を $t(G)<\delta n^3$ を満たす $n$ 頂点のグラフとする。
段 1（分割）。 正則性補題により、$G$ の $\varepsilon/4$-正則分割 $\{V_1,\dots,V_m\}$（$m\le M$）をとる。
段 2（辺を除く）。 $x\in V_i$、$y\in V_j$ を結ぶ辺 $xy$ のうち、次のどれかに当たるものの集合を $F$ とする。

• (a) $(V_i,V_j)$ が $\varepsilon/4$-正則でない。
• (b) $d(V_i,V_j)<\varepsilon/2$ である。
• (c) $\lvert V_i\rvert<\varepsilon n/(4m)$ または $\lvert V_j\rvert<\varepsilon n/(4m)$ である。
  $x\in V_i$、$y\in V_j$ を結ぶ辺は $e(V_i,V_j)$ で少なくとも 1 回数えられる。(a) の辺は $\sum_{(i,j)\text{ が正則でない}}e(V_i,V_j)\le\sum_{(i,j)\text{ が正則でない}}\lvert V_i\rvert\lvert V_j\rvert\le\frac\varepsilon4n^2$ 本以下である。(b) の辺は $\sum_{d(V_i,V_j)<\varepsilon/2}d(V_i,V_j)\lvert V_i\rvert\lvert V_j\rvert\le\frac\varepsilon2\sum_{i,j}\lvert V_i\rvert\lvert V_j\rvert=\frac\varepsilon2n^2$ 本以下である。(c) の辺は大きさが $\varepsilon n/(4m)$ 未満の部分の頂点を端点にもち、そのような頂点は $m\cdot\varepsilon n/(4m)=\varepsilon n/4$ 個未満（そのような部分がなければ $0$ 個）で、各頂点の次数は $n-1$ 以下なので、(c) の辺は、そのような部分があれば $\varepsilon n^2/4$ 本未満、なければ $0$ 本である。合わせて $\lvert F\rvert<\varepsilon n^2$ である。

段 3（残ったグラフに三角形はない）。 $G-F$ に三角形 $\{x,y,z\}$ があり、$x\in V_i$、$y\in V_j$、$z\in V_k$（$i,j,k$ は相異なるとは限らない）とする。辺 $xy,yz,zx$ は $F$ に入らないので、3 つの対 $(V_i,V_j)$、$(V_j,V_k)$、$(V_k,V_i)$ は $G$ で $\varepsilon/4$-正則で、$G$ での辺の密度はどれも $\varepsilon/2=2\cdot\frac\varepsilon4$ 以上であり、3 つの部分の大きさは $\varepsilon n/(4m)\ge\varepsilon n/(4M)$ 以上である。$G$ で数え上げ補題を $\varepsilon'=\varepsilon/4$ として当てると、各密度について $d-\varepsilon/4\ge\varepsilon/4$ なので、3 辺が $G$ の辺である $(x',y',z')\in V_i\times V_j\times V_k$ は
$$ \Bigl(1-\frac\varepsilon2\Bigr)\Bigl(\frac\varepsilon4\Bigr)^3\lvert V_i\rvert\lvert V_j\rvert\lvert V_k\rvert\ge\Bigl(1-\frac\varepsilon2\Bigr)\Bigl(\frac\varepsilon4\Bigr)^3\Bigl(\frac{\varepsilon n}{4M}\Bigr)^3=6\delta n^3 $$
個以上ある。このような組の 3 点は $G$ の三角形をなし、1 つの三角形は組として高々 $3!=6$ 回現れるので、$t(G)\ge\delta n^3$ となって仮定に反する。よって $G-F$ は三角形を含まない。$\square$

thm-trr-main の $\delta$ をとり、$n_0>1/(6\delta)$ とする。各三角形は 3 本の辺をもち、各辺はちょうど 1 つの三角形に含まれるので、$t(G)=\lvert E\rvert/3\le n^2/6<\delta n^3$ である（$n\ge n_0$）。よって $\lvert F\rvert<\varepsilon n^2$ で $G-F$ が三角形を含まない $F$ がある。$F$ の辺はそれぞれ 1 つの三角形にしか含まれないので、$F$ の辺を含む三角形は $\lvert F\rvert$ 個以下である。すべての三角形が $F$ の辺を含むので $t(G)\le\lvert F\rvert$、すなわち $\lvert E\rvert/3<\varepsilon n^2$ である。$\square$

$\mathcal H$ を (6,3) の配置をもたない $n$ 頂点の 3-一様ハイパーグラフとする。
段 1（2 点を共有する辺は孤立した組をなす）。 相異なる辺 $e,f$ が 2 点を共有するとし、$U:=e\cup f$（4 点）とおく。ほかの辺 $g$ が $U$ と交われば $\lvert e\cup f\cup g\rvert\le4+2=6$ となるので、$e,f$ 以外の辺は $U$ と交わらない。とくに $e$ と 2 点を共有する辺は $f$ だけである。よって、ほかの辺と 2 点を共有する辺の集合 $\mathcal E_2$ は、互いに交わらない 4 点集合をもつ組に分かれ、$\lvert\mathcal E_2\rvert\le2\cdot\frac n4=\frac n2$ である。$\mathcal E':=\mathcal E\setminus\mathcal E_2$ とおくと、$\mathcal E'$ の相異なる 2 辺は高々 1 点しか共有せず、$(V,\mathcal E')$ も (6,3) の配置をもたない。
段 2（グラフを作る）。 $V$ を頂点とし、$\mathcal E'$ のある辺に含まれる 2 点を結んだグラフを $G$ とする。2 点を含む $\mathcal E'$ の辺は高々 1 本なので、$\mathcal E'$ の各辺 $\{a,b,c\}$ は $G$ の 3 本の辺 $ab,bc,ca$ を与え、これらは辺ごとに異なり、$\lvert E(G)\rvert=3\lvert\mathcal E'\rvert$ である。
段 3（$G$ の三角形は $\mathcal E'$ の辺だけ）。 $\{x,y,z\}$ を $G$ の三角形とし、$xy,yz,zx$ を含む $\mathcal E'$ の辺を $e_1,e_2,e_3$ とする。2 つが等しければ、たとえば $e_1=e_2$ なら $e_1\supset\{x,y,z\}$ で $e_1=\{x,y,z\}$ である。3 つが相異なれば、$e_1\cup e_2\cup e_3$ は $\{x,y,z\}$ と各 $e_i$ の残りの 1 点からなり、元は $6$ 個以下なので、(6,3) の配置をもたないことに反する。よって $G$ の三角形はちょうど $\mathcal E'$ の辺であり、$G$ の各辺は、それを含む $\mathcal E'$ のただ 1 つの辺がなす三角形にだけ含まれる。
段 4（合わせる）。 cor-trr-unique を $\varepsilon/6$ で使い、$n_1\ge\max\{n_0(\varepsilon/6),\,1/\varepsilon\}$ とすると、$n\ge n_1$ で $3\lvert\mathcal E'\rvert=\lvert E(G)\rvert<\frac\varepsilon2n^2$ である。よって $\lvert\mathcal E\rvert\le\lvert\mathcal E'\rvert+\frac n2<\frac\varepsilon6n^2+\frac\varepsilon2n^2<\varepsilon n^2$ である（$n\ge1/\varepsilon$ から $\frac n2\le\frac\varepsilon2n^2$）。$\square$

$A\subset[N]$ が 3 項の等差数列を含まないとする。$M:=2N+1$ とし、$A$ を $\mathbb Z/M\mathbb Z$ の部分集合とみる（$N< M$ なので $[N]\to\mathbb Z/M\mathbb Z$ は単射）。$M$ は奇数なので $2$ は $\mathbb Z/M\mathbb Z$ で可逆である。
段 1（$\mathbb Z/M\mathbb Z$ でも等差数列はない）。 $a,b,c\in A$ が $a+c\equiv2b\pmod M$ を満たすとする。$a,b,c\in[N]$ から $\lvert a+c-2b\rvert\le2N-2< M$ なので $a+c=2b$ であり、仮定から $a=b=c$ である。
段 2（グラフ）。 頂点を $(\mathbb Z/M\mathbb Z)\times\{1,2,3\}$ の $3M$ 個とし、$(x,1)$ と $(y,2)$ を $y-x\in A$ のとき、$(y,2)$ と $(z,3)$ を $z-y\in A$ のとき、$(x,1)$ と $(z,3)$ を $(z-x)/2\in A$ のとき結んだグラフを $G$ とする。同じ番号の頂点どうしは結ばない。各 $x$ と $a\in A$ について $(x,1)$ と $(x+a,2)$ が結ばれ、ほかの 2 種類も同じなので、$\lvert E(G)\rvert=3M\lvert A\rvert$ である。
段 3（各辺はちょうど 1 つの三角形に含まれる）。 三角形は番号 $1,2,3$ の頂点を 1 つずつもつ。$(x,1),(y,2),(z,3)$ が三角形をなすことは、$a:=y-x$、$c:=z-y$、$b:=(z-x)/2$ がどれも $A$ に属することと同じで、このとき $a+c=z-x=2b$ である。段 1 から $a=b=c$ となる。よって辺 $(x,1)(y,2)$（$y-x=a$）を含む三角形は $(z,3)=(y+a,3)$ のものだけで、実際 $(z-x)/2=a\in A$ なのでこれは三角形である。同じく、辺 $(y,2)(z,3)$ は $(2y-z,1)$ を加えた三角形に、辺 $(x,1)(z,3)$ は $(x+(z-x)/2,2)$ を加えた三角形にだけ含まれる。
段 4（合わせる）。 $\varepsilon>0$ に対し、cor-trr-unique を $\varepsilon/81$ で使う。$3M\ge n_0(\varepsilon/81)$ となる $N$ について、$3M\lvert A\rvert<3\cdot\frac\varepsilon{81}(3M)^2$、すなわち $\lvert A\rvert<\frac\varepsilon9M=\frac\varepsilon9(2N+1)\le\frac\varepsilon3N$ である。$\square$

Behrend の構成の集合 $A\subset[N]$ に prf-trr-roth の段 2 のグラフ $G$ を作る。段 1・段 3 は $A$ が 3 項の等差数列を含まないことだけを使っているので、$G$ の各辺はちょうど 1 つの三角形に含まれる。頂点は $3M=n$ 個、辺は $3M\lvert A\rvert=n\lvert A\rvert\ge nN\exp(-5\sqrt{\log N})$ 本である。$N\ge3$ から $n\le7N$ なので $N\ge n/7$ であり、$N< n$ から $\exp(-5\sqrt{\log N})\ge\exp(-5\sqrt{\log n})$ である。$\square$

要点：prop-trr-rs-graph のグラフは三角形が $M\lvert A\rvert$ 個しかないが、三角形をなくすには $M\lvert A\rvert$ 本の辺を除く必要がある。