K₄ Ramsey–Turán V — Improvements

Loading…

K₄ Ramsey–Turán V — Improvements

Part 5 of 5. ← Proof

改进

回到我们最初的这个问题，就是为什么取的是

\nu=1/500？

Proposition 1.

沿用原文的整体证明框架，并保持

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

N=\exp!\left(\frac{10\log(1/\nu)}{\nu}\right),

只要 0<\nu<1/321，则正文中从 Step 1 到 Step 5 的论证仍然可以完成。也就是说，把原文中的 \nu=1/500 换成任意 \nu<1/321 仍然足够。

Proof.

我们只需关注具体用的这个 \nu 的范围的地方：

先看 Step 3。对每个 v\in A_2，由 (clm:step2-a2-internal) 可知

\deg(v,V\setminus A2)\ge \frac n4-\nu|A1|.

将 (lem:large-regular-pair) 应用于二部图 G[A2,V\setminus A2] 后，对每个 v\in A_2'，有

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

注意到

|V\setminus A_2|=n-|A_2|,

|A_2|>(1-\nu)|A_1|,

所以

\begin{aligned} \nu|A1|+2\nu|V\setminus A2| &=\nu|A1|+2\nu(n-|A2|)\ &=2\nu n+\nu(|A1|-2|A2|)\ &<2\nu n, \end{aligned}

因为

|A_1|-2|A_2|<|A_1|-2(1-\nu)|A_1|=(2\nu-1)|A_1|<0.

于是对每个 v\in A_2'，都有

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

再像原文那样在 A_2' 中取一条边 uv，由

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

得到

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

接着由 B_3 的定义和 \nu^+-regular 性，

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

另一方面，Step 2 里已经有

|A_2|\ge \frac n2-7\nu n-\alpha(G).

因此

|V\setminus(A2\cup B3)|

=n-|A2|-|B3| <12\nu n+2\alpha(G).

由于 \alpha(G)<\nu^3 n，上式进一步给出

|V\setminus(A2\cup B3)|<(12\nu+2\nu^3)n.

现在回到 (obs:step4-split-degree)。对任意 x\in V\setminus(A_2\cup B_3)，由最小度条件 \delta(G)\ge n/4 得

\deg(x,A2)+\deg(x,B3)

\frac n4-(12\nu+2\nu^3)n.

若 x\in A'，则 \deg(x,B_3)\ge \deg(x,A_2)，从而

\deg(x,B_3)> \left(\frac18-6\nu-\nu^3\right)n.

同理，若 x\in B'，则

\deg(x,A_2)> \left(\frac18-6\nu-\nu^3\right)n.

接下来我们来看 (clm:step4-a-minus-aprime)。设 u1u2 是 A\setminus A'=A2 中的一条边。由 \deg(ui,A2)\le \nu|A1|<\nu n 以及

|A'|\le |V\setminus(A2\cup B3)|<12\nu n+2\alpha(G),

可得

\deg(u_i,A)<13\nu n+2\alpha(G).

于是

\deg(u_i,B)>\frac n4-13\nu n-2\alpha(G).

再利用

|N(u1)\cap N(u2)|\le \alpha(G),

可得

|(N(u1)\cup N(u2))\cap B|

\frac n2-26\nu n-5\alpha(G).

同时由

|B|\le \frac n2+7\nu n+\alpha(G)

得到

|B\setminus (N(u1)\cup N(u2))|

<33\nu n+6\alpha(G).

现在对任意 v\in A，都有

|N(v)\cap B|>

\left(\frac18-6\nu-\nu^3\right)n.

若同时有

|N(v)\cap N(u_1)\cap B|

\le \frac12\left(\left(\frac18-6\nu-\nu^3\right)n-(33\nu n+6\alpha(G))\right)

和

|N(v)\cap N(u_2)\cap B|

\le \frac12\left(\left(\frac18-6\nu-\nu^3\right)n-(33\nu n+6\alpha(G))\right),

那么就会推出

|N(v)\cap B|

< \left(\frac18-6\nu-\nu^3\right)n,

矛盾。因此至少有一个交集满足

|N(v)\cap N(u_i)\cap B|

\frac12\left(\left(\frac18-39\nu-\nu^3\right)n-6\alpha(G)\right).

只要右端大于 \alpha(G)，(clm:step4-a-minus-aprime) 的原论证就仍然成立。由 \alpha(G)<\nu^3 n，只需验证

\frac18-39\nu-9\nu^3>0.

解出来大概是 \nu<1/321 ，也就是说，当 \nu<1/321 时 (clm:step4-a-minus-aprime) 仍然成立。

一旦 (clm:step4-a-minus-aprime) 保持成立，后面的 (cor:step4-internal-degree) 和 (clm:step4-a-degree-alpha) 也可以用同样的方法继续推进。事实上，此时

\deg(v,A)<13\nu n+3\alpha(G),

是满足的。最后 Step 5 里涉及 |A|,|B| 的估计本来就只有 O(\alpha(G)) 量级，对 \nu 的选取也没有影响。

所以实际上我们取 \nu<1/321 也是能按照原文的思路完成证明的。

∎

下面我们给出一个比 (lem:large-regular-pair) 更强的参数化版本。相比 (lem:large-regular-pair) ，我们引入了一个新参数进行推广，得到了一个更精细的下界。

Proposition 2.

设 F 是二部图，二部划分为 (A,B)，其中

|A|=a, |B|=b.

假设每个 x\in A 在 B 中至少有 \delta b 个邻点。取参数

1<t<\frac{\delta}{\varepsilon},

并假设 0<\varepsilon<1。那么存在 X\subseteq A、Y\subseteq B，使得 F[X,Y] 是 \varepsilon^+-regular pair，并且

|Y|\ge

\frac{\delta-t\varepsilon}{1-t\varepsilon}b,

同时

\deg(x,Y)\ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b \forall x\in X,

而且

|X|

\ge \exp\left( - \frac{ \log\frac{1}{\varepsilon(1-1/t)} \cdot \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} } \right)a.

Proof.

我们沿用 (lem:large-regular-pair) 的迭代思想，把 2\varepsilon 改成 t\varepsilon。

从

X0=A, Y0=B

开始。若 F[Xi,Yi] 已经是 \varepsilon^+-regular pair，则停止。

否则，存在

S\subseteq Xi, T\subseteq Yi

满足

|S|\ge \varepsilon |X_i|,

|T|\ge \varepsilon |Y_i|,

且

d(S,T)<\varepsilon.

由 (clm:density-convexity)，可以取

X'{i+1}\subseteq S, Y'{i+1}\subseteq T

满足

|X'_{i+1}|=\varepsilon |X_i|,

|Y'_{i+1}|=\varepsilon |Y_i|,

并且

e(X'{i+1},Y'{i+1}) < \varepsilon |X'{i+1}||Y'{i+1}|.

令

Z{i+1} = \left{ x\in X'{i+1}: \deg(x,Y'{i+1})>t\varepsilon |Y'{i+1}| \right}.

因为总边数小于

\varepsilon |X'{i+1}||Y'{i+1}|,

所以

|Z_{i+1}|<\frac1t |X'_{i+1}|.

令

X{i+1}=X'{i+1}\setminus Z_{i+1},

Y{i+1}=Yi\setminus Y'_{i+1}.

则

|X_{i+1}|

\ge \left(1-\frac1t\right)|X'{i+1}| = \varepsilon\left(1-\frac1t\right)|Xi|,

并且

|Y_{i+1}|=(1-\varepsilon)|Y_i|.

所以若迭代进行了 l 步，则

|X_l|

\ge \left(\varepsilon\left(1-\frac1t\right)\right)^l a,

|Y_l|=(1-\varepsilon)^l b.

接下来估计 $l$ 。在每一步中，保留下来的 $x\in X_{i+1}$ 对被删掉的 $Y'_{i+1}$ 的邻点数至多

t\varepsilon |Y'_{i+1}|.

因此对任意 $x\in X_l$ ，它在所有被删去的 $Y$ -块中的邻点总数至多

t\varepsilon\sum_{j=1}^{l}|Y'_j| = t\varepsilon(b-|Y_l|).

由于一开始

\deg(x,B)\ge \delta b,

所以

\deg(x,Y_l) \ge \delta b-t\varepsilon(b-|Y_l|) = (\delta-t\varepsilon)b+t\varepsilon |Y_l|.

但是

\deg(x,Y_l)\le |Y_l|.

因此

|Y_l| \ge (\delta-t\varepsilon)b+t\varepsilon |Y_l|.

故

|Y_l| \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b.

又因为

|Y_l|=(1-\varepsilon)^l b,

所以

(1-\varepsilon)^l \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}.

取对数后可得

l \le \frac{ \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} }.

代回对 $X_l$ 的估计：

|X_l| \ge \left(\varepsilon\left(1-\frac1t\right)\right)^l a.

由于

0<\varepsilon\left(1-\frac1t\right)<1,

于是

|X_l| \ge \exp\left( - \frac{ \log\frac{1}{\varepsilon(1-1/t)} \cdot \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} } \right)a.

如果过程停止，则得到的就是 $\varepsilon^+$ -regular pair。若过程一直不停止，那么 $Y_l$ 会持续按 $(1-\varepsilon)^l$ 缩小，最终也会与刚才推出的必要条件

|Y_l| \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b.

相矛盾！所以过程必定在某一步停止，命题得证。

∎

Proposition 3.

设 $G$ 是一个 $K_4$ -free 图，满足 $\delta(G)\ge n/4$ ，并且存在划分 $V(G)=A\cup B$ 满足 (clm:step4-a-degree-alpha) 与 (clm:step4-balance) 的结论。若 $r\ge 1$ 且

(28r+8)\alpha(G)<n,

则 $G[A]$ 与 $G[B]$ 都不含长度为 $2r+1$ 的圈。

Proof.

我们只证明 $G[A]$ 的情形。假设

v_1v_2\cdots v_{2r+1}v_1

是 $G[A]$ 中的一个圈，并记

H_i:=N(v_i)\cap B.

由 (clm:step4-a-degree-alpha) 与最小度条件可知

|H_i|\ge \frac n4-\alpha(G).

又由 (clm:step4-balance)，

|B|\le \frac n2+3\alpha(G).

对任意相邻的 $v_i,v_{i+1}$ ，集合 $H_i\cap H_{i+1}$ 必须是独立集，否则其中一条边会与 $v_iv_{i+1}$ 构成 $K_4$ 。因此

|H_i\cap H_{i+1}|\le \alpha(G).

从而

\begin{aligned} |B\setminus(H_i\cup H_{i+1})| &=|B|-|H_i|-|H_{i+1}|+|H_i\cap H_{i+1}|\\ &\le 6\alpha(G). \end{aligned}

于是

H_{i+2}\setminus H_i \subseteq \bigl(H_{i+2}\cap H_{i+1}\bigr) \cup \bigl(B\setminus(H_i\cup H_{i+1})\bigr),

故

|H_{i+2}\setminus H_i|\le 7\alpha(G).

将这个不等式沿奇数下标迭代 $r$ 次，得到

|H_{2r+1}\setminus H_1|\le 7r\alpha(G).

所以

|H_{2r+1}\cap H_1| \ge |H_{2r+1}|-|H_{2r+1}\setminus H_1| \ge \frac n4-(7r+1)\alpha(G).

由 $(28r+8)\alpha(G)<n$ 可知右端严格大于 $\alpha(G)$ 。但 $v_1v_{2r+1}\in E(G)$ ，因此 $H_1\cap H_{2r+1}$ 必须是独立集，大小至多为 $\alpha(G)$ ，矛盾。

G[B]

的证明完全相同。

∎

PDF

Download the original write-up here.

Part 5 of 5. ← Proof

改进

回到我们最初的这个问题，就是为什么取的是

\nu=1/500？

Proposition 1.

沿用原文的整体证明框架，并保持

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

N=\exp!\left(\frac{10\log(1/\nu)}{\nu}\right),

只要 0<\nu<1/321，则正文中从 Step 1 到 Step 5 的论证仍然可以完成。也就是说，把原文中的 \nu=1/500 换成任意 \nu<1/321 仍然足够。

Proof.

我们只需关注具体用的这个 \nu 的范围的地方：

先看 Step 3。对每个 v\in A_2，由 (clm:step2-a2-internal) 可知

\deg(v,V\setminus A2)\ge \frac n4-\nu|A1|.

将 (lem:large-regular-pair) 应用于二部图 G[A2,V\setminus A2] 后，对每个 v\in A_2'，有

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

注意到

|V\setminus A_2|=n-|A_2|,

|A_2|>(1-\nu)|A_1|,

所以

\begin{aligned} \nu|A1|+2\nu|V\setminus A2| &=\nu|A1|+2\nu(n-|A2|)\ &=2\nu n+\nu(|A1|-2|A2|)\ &<2\nu n, \end{aligned}

因为

|A_1|-2|A_2|<|A_1|-2(1-\nu)|A_1|=(2\nu-1)|A_1|<0.

于是对每个 v\in A_2'，都有

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

再像原文那样在 A_2' 中取一条边 uv，由

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

得到

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

接着由 B_3 的定义和 \nu^+-regular 性，

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

另一方面，Step 2 里已经有

|A_2|\ge \frac n2-7\nu n-\alpha(G).

因此

|V\setminus(A2\cup B3)|

=n-|A2|-|B3| <12\nu n+2\alpha(G).

由于 \alpha(G)<\nu^3 n，上式进一步给出

|V\setminus(A2\cup B3)|<(12\nu+2\nu^3)n.

现在回到 (obs:step4-split-degree)。对任意 x\in V\setminus(A_2\cup B_3)，由最小度条件 \delta(G)\ge n/4 得

\deg(x,A2)+\deg(x,B3)

\frac n4-(12\nu+2\nu^3)n.

若 x\in A'，则 \deg(x,B_3)\ge \deg(x,A_2)，从而

\deg(x,B_3)> \left(\frac18-6\nu-\nu^3\right)n.

同理，若 x\in B'，则

\deg(x,A_2)> \left(\frac18-6\nu-\nu^3\right)n.

接下来我们来看 (clm:step4-a-minus-aprime)。设 u1u2 是 A\setminus A'=A2 中的一条边。由 \deg(ui,A2)\le \nu|A1|<\nu n 以及

|A'|\le |V\setminus(A2\cup B3)|<12\nu n+2\alpha(G),

可得

\deg(u_i,A)<13\nu n+2\alpha(G).

于是

\deg(u_i,B)>\frac n4-13\nu n-2\alpha(G).

再利用

|N(u1)\cap N(u2)|\le \alpha(G),

可得

|(N(u1)\cup N(u2))\cap B|

\frac n2-26\nu n-5\alpha(G).

同时由

|B|\le \frac n2+7\nu n+\alpha(G)

得到

|B\setminus (N(u1)\cup N(u2))|

<33\nu n+6\alpha(G).

现在对任意 v\in A，都有

|N(v)\cap B|>

\left(\frac18-6\nu-\nu^3\right)n.

若同时有

|N(v)\cap N(u_1)\cap B|

\le \frac12\left(\left(\frac18-6\nu-\nu^3\right)n-(33\nu n+6\alpha(G))\right)

和

|N(v)\cap N(u_2)\cap B|

\le \frac12\left(\left(\frac18-6\nu-\nu^3\right)n-(33\nu n+6\alpha(G))\right),

那么就会推出

|N(v)\cap B|

< \left(\frac18-6\nu-\nu^3\right)n,

矛盾。因此至少有一个交集满足

|N(v)\cap N(u_i)\cap B|

\frac12\left(\left(\frac18-39\nu-\nu^3\right)n-6\alpha(G)\right).

只要右端大于 \alpha(G)，(clm:step4-a-minus-aprime) 的原论证就仍然成立。由 \alpha(G)<\nu^3 n，只需验证

\frac18-39\nu-9\nu^3>0.

解出来大概是 \nu<1/321 ，也就是说，当 \nu<1/321 时 (clm:step4-a-minus-aprime) 仍然成立。

一旦 (clm:step4-a-minus-aprime) 保持成立，后面的 (cor:step4-internal-degree) 和 (clm:step4-a-degree-alpha) 也可以用同样的方法继续推进。事实上，此时

\deg(v,A)<13\nu n+3\alpha(G),

是满足的。最后 Step 5 里涉及 |A|,|B| 的估计本来就只有 O(\alpha(G)) 量级，对 \nu 的选取也没有影响。

所以实际上我们取 \nu<1/321 也是能按照原文的思路完成证明的。

∎

下面我们给出一个比 (lem:large-regular-pair) 更强的参数化版本。相比 (lem:large-regular-pair) ，我们引入了一个新参数进行推广，得到了一个更精细的下界。

Proposition 2.

设 F 是二部图，二部划分为 (A,B)，其中

|A|=a, |B|=b.

假设每个 x\in A 在 B 中至少有 \delta b 个邻点。取参数

1<t<\frac{\delta}{\varepsilon},

并假设 0<\varepsilon<1。那么存在 X\subseteq A、Y\subseteq B，使得 F[X,Y] 是 \varepsilon^+-regular pair，并且

|Y|\ge

\frac{\delta-t\varepsilon}{1-t\varepsilon}b,

同时

\deg(x,Y)\ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b \forall x\in X,

而且

|X|

\ge \exp\left( - \frac{ \log\frac{1}{\varepsilon(1-1/t)} \cdot \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} } \right)a.

Proof.

我们沿用 (lem:large-regular-pair) 的迭代思想，把 2\varepsilon 改成 t\varepsilon。

从

X0=A, Y0=B

开始。若 F[Xi,Yi] 已经是 \varepsilon^+-regular pair，则停止。

否则，存在

S\subseteq Xi, T\subseteq Yi

满足

|S|\ge \varepsilon |X_i|,

|T|\ge \varepsilon |Y_i|,

且

d(S,T)<\varepsilon.

由 (clm:density-convexity)，可以取

X'{i+1}\subseteq S, Y'{i+1}\subseteq T

满足

|X'_{i+1}|=\varepsilon |X_i|,

|Y'_{i+1}|=\varepsilon |Y_i|,

并且

e(X'{i+1},Y'{i+1}) < \varepsilon |X'{i+1}||Y'{i+1}|.

令

Z{i+1} = \left{ x\in X'{i+1}: \deg(x,Y'{i+1})>t\varepsilon |Y'{i+1}| \right}.

因为总边数小于

\varepsilon |X'{i+1}||Y'{i+1}|,

所以

|Z_{i+1}|<\frac1t |X'_{i+1}|.

令

X{i+1}=X'{i+1}\setminus Z_{i+1},

Y{i+1}=Yi\setminus Y'_{i+1}.

则

|X_{i+1}|

\ge \left(1-\frac1t\right)|X'{i+1}| = \varepsilon\left(1-\frac1t\right)|Xi|,

并且

|Y_{i+1}|=(1-\varepsilon)|Y_i|.

所以若迭代进行了 l 步，则

|X_l|

\ge \left(\varepsilon\left(1-\frac1t\right)\right)^l a,

|Y_l|=(1-\varepsilon)^l b.

接下来估计 $l$ 。在每一步中，保留下来的 $x\in X_{i+1}$ 对被删掉的 $Y'_{i+1}$ 的邻点数至多

t\varepsilon |Y'_{i+1}|.

因此对任意 $x\in X_l$ ，它在所有被删去的 $Y$ -块中的邻点总数至多

t\varepsilon\sum_{j=1}^{l}|Y'_j| = t\varepsilon(b-|Y_l|).

由于一开始

\deg(x,B)\ge \delta b,

所以

\deg(x,Y_l) \ge \delta b-t\varepsilon(b-|Y_l|) = (\delta-t\varepsilon)b+t\varepsilon |Y_l|.

但是

\deg(x,Y_l)\le |Y_l|.

因此

|Y_l| \ge (\delta-t\varepsilon)b+t\varepsilon |Y_l|.

故

|Y_l| \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b.

又因为

|Y_l|=(1-\varepsilon)^l b,

所以

(1-\varepsilon)^l \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}.

取对数后可得

l \le \frac{ \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} }.

代回对 $X_l$ 的估计：

|X_l| \ge \left(\varepsilon\left(1-\frac1t\right)\right)^l a.

由于

0<\varepsilon\left(1-\frac1t\right)<1,

于是

|X_l| \ge \exp\left( - \frac{ \log\frac{1}{\varepsilon(1-1/t)} \cdot \log\frac{1-t\varepsilon}{\delta-t\varepsilon} }{ \log\frac1{1-\varepsilon} } \right)a.

如果过程停止，则得到的就是 $\varepsilon^+$ -regular pair。若过程一直不停止，那么 $Y_l$ 会持续按 $(1-\varepsilon)^l$ 缩小，最终也会与刚才推出的必要条件

|Y_l| \ge \frac{\delta-t\varepsilon}{1-t\varepsilon}b.

相矛盾！所以过程必定在某一步停止，命题得证。

∎

Proposition 3.

设 $G$ 是一个 $K_4$ -free 图，满足 $\delta(G)\ge n/4$ ，并且存在划分 $V(G)=A\cup B$ 满足 (clm:step4-a-degree-alpha) 与 (clm:step4-balance) 的结论。若 $r\ge 1$ 且

(28r+8)\alpha(G)<n,

则 $G[A]$ 与 $G[B]$ 都不含长度为 $2r+1$ 的圈。

Proof.

我们只证明 $G[A]$ 的情形。假设

v_1v_2\cdots v_{2r+1}v_1

是 $G[A]$ 中的一个圈，并记

H_i:=N(v_i)\cap B.

由 (clm:step4-a-degree-alpha) 与最小度条件可知

|H_i|\ge \frac n4-\alpha(G).

又由 (clm:step4-balance)，

|B|\le \frac n2+3\alpha(G).

对任意相邻的 $v_i,v_{i+1}$ ，集合 $H_i\cap H_{i+1}$ 必须是独立集，否则其中一条边会与 $v_iv_{i+1}$ 构成 $K_4$ 。因此

|H_i\cap H_{i+1}|\le \alpha(G).

从而

\begin{aligned} |B\setminus(H_i\cup H_{i+1})| &=|B|-|H_i|-|H_{i+1}|+|H_i\cap H_{i+1}|\\ &\le 6\alpha(G). \end{aligned}

于是

H_{i+2}\setminus H_i \subseteq \bigl(H_{i+2}\cap H_{i+1}\bigr) \cup \bigl(B\setminus(H_i\cup H_{i+1})\bigr),

故

|H_{i+2}\setminus H_i|\le 7\alpha(G).

将这个不等式沿奇数下标迭代 $r$ 次，得到

|H_{2r+1}\setminus H_1|\le 7r\alpha(G).

所以

|H_{2r+1}\cap H_1| \ge |H_{2r+1}|-|H_{2r+1}\setminus H_1| \ge \frac n4-(7r+1)\alpha(G).

由 $(28r+8)\alpha(G)<n$ 可知右端严格大于 $\alpha(G)$ 。但 $v_1v_{2r+1}\in E(G)$ ，因此 $H_1\cap H_{2r+1}$ 必须是独立集，大小至多为 $\alpha(G)$ ，矛盾。

G[B]

的证明完全相同。

∎

PDF

Download the original write-up here.

K₄ Ramsey–Turán V — Improvements

Search

K₄ Ramsey–Turán V — Improvements

改进

PDF

改进

PDF