K₄ Ramsey–Turán III — Proof, Steps 1–3

Loading…

K₄ Ramsey–Turán III — Proof, Steps 1–3

Part 4 of 5. ← K₄ Ramsey–Turán II — Tools · K₄ Ramsey–Turán V — Improvements →

主定理的证明

Observation.

设

F 是一个 K_4-free 图，S\subseteq V(F)，且 uv\in E(F)。则

\degF(u,S)+\degF(v,S)\le |S|+\alpha(F).

Note.

(这里原文没有证明，我自己补充一下)

我们记

NF(u,S)=NF(u)\cap S, NF(v,S)=NF(v)\cap S.

由于 uv\in E(F) 且 F 不含 K_4，所以任意两个同时属于

NF(u,S)\cap NF(v,S)

的顶点都不能相邻；否则若 x,y\in NF(u,S)\cap NF(v,S) 且 xy\in E(F)，那么 {u,v,x,y} 就构成一个 K_4，矛盾。因此

NF(u,S)\cap NF(v,S)

是 F 的一个独立集，从而

|NF(u,S)\cap NF(v,S)|\le \alpha(F).

另一方面，

\degF(u,S)+\degF(v,S)=|NF(u,S)|+|NF(v,S)|

=|N_F(u,S)\cup N_F(v,S)|+|N_F(u,S)\cap N_F(v,S)| \le |S|+\alpha(F).

故结论成立。

Fact.

有

\alpha=\alpha(G)/n<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

Note.

(这里原文没有证明，我自己补充一下)

由 (thm1.3) 的条件，

\alpha\le \gamma=\exp\!\left(-\frac{10\log(1/\nu)}{\nu}\right).

因此只需证明

\gamma<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

对第一个不等式，两边取对数后，我们只需验证

-\frac{10\log(1/\nu)}{\nu}<-\frac{\log(2/\nu)}{\nu}+2\log \nu.

等价地，

10\log(1/\nu)>\log(2/\nu)+2\nu\log(1/\nu).

而

\log(2/\nu)=\log 2+\log(1/\nu),

所以只需证明

(9-2\nu)\log(1/\nu)>\log 2,

这对 $\nu=1/500$ 显然成立。于是

\gamma<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2.

对第二个不等式，我们只需证明

\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)<\nu.

两边取对数后，等价于

\frac{\log(2/\nu)}{\nu}>\log(1/\nu).

而

\log(2/\nu)=\log 2+\log(1/\nu)>\nu\log(1/\nu),

故上式成立，从而

\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

Remark 12.

接下来我们来证明论文的主定理 (thm1.3)，分成5个 Step。

Step 1

任取一个大小为 $\nu n$ 的点集 $B_0\subset V$ ，令 $A_0=V\setminus B_0$ 。由于前面已经把原本要证明的问题约化到 $\delta(G)\ge n/4$ 的情形，所以对每个 $v\in B_0$ ，都有

\deg(v,A_0)\ge \frac n4-|B_0|=\left(\frac14-\nu\right)n.

我们将 (lem:large-regular-pair) 应用于二部图 $G[B_0,A_0]$ ，其中取

\varepsilon=\nu, \delta=\frac{(1/4-\nu)n}{|A_0|}=\frac{1/4-\nu}{1-\nu},

得到一个 $\nu^+$ -regular 对 $G[B_1,A_1]$ ，其中 $B_1\subseteq B_0$ 、 $A_1\subseteq A_0$ ，并且

|A_1|\ge (\delta-2\nu)|A_0|=\left(\frac14-3\nu+2\nu^2\right)n,

且对每个 $v\in B_1$ ，都有

\deg(v,A_1)\ge (\delta-2\nu)|A_0|=\left(\frac14-3\nu+2\nu^2\right)n.

Claim.

由于 $G$ 不含 $K_4$ ，有

|A_1|\ge \frac n2-6\nu n-\alpha(G).

Proof.

首先 $|B_1|>\alpha(G)$ ，于是 $B_1$ 不是独立集，所以存在一条边 $uv\in E(G[B_1])$ 。

Note.

（论文对 $|B_1|>\alpha(G)$ 没有证明，我补充了一下证明）由 (lem:large-regular-pair)，

|B_1|\ge \exp\!\left(-\frac{2\log(2/\nu)\log(2/\delta)}{\nu}\right)|B_0|,

其中

\delta=\frac{1/4-\nu}{1-\nu}>\frac15.

因此

|B_1|>\exp\!\left(-\frac{5\log(2/\nu)}{\nu}\right)\nu n.

另一方面，由 (fact:alpha-small)，

\alpha(G)=\alpha n<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2n.

由于 $\nu=1/500$ ，有

\exp\!\left(-\frac{5\log(2/\nu)}{\nu}\right)\nu > \exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2,

故

|B_1|>\alpha(G).

由 (obs:edge-neighborhood-sum)（取 $F=G$ 、 $S=A_1$ ）可得

\deg(u,A_1)+\deg(v,A_1)\le |A_1|+\alpha(G).

另外，由于对每个 $v\in B_1$ 都有

\deg(v,A_1)\ge \left(\frac14-3\nu+2\nu^2\right)n.

因此

|A_1|+\alpha(G)\ge 2\left(\frac14-3\nu+2\nu^2\right)n =\left(\frac12-6\nu+4\nu^2\right)n.

于是

|A_1| \ge \left(\frac12-6\nu+4\nu^2\right)n-\alpha(G) \ge \frac n2-6\nu n-\alpha(G).

故结论成立。

∎

Step 2

我们定义

A_2=A_1-\{v\in A_1:\deg(v,B_1)<\nu|B_1|\}=\{v\in A_1:\deg(v,B_1)\ge \nu|B_1|\}.

也就是说，我们从 $A_1$ 中删去所有在 $B_1$ 中邻点少于 $\nu|B_1|$ 的顶点。由于在 Step 1 中得到的 $G[B_1,A_1]$ 是一个 $\nu^+$ -regular pair，我们记

X=\{v\in A_1:\deg(v,B_1)<\nu|B_1|\}

若满足 $|X|\ge \nu|A_1|$ ，那么就会有

d_G(X,B_1)<\nu,

这与 $\nu^+$ -regular 性矛盾。因此

|X|<\nu|A_1|, |A_2|=|A_1|-|X|\ge (1-\nu)|A_1|.

结合 Step 1 中对 $|A_1|$ 的下界，可得

\left|A_2\right|\ge (1-\nu)|A_1|\ge |A_1|-\nu n\ge \frac n2-7\nu n-\alpha(G).

此外，对每个 $v\in B_1$ ，由于至多删去了 $\nu n$ 个 $A_1$ 中的顶点，而在 Step 1 中已经有

\deg(v,A_1)\ge \frac n4-3\nu n,

故

\deg(v,A_2)\ge \deg(v,A_1)-\nu n\ge \frac n4-4\nu n.

Claim.

对每个 $v\in A_2$ ，其在 $A_2$ 内的度满足

\deg(v,A_2)\le \nu |A_1|.

Proof.

假设存在某个 $v\in A_2$ 满足

\deg(v,A_2)>\nu|A_1|.

由于 $v\in A_2$ ，按定义有

|N(v)\cap B_1|=\deg(v,B_1)\ge \nu|B_1|.

又因为 $G[B_1,A_1]$ 是一个 $\nu^+$ -regular pair，而

|N(v)\cap A_2|=\deg(v,A_2)>\nu|A_1|, |N(v)\cap B_1|=\deg(v,B_1)\ge \nu|B_1|,

所以在二部图

G[N(v)\cap A_2,\ N(v)\cap B_1]

中，边密度至少为 $\nu$ 。因此存在某个顶点 $w\in N(v)\cap B_1$ ，使得它在 $N(v)\cap A_2$ 中至少有

\nu|N(v)\cap A_2|=\nu\deg(v,A_2)\ge \nu^2|A_1|

个邻点。

另一方面，由前面的 $|A_1|\ge n/2-6\nu n-\alpha(G)$ 以及 (fact:alpha-small) 可得

|A_1|>\frac n3,

从而

\nu^2|A_1|>\frac{\nu^2 n}{3}>\alpha(G).

于是 $w$ 在 $N(v)\cap A_2$ 中有多于 $\alpha(G)$ 个邻点，所以其中必有两个顶点彼此相邻。设这两个顶点为 $x,y$ 。那么

v,w,x,y

两两相邻，从而构成一个 $K_4$ ，矛盾！故

\deg(v,A_2)\le \nu|A_1|

对每个 $v\in A_2$ 都成立。

∎

Step 3

对于二部图 $G[A_2,V\setminus A_2]$ ，由 (clm:step2-a2-internal)，每个 $v\in A_2$ 在 $V\setminus A_2$ 中至少有

\frac n4-\nu n

个邻点，由 (lem:large-regular-pair) ，我们得到一个 $\nu^+$ -regular pair

(A_2',B_2),

其中

A_2'\subseteq A_2, B_2\subseteq V\setminus A_2,

并且

|A_2'|\ge \exp\!\left(-\frac{2\log(2/\nu)}{\nu}\right)\frac{\nu n}{3}, |B_2|\ge \frac n2-6\nu n-\alpha(G).

Note.

由 (lem:large-regular-pair)，对每个 $v\in A_2'$ 都有

\deg(v,B_2)\ge \frac n4-3\nu n.

由于

|A_2'|\ge \exp\!\left(-\frac{2\log(2/\nu)}{\nu}\right)\frac{\nu n}{3},

再结合 (fact:alpha-small) 可知 $|A_2'|>\alpha(G)$ 。因此 $A_2'$ 不是独立集，于是存在一条边

uv\in E(G[A_2']).

现在对这条边应用 (obs:edge-neighborhood-sum)，取 $F=G$ 、 $S=B_2$ ，便有

\deg(u,B_2)+\deg(v,B_2)\le |B_2|+\alpha(G).

另一方面，由上面的度下界，

\deg(u,B_2)\ge \frac n4-3\nu n, \deg(v,B_2)\ge \frac n4-3\nu n.

因此

|B_2|+\alpha(G)\ge \frac n2-6\nu n,

从而

|B_2|\ge \frac n2-6\nu n-\alpha(G).

和前面对 $A_1$ 的处理一样，我们删去 $B_2$ 中那些在 $A_2'$ 中邻点少于 $\nu|A_2'|$ 的顶点。定义

B_3=B_2-\{v\in B_2:\deg(v,A_2')<\nu|A_2'|\} =\{v\in B_2:\deg(v,A_2')\ge \nu|A_2'|\}.

由 $\nu^+$ -regular 性可得

|B_3|\ge (1-\nu)|B_2|\ge |B_2|-\nu n\ge \frac n2-7\nu n-\alpha(G).

这里的下界还可以进一步改进。对每个 $v\in A_2'$ ，由 (clm:step2-a2-internal) 和 (lem:large-regular-pair) 可得

\deg(v,B_2)\ge \frac n4-\nu|A_1|-2\nu|V\setminus A_2|.

又因为 $|A_2|\ge(1-\nu)|A_1|$ ，所以

\begin{aligned} \nu|A_1|+2\nu|V\setminus A_2| &=\nu|A_1|+2\nu(n-|A_2|)\\ &\le 2\nu n-(1-2\nu)\nu|A_1|\\ &<2\nu n. \end{aligned}

因此

\deg(v,B_2)>\frac n4-2\nu n.

由于 $|A_2'|>\alpha(G)$ ，可以在 $A_2'$ 中取一条边 $uv$ 。对这条边应用 (obs:edge-neighborhood-sum)，得到

|B_2|+\alpha(G)\ge \deg(u,B_2)+\deg(v,B_2) >\frac n2-4\nu n.

从而

|B_2|>\frac n2-4\nu n-\alpha(G).

再由 $B_3$ 的定义和 $\nu^+$ -regular 性，

|B_3|\ge(1-\nu)|B_2|\ge |B_2|-\nu n >\frac n2-5\nu n-\alpha(G).

Claim.

对每个 $v\in B_3$ ，其在 $B_3$ 内的度满足

\deg(v,B_3)\le \nu |B_2|.

Note.

假设存在某个 $v\in B_3$ 满足

\deg(v,B_3)>\nu|B_2|.

由于 $v\in B_3$ ，按定义有

\deg(v,A_2')\ge \nu|A_2'|.

又因为 $G[A_2',B_2]$ 是一个 $\nu^+$ -regular pair，而

|N(v)\cap A_2'|=\deg(v,A_2')\ge \nu|A_2'|, |N(v)\cap B_3|=\deg(v,B_3)>\nu|B_2|,

所以二部图

G[N(v)\cap A_2',\,N(v)\cap B_3]

的边密度至少为 $\nu$ 。因此存在某个顶点 $w\in N(v)\cap A_2'$ ，使得它在 $N(v)\cap B_3$ 中至少有

\nu|N(v)\cap B_3|=\nu\deg(v,B_3)\ge \nu^2|B_2|

个邻点。

另一方面，由 Step 3 中的下界

|B_2|\ge \frac n2-6\nu n-\alpha(G)>\frac n3

以及 (fact:alpha-small) 可得

\nu^2|B_2|>\frac{\nu^2n}{3}>\alpha(G).

于是 $w$ 在 $N(v)\cap B_3$ 中有多于 $\alpha(G)$ 个邻点，所以其中必有两个顶点彼此相邻。设这两个顶点为 $x,y$ 。那么

v,w,x,y

两两相邻，从而构成一个 $K_4$ ，矛盾！因此对每个 $v\in B_3$ ，都只能有

\deg(v,B_3)\le \nu|B_2|.

Part 3 of 5. ← Tools · Steps 4–5 →

Part 4 of 5. ← K₄ Ramsey–Turán II — Tools · K₄ Ramsey–Turán V — Improvements →

主定理的证明

Observation.

设

F 是一个 K_4-free 图，S\subseteq V(F)，且 uv\in E(F)。则

\degF(u,S)+\degF(v,S)\le |S|+\alpha(F).

Note.

(这里原文没有证明，我自己补充一下)

我们记

NF(u,S)=NF(u)\cap S, NF(v,S)=NF(v)\cap S.

由于 uv\in E(F) 且 F 不含 K_4，所以任意两个同时属于

NF(u,S)\cap NF(v,S)

的顶点都不能相邻；否则若 x,y\in NF(u,S)\cap NF(v,S) 且 xy\in E(F)，那么 {u,v,x,y} 就构成一个 K_4，矛盾。因此

NF(u,S)\cap NF(v,S)

是 F 的一个独立集，从而

|NF(u,S)\cap NF(v,S)|\le \alpha(F).

另一方面，

\degF(u,S)+\degF(v,S)=|NF(u,S)|+|NF(v,S)|

=|N_F(u,S)\cup N_F(v,S)|+|N_F(u,S)\cap N_F(v,S)| \le |S|+\alpha(F).

故结论成立。

Fact.

有

\alpha=\alpha(G)/n<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

Note.

(这里原文没有证明，我自己补充一下)

由 (thm1.3) 的条件，

\alpha\le \gamma=\exp\!\left(-\frac{10\log(1/\nu)}{\nu}\right).

因此只需证明

\gamma<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

对第一个不等式，两边取对数后，我们只需验证

-\frac{10\log(1/\nu)}{\nu}<-\frac{\log(2/\nu)}{\nu}+2\log \nu.

等价地，

10\log(1/\nu)>\log(2/\nu)+2\nu\log(1/\nu).

而

\log(2/\nu)=\log 2+\log(1/\nu),

所以只需证明

(9-2\nu)\log(1/\nu)>\log 2,

这对 $\nu=1/500$ 显然成立。于是

\gamma<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2.

对第二个不等式，我们只需证明

\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)<\nu.

两边取对数后，等价于

\frac{\log(2/\nu)}{\nu}>\log(1/\nu).

而

\log(2/\nu)=\log 2+\log(1/\nu)>\nu\log(1/\nu),

故上式成立，从而

\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2<\nu^3.

Remark 12.

接下来我们来证明论文的主定理 (thm1.3)，分成5个 Step。

Step 1

\deg(v,A_0)\ge \frac n4-|B_0|=\left(\frac14-\nu\right)n.

我们将 (lem:large-regular-pair) 应用于二部图 $G[B_0,A_0]$ ，其中取

\varepsilon=\nu, \delta=\frac{(1/4-\nu)n}{|A_0|}=\frac{1/4-\nu}{1-\nu},

得到一个 $\nu^+$ -regular 对 $G[B_1,A_1]$ ，其中 $B_1\subseteq B_0$ 、 $A_1\subseteq A_0$ ，并且

|A_1|\ge (\delta-2\nu)|A_0|=\left(\frac14-3\nu+2\nu^2\right)n,

且对每个 $v\in B_1$ ，都有

\deg(v,A_1)\ge (\delta-2\nu)|A_0|=\left(\frac14-3\nu+2\nu^2\right)n.

Claim.

由于 $G$ 不含 $K_4$ ，有

|A_1|\ge \frac n2-6\nu n-\alpha(G).

Proof.

首先 $|B_1|>\alpha(G)$ ，于是 $B_1$ 不是独立集，所以存在一条边 $uv\in E(G[B_1])$ 。

Note.

（论文对 $|B_1|>\alpha(G)$ 没有证明，我补充了一下证明）由 (lem:large-regular-pair)，

|B_1|\ge \exp\!\left(-\frac{2\log(2/\nu)\log(2/\delta)}{\nu}\right)|B_0|,

其中

\delta=\frac{1/4-\nu}{1-\nu}>\frac15.

因此

|B_1|>\exp\!\left(-\frac{5\log(2/\nu)}{\nu}\right)\nu n.

另一方面，由 (fact:alpha-small)，

\alpha(G)=\alpha n<\exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2n.

由于 $\nu=1/500$ ，有

\exp\!\left(-\frac{5\log(2/\nu)}{\nu}\right)\nu > \exp\!\left(-\frac{\log(2/\nu)}{\nu}\right)\nu^2,

故

|B_1|>\alpha(G).

由 (obs:edge-neighborhood-sum)（取 $F=G$ 、 $S=A_1$ ）可得

\deg(u,A_1)+\deg(v,A_1)\le |A_1|+\alpha(G).

另外，由于对每个 $v\in B_1$ 都有

\deg(v,A_1)\ge \left(\frac14-3\nu+2\nu^2\right)n.

因此

|A_1|+\alpha(G)\ge 2\left(\frac14-3\nu+2\nu^2\right)n =\left(\frac12-6\nu+4\nu^2\right)n.

于是

|A_1| \ge \left(\frac12-6\nu+4\nu^2\right)n-\alpha(G) \ge \frac n2-6\nu n-\alpha(G).

故结论成立。

∎

Step 2

我们定义

A_2=A_1-\{v\in A_1:\deg(v,B_1)<\nu|B_1|\}=\{v\in A_1:\deg(v,B_1)\ge \nu|B_1|\}.

也就是说，我们从 $A_1$ 中删去所有在 $B_1$ 中邻点少于 $\nu|B_1|$ 的顶点。由于在 Step 1 中得到的 $G[B_1,A_1]$ 是一个 $\nu^+$ -regular pair，我们记

X=\{v\in A_1:\deg(v,B_1)<\nu|B_1|\}

若满足 $|X|\ge \nu|A_1|$ ，那么就会有

d_G(X,B_1)<\nu,

这与 $\nu^+$ -regular 性矛盾。因此

|X|<\nu|A_1|, |A_2|=|A_1|-|X|\ge (1-\nu)|A_1|.

结合 Step 1 中对 $|A_1|$ 的下界，可得

\left|A_2\right|\ge (1-\nu)|A_1|\ge |A_1|-\nu n\ge \frac n2-7\nu n-\alpha(G).

此外，对每个 $v\in B_1$ ，由于至多删去了 $\nu n$ 个 $A_1$ 中的顶点，而在 Step 1 中已经有

\deg(v,A_1)\ge \frac n4-3\nu n,

故

\deg(v,A_2)\ge \deg(v,A_1)-\nu n\ge \frac n4-4\nu n.

Claim.

对每个 $v\in A_2$ ，其在 $A_2$ 内的度满足

\deg(v,A_2)\le \nu |A_1|.

Proof.

假设存在某个 $v\in A_2$ 满足

\deg(v,A_2)>\nu|A_1|.

由于 $v\in A_2$ ，按定义有

|N(v)\cap B_1|=\deg(v,B_1)\ge \nu|B_1|.

又因为 $G[B_1,A_1]$ 是一个 $\nu^+$ -regular pair，而

|N(v)\cap A_2|=\deg(v,A_2)>\nu|A_1|, |N(v)\cap B_1|=\deg(v,B_1)\ge \nu|B_1|,

所以在二部图

G[N(v)\cap A_2,\ N(v)\cap B_1]

中，边密度至少为 $\nu$ 。因此存在某个顶点 $w\in N(v)\cap B_1$ ，使得它在 $N(v)\cap A_2$ 中至少有

\nu|N(v)\cap A_2|=\nu\deg(v,A_2)\ge \nu^2|A_1|

个邻点。

另一方面，由前面的 $|A_1|\ge n/2-6\nu n-\alpha(G)$ 以及 (fact:alpha-small) 可得

|A_1|>\frac n3,

从而

\nu^2|A_1|>\frac{\nu^2 n}{3}>\alpha(G).

于是 $w$ 在 $N(v)\cap A_2$ 中有多于 $\alpha(G)$ 个邻点，所以其中必有两个顶点彼此相邻。设这两个顶点为 $x,y$ 。那么

v,w,x,y

两两相邻，从而构成一个 $K_4$ ，矛盾！故

\deg(v,A_2)\le \nu|A_1|

对每个 $v\in A_2$ 都成立。

∎

Step 3

对于二部图 $G[A_2,V\setminus A_2]$ ，由 (clm:step2-a2-internal)，每个 $v\in A_2$ 在 $V\setminus A_2$ 中至少有

\frac n4-\nu n

个邻点，由 (lem:large-regular-pair) ，我们得到一个 $\nu^+$ -regular pair

(A_2',B_2),

其中

A_2'\subseteq A_2, B_2\subseteq V\setminus A_2,

并且

|A_2'|\ge \exp\!\left(-\frac{2\log(2/\nu)}{\nu}\right)\frac{\nu n}{3}, |B_2|\ge \frac n2-6\nu n-\alpha(G).

Note.

由 (lem:large-regular-pair)，对每个 $v\in A_2'$ 都有

\deg(v,B_2)\ge \frac n4-3\nu n.

由于

|A_2'|\ge \exp\!\left(-\frac{2\log(2/\nu)}{\nu}\right)\frac{\nu n}{3},

再结合 (fact:alpha-small) 可知 $|A_2'|>\alpha(G)$ 。因此 $A_2'$ 不是独立集，于是存在一条边

uv\in E(G[A_2']).

现在对这条边应用 (obs:edge-neighborhood-sum)，取 $F=G$ 、 $S=B_2$ ，便有

\deg(u,B_2)+\deg(v,B_2)\le |B_2|+\alpha(G).

另一方面，由上面的度下界，

\deg(u,B_2)\ge \frac n4-3\nu n, \deg(v,B_2)\ge \frac n4-3\nu n.

因此

|B_2|+\alpha(G)\ge \frac n2-6\nu n,

从而

|B_2|\ge \frac n2-6\nu n-\alpha(G).

和前面对 $A_1$ 的处理一样，我们删去 $B_2$ 中那些在 $A_2'$ 中邻点少于 $\nu|A_2'|$ 的顶点。定义

B_3=B_2-\{v\in B_2:\deg(v,A_2')<\nu|A_2'|\} =\{v\in B_2:\deg(v,A_2')\ge \nu|A_2'|\}.

由 $\nu^+$ -regular 性可得

|B_3|\ge (1-\nu)|B_2|\ge |B_2|-\nu n\ge \frac n2-7\nu n-\alpha(G).

这里的下界还可以进一步改进。对每个 $v\in A_2'$ ，由 (clm:step2-a2-internal) 和 (lem:large-regular-pair) 可得

\deg(v,B_2)\ge \frac n4-\nu|A_1|-2\nu|V\setminus A_2|.

又因为 $|A_2|\ge(1-\nu)|A_1|$ ，所以

\begin{aligned} \nu|A_1|+2\nu|V\setminus A_2| &=\nu|A_1|+2\nu(n-|A_2|)\\ &\le 2\nu n-(1-2\nu)\nu|A_1|\\ &<2\nu n. \end{aligned}

因此

\deg(v,B_2)>\frac n4-2\nu n.

由于 $|A_2'|>\alpha(G)$ ，可以在 $A_2'$ 中取一条边 $uv$ 。对这条边应用 (obs:edge-neighborhood-sum)，得到

|B_2|+\alpha(G)\ge \deg(u,B_2)+\deg(v,B_2) >\frac n2-4\nu n.

从而

|B_2|>\frac n2-4\nu n-\alpha(G).

再由 $B_3$ 的定义和 $\nu^+$ -regular 性，

|B_3|\ge(1-\nu)|B_2|\ge |B_2|-\nu n >\frac n2-5\nu n-\alpha(G).

Claim.

对每个 $v\in B_3$ ，其在 $B_3$ 内的度满足

\deg(v,B_3)\le \nu |B_2|.

Note.

假设存在某个 $v\in B_3$ 满足

\deg(v,B_3)>\nu|B_2|.

由于 $v\in B_3$ ，按定义有

\deg(v,A_2')\ge \nu|A_2'|.

又因为 $G[A_2',B_2]$ 是一个 $\nu^+$ -regular pair，而

|N(v)\cap A_2'|=\deg(v,A_2')\ge \nu|A_2'|, |N(v)\cap B_3|=\deg(v,B_3)>\nu|B_2|,

所以二部图

G[N(v)\cap A_2',\,N(v)\cap B_3]

的边密度至少为 $\nu$ 。因此存在某个顶点 $w\in N(v)\cap A_2'$ ，使得它在 $N(v)\cap B_3$ 中至少有

\nu|N(v)\cap B_3|=\nu\deg(v,B_3)\ge \nu^2|B_2|

个邻点。

另一方面，由 Step 3 中的下界

|B_2|\ge \frac n2-6\nu n-\alpha(G)>\frac n3

以及 (fact:alpha-small) 可得

\nu^2|B_2|>\frac{\nu^2n}{3}>\alpha(G).

于是 $w$ 在 $N(v)\cap B_3$ 中有多于 $\alpha(G)$ 个邻点，所以其中必有两个顶点彼此相邻。设这两个顶点为 $x,y$ 。那么

v,w,x,y

两两相邻，从而构成一个 $K_4$ ，矛盾！因此对每个 $v\in B_3$ ，都只能有

\deg(v,B_3)\le \nu|B_2|.

K₄ Ramsey–Turán III — Proof, Steps 1–3

Search

K₄ Ramsey–Turán III — Proof, Steps 1–3

主定理的证明

Step 1

Step 2

Step 3

主定理的证明

Step 1

Step 2

Step 3