K₄ Ramsey–Turán IV — Proof, Steps 4–5

Part 4 of 5. ← Steps 1–3 · Improvements →

Step 4

我们把

V-(A_2\cup B_3) 分成 A' 和 B'：

A'=\left{v\in V\setminus(A2\cup B3):\deg(v,B3)\ge \deg(v,A2)\right},

B'=\left\{v\in V\setminus(A_2\cup B_3):\deg(v,B_3)< \deg(v,A_2)\right\}.

再令

A=A_2\cup A', B=B_3\cup B'.

有

A\cap B=\emptyset, A\cup B=V.

且

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

Note.

由 Step 3 我们可知

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

又由于

A=A_2 \cup A',

故

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

另一方面，由于

A\cup B=V,

故

|B|=n-|A|\leq n-\left(\frac n2-7\nu n-\alpha(G)\right)=\frac n2+7\nu n+\alpha(G).

Observation.

对每个 $v\in A'$ ，有

\deg(v,B_3)\ge n/9;

对每个 $u\in B'$ ，有

\deg(u,A_2)\ge n/9.

原论文在这里写出的下界是 $n/9$ ，但若只使用前面已经粗化过的不等式

|V\setminus(A_2\cup B_3)|\le 14\nu n+2\alpha(G),

则对 $v\in A'$ 只能保证

\deg(v,B_3)\ge \left(\frac18-7\nu\right)n-\alpha(G).

当 $\nu=1/500$ 时，这个下界略小于 $n/9$ ，所以前面粗略估计不足以证明原结论。不过，保留 Step 3 中应用 (lem:large-regular-pair) 时得到的度数范围，我们可以把 $B_3$ 的下界加强到

|B_3|>\frac n2-5\nu n-\alpha(G),

从而补全 $n/9$ 的证明。

Note.

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

由 (clm:step2-a2-internal) 可知，对每个 $v\in A_2$ ，都有

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

将 (lem:large-regular-pair) 应用于二部图 $G[A_2,V\setminus A_2]$ 时，得到的集合 $A_2'$ 、 $B_2$ 满足：对每个 $v\in A_2'$ ，

\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} \deg(v,B_2) &\ge \frac n4-\nu|A_1|-2\nu(n-|A_2|)\\ &\ge \frac n4-2\nu n+(\nu-2\nu^2)|A_1|\\ &>\frac n4-2\nu n. \end{aligned}

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

|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).

再结合 Step 2 中

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

便有

|V\setminus(A_2\cup B_3)| <12\nu n+2\alpha(G) <(12\nu+2\nu^3)n <\frac n{36}.

因此，对任意 $x\in V\setminus(A_2\cup B_3)$ ，由 $\delta(G)\ge n/4$ 可得

\deg(x,A_2)+\deg(x,B_3) >\frac n4-\frac n{36}=\frac{2n}{9}.

若 $x\in A'$ ，则 $\deg(x,B_3)\ge\deg(x,A_2)$ ，故

\deg(x,B_3)>\frac n9.

若 $x\in B'$ ，则 $\deg(x,A_2)>\deg(x,B_3)$ ，故

\deg(x,A_2)>\frac n9.

上面的计算实际上给出了比 $n/9$ 更精确的结论。由

|A_2|\ge\frac n2-7\nu n-\alpha(G), |B_3|>\frac n2-5\nu n-\alpha(G)

可得

|V\setminus(A_2\cup B_3)| <12\nu n+2\alpha(G) <(12\nu+2\nu^3)n.

因此，对任意 $x\in V\setminus(A_2\cup B_3)$ ，都有

\deg(x,A_2)+\deg(x,B_3)> \left(\frac14-12\nu-2\nu^3\right)n.

结合 $A'$ 、 $B'$ 的定义，可以进一步得到

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

以及

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

Claim.

若 $v\in A$ ，则

\deg(v,A\setminus A')\le \alpha(G);

同理，若 $u\in B$ ，则

\deg(u,B\setminus B')\le \alpha(G).

Proof.

我们只证明关于 $A$ 的部分；关于 $B$ 的部分的证明完全相同。假设存在某个 $v\in A$ 满足

\deg(v,A\setminus A')>\alpha(G).

于是

N(v)\cap (A\setminus A')

中存在一条边，记其两个端点为 $u_1,u_2$ 。由于 $G$ 是 $K_4$ -free 图，

|N(u_1)\cap N(u_2)|\le \alpha(G).

Note.

若否，若有

|N(u_1)\cap N(u_2)|> \alpha(G).

则存在 $w_1,w_2\in N(u_1)\cap N(u_2)$ ，那么此时

w_1,w_2,u_1,u_2

两两相连，构成一个 $K_4$ ，矛盾！

另一方面， $u_1,u_2\in A\setminus A'=A_2$ 。由 (clm:step2-a2-internal) 可知，它们在 $A_2$ 内各自都只有少于 $\nu n$ 个邻点。故它们在 $A'$ 中的邻点数至多为

|A'|\le |A'|+|B'|\le 14\nu n+2\alpha(G)<15\nu n,

于是由 (obs:edge-neighborhood-sum)，我们有

|(N(u_1)\cup N(u_2))\cap B|>\frac n2-33\nu n.

Note.

由上面的估计可知，对 $i=1,2$ ，都有

\deg(u_i,A)<\nu n+15\nu n=16\nu n.

因此由 $\delta(G)\ge n/4$ 可得

\deg(u_i,B)\ge \frac n4-16\nu n.

又因为 $u_1u_2\in E(G)$ ，由 (obs:edge-neighborhood-sum) 作用于集合 $B$ 得

\deg(u_1,B)+\deg(u_2,B)\le |B|+\alpha(G).

另一方面，

|(N(u_1)\cup N(u_2))\cap B| =\deg(u_1,B)+\deg(u_2,B)-|N(u_1)\cap N(u_2)\cap B|.

由

|N(u_1)\cap N(u_2)\cap B|\le |N(u_1)\cap N(u_2)|\le \alpha(G)

便得到

|(N(u_1)\cup N(u_2))\cap B| \ge \deg(u_1,B)+\deg(u_2,B)-\alpha(G) \ge 2\left(\frac n4-16\nu n\right)-\alpha(G) =\frac n2-32\nu n-\alpha(G).

再由 (fact:alpha-small) 知 $\alpha(G)=\alpha n<\nu^3n<\nu n$ ，所以

\frac n2-32\nu n-\alpha(G)>\frac n2-33\nu n.

另一方面，由 Step 4 中对 $|B|$ 的上界可知

|B|\le \left(\frac12+7\nu\right)n+\alpha(G),

从而

|B\setminus (N(u_1)\cup N(u_2))| <\left(\frac12+7\nu\right)n+\alpha(G)-\left(\frac12-33\nu\right)n <41\nu n.

下面说明 $v$ 在 $B$ 中至少有 $n/9$ 个邻点。若 $v\in A'$ ，则由 (obs:step4-split-degree) 立刻有

\deg(v,B)\ge \deg(v,B_3)\ge \frac n9.

若 $v\in A_2$ ，则由 (clm:step2-a2-internal) 以及 $|A'|<15\nu n$ 可得

\deg(v,A)\le \deg(v,A_2)+|A'|<\nu n+15\nu n=16\nu n,

从而

\deg(v,B)\ge \delta(G)-\deg(v,A)\ge \frac n4-16\nu n>\frac n9.

因此总有

|N(v)\cap B|\ge \frac n9.

若

|N(v)\cap N(u_1)\cap B|\le \frac12\left(\frac n9-41\nu n\right)

且

|N(v)\cap N(u_2)\cap B|\le \frac12\left(\frac n9-41\nu n\right),

那么

|N(v)\cap B| \le |N(v)\cap N(u_1)\cap B|+|N(v)\cap N(u_2)\cap B|+|B\setminus (N(u_1)\cup N(u_2))| < \left(\frac n9-41\nu n\right)+41\nu n=\frac n9,

这与 $|N(v)\cap B|\ge n/9$ 矛盾。因此至少有一个集合

N(v)\cap N(u_1)\cap B, N(v)\cap N(u_2)\cap B

的大小严格大于

\frac12\left(\frac n9-41\nu n\right).

再由 (fact:alpha-small) 以及 $1/9-41\nu>1/90$ 可得

\frac12\left(\frac n9-41\nu n\right)>\alpha(G).

Note.

由 $\nu=1/500$ 可知

\frac19-41\nu=\frac19-\frac{41}{500}>\frac1{90},

从而

\frac12\left(\frac n9-41\nu n\right) =\frac12\left(\frac19-41\nu\right)n >\frac{n}{180}.

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

\alpha(G)=\alpha n<\nu^3n=\frac{n}{500^3}<\frac{n}{180}.

于是

\frac12\left(\frac n9-41\nu n\right)>\alpha(G).

于是这两个集合中至少有一个含有多于 $\alpha(G)$ 个顶点，从而其中必有两个顶点彼此相邻。无论出现在哪一个集合中，这两个顶点都与 $v$ 以及对应的 $u_i$ 相邻，从而构成一个 $K_4$ ，矛盾。

故对每个 $v\in A$ 都有

\deg(v,A\setminus A')\le \alpha(G).

∎

Corollary 1.

每个 $A$ 中的顶点在 $A$ 内至多有

|A'|+\alpha(G)<16\nu n

个邻点；同理，每个 $B$ 中的顶点在 $B$ 内至多有

|B'|+\alpha(G)<16\nu n

个邻点。

Note.

任取 $v\in A$ 。由 (clm:step4-a-minus-aprime) 可知

\deg(v,A\setminus A')\le \alpha(G).

因此

\deg(v,A)\le \deg(v,A\setminus A')+|A'|\le \alpha(G)+|A'|.

又由 Step 4 中

|A'|<|A'|+|B'|\le 14\nu n+2\alpha(G)<15\nu n

以及 (fact:alpha-small) 中的 $\alpha(G)<\nu n$ ，便得到

\deg(v,A)\le |A'|+\alpha(G)<16\nu n.

关于 $B$ 的证明也完全相同。

Claim.

任意 $v\in A$ 都满足

\deg(v,A)\le \alpha(G),

任意 $u\in B$ 都满足

\deg(u,B)\le \alpha(G).

Proof.

我们只证明关于 $A$ 的部分，关于 $B$ 的部分完全同理。假设存在某个 $v\in A$ 满足

\deg(v,A)>\alpha(G).

则集合

N(v)\cap A

的大小大于 $\alpha(G)$ ，因而它不可能是独立集。于是其中存在两个相邻顶点，记为 $u,w$ 。这样 $u,v,w$ 在 $A$ 中构成一个三角形。

对这三个顶点，利用 (cor:step4-internal-degree) 可知它们在 $A$ 中的度都小于 $16\nu n$ ，从而都在 $B$ 中至少有

\delta(G)-16\nu n\ge \frac n4-16\nu n

个邻点。设

H_v=N(v)\cap B, H_u=N(u)\cap B, H_w=N(w)\cap B.

若三对交集

H_v\cap H_u, H_v\cap H_w, H_u\cap H_w

都至多有 $\alpha(G)$ 个顶点，那么

|H_v|+|H_u|+|H_w| \le |H_v\cup H_u\cup H_w|+|H_v\cap H_u|+|H_v\cap H_w|+|H_u\cap H_w| \le |B|+3\alpha(G).

另一方面，

|H_v|+|H_u|+|H_w| \ge 3\left(\frac n4-16\nu n\right)=\frac{3n}{4}-48\nu n.

又由 Step 4 中的上界

|B|\le \left(\frac12+7\nu\right)n+\alpha(G)

可知

\frac{3n}{4}-48\nu n \le |B|+3\alpha(G) \le \left(\frac12+7\nu\right)n+4\alpha(G).

这推出

\left(\frac14-55\nu\right)n\le 4\alpha(G).

但由 (fact:alpha-small) 有 $\alpha(G)<\nu n$ ，于是右边小于 $4\nu n$ ，从而

\left(\frac14-59\nu\right)n<0,

这与 $\nu=1/500$ 矛盾。

因此，上面三对交集中至少有一对的大小大于 $\alpha(G)$ 。不妨设

|H_v\cap H_u|>\alpha(G).

那么集合

H_v\cap H_u

不可能是独立集，于是其中存在两个相邻顶点 $x,y$ 。于是

u,v,x,y

两两相邻，构成一个 $K_4$ ，矛盾。

故对每个 $v\in A$ 都有

\deg(v,A)\le \alpha(G).

∎

Claim.

存在某个非负整数 $k\le 3\alpha(G)$ ，使得

\frac n2-k\le |A|,|B|\le \frac n2+k.

Proof.

在 Step 4 中我们已经得到

|A|\ge \frac n2-7\nu n-\alpha(G)>\alpha(G),

即集合 $A$ 不可能是独立集，因此 $A$ 中存在一条边。取 $u,v\in A$ 且 $uv\in E(G)$ 。由 (clm:step4-a-degree-alpha) 可知

\deg(u,A),\deg(v,A)\le \alpha(G).

又由最小度条件 $\delta(G)\ge n/4$ ，得到

\deg(u,B)\ge \frac n4-\alpha(G), \deg(v,B)\ge \frac n4-\alpha(G).

又由 (obs:edge-neighborhood-sum) 可得

|B|\ge \deg(u,B)+\deg(v,B)-\alpha(G) \ge 2\left(\frac n4-\alpha(G)\right)-\alpha(G) =\frac n2-3\alpha(G).

Note.

在 (obs:edge-neighborhood-sum) 取边 $uv$ 以及 $S=B$ 。

同理也有

|A|\ge \frac n2-3\alpha(G).

由于

A\cap B=\emptyset, A\cup B=V(G), |V(G)|=n,

故3

|B|=n-|A|\leq n-\left(\frac{n}{2}-3\alpha(G)\right)=\frac{n}{2}+3\alpha(G).

同理也有

|A|\leq \frac{n}{2}+3\alpha(G)

即存在某个非负整数 $k\le 3\alpha(G)$ ，使得

\frac n2-k\le |A|,|B|\le \frac n2+k.

∎

Claim.

图 $G[A]$ 与 $G[B]$ 都不含长度为 $3,5,7$ 的奇圈。

Proof.

我们只证明 $G[A]$ 的情形， $G[B]$ 的证明完全同理。

由 (clm:step4-a-degree-alpha) 我们可知 $G[A]$ 中不含三角形，因此我们只需证不包含 $C_5$ 和 $C_5$ 。

我们先证明 \keypart{ $G[A]$ 不含 $C_5$ }。假设存在 $C_5$ ，即有

v_1,v_2,v_3,v_4,v_5\in A

满足

v_iv_{i+1}\in E(G) (i=1,2,3,4).

对 $1\le i\le 5$ ，记

H_i=N(v_i)\cap B.

由于 $G$ 是 $K_4$ -free 图，集合 $H_1\cap H_2$ 与 $H_2\cap H_3$ 都是独立集，从而

|H_1\cap H_2|\le \alpha(G), |H_2\cap H_3|\le \alpha(G).

Note.

若否，即若有

|H_1\cap H_2|> \alpha(G).

则存在 $x,y\in H_1\cap H_2$ 且 $xy\in E$ ，则

v_1,v_2,x,y

两两相连，即构成一个 $K_4$ ，矛盾！

另一方面，由 (clm:step4-a-degree-alpha) 可知，对每个 $1\le i\le 5$ ，都有

|H_i|=\deg(v_i,B)\ge \frac n4-\alpha(G).

再由 (clm:step4-balance) 得

|B\setminus H_{i+1}| \le \frac n2+3\alpha(G)-\left(\frac n4-\alpha(G)\right) =\frac n4+4\alpha(G).

由于

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

则对 $i=1,2,3,4$ ，都有

|H_i|\le \frac n4+4\alpha(G)+\alpha(G)=\frac n4+5\alpha(G).

又有

|B\setminus (H_1\cup H_2)|=|B|-|H_1|-|H_2|+|H_1\cap H_2| \le \frac n2+3\alpha(G)-2\left(\frac n4-\alpha(G)\right)+\alpha(G) =6\alpha(G).

故 $v_3$ 在 $B\setminus (H_1\cup H_2)$ 中至多有 $6\alpha(G)$ 个邻点，而在 $H_2$ 中至多还有 $\alpha(G)$ 个邻点，所以

|H_1\cap H_3|\ge \frac n4-8\alpha(G).

Note.

由于

B=H_1\cup H_2\cup (B-(H_1\cap H_2)),

故

H_3\subseteq(H_3\cap H_2)\cup(H_3\cap H_2)\cup(B-(H_1\cap H_2)).

那么

|H_3|\leq|H_3\cap H_1|+|H_3\cap H_2|+|B-(H_1\cap H_2)|,

则

|H_1\cap H_3|\ge |H_3|-|H_3\cap H_2|-|B-(H_1\cap H_2)|\ge \frac{n}{4}-\alpha(G)-\alpha(G)-6\alpha(G)=\frac{n}{4}-8\alpha(G)

同理可得

|H_3\cap H_5|\ge \frac n4-8\alpha(G).

另一方面，由

|H_3\setminus H_1|=|H_3|-|H_1\cap H_3|

以及前面的估计，得到

|H_3\setminus H_1| \le \left(\frac n4+5\alpha(G)\right)-\left(\frac n4-8\alpha(G)\right) =13\alpha(G).

从而

|H_5\cap H_1| \ge |H_5\cap H_1\cap H_3| =|H_5\cap H_3|-|H_5\cap (H_3\setminus H_1)| \ge \left(\frac n4-8\alpha(G)\right)-13\alpha(G) =\frac n4-21\alpha(G).

由 (fact:alpha-small) 知 $\alpha(G)=\alpha n<\nu^3n<n/84$ ，故

\frac n4-21\alpha(G)>\alpha(G).

于是 $H_5\cap H_1$ 中有多于 $\alpha(G)$ 个顶点，不可能是独立集，因此其中存在一条边。这样与边 $v_1v_5$ 一起便构成一个 $K_4$ ，矛盾。故 $G[A]$ 不含 $C_5$ 。

下面证明 \keypart{ $G[A]$ 不含 $C_7$ }。假设

v_1,v_2,\ldots,v_7\in A

满足

v_iv_{i+1}\in E(G) (i=1,2,\ldots,6).

仍记

H_i=N(v_i)\cap B (1\le i\le 7).

由前面对 $C_5$ 情形的同样论证可得

|H_3\setminus H_1|\le 13\alpha(G), |H_7\cap H_3|\ge \frac n4-21\alpha(G),

以及

|H_7\cap (H_3\setminus H_1)|\le 13\alpha(G).

于是

|H_7\cap H_1| \ge |H_7\cap H_3\cap H_1| =|H_7\cap H_3|-|H_7\cap (H_3\setminus H_1)| \ge \left(\frac n4-21\alpha(G)\right)-13\alpha(G) =\frac n4-34\alpha(G).

同样由 (fact:alpha-small) 可知

\frac n4-34\alpha(G)>\alpha(G).

因此 $H_7\cap H_1$ 中有多于 $\alpha(G)$ 个顶点，不可能是独立集，于是其中存在一条边。这样便与边 $v_1v_7$ 构成一个 $K_4$ ，矛盾。

关于 $G[B]$ 不包含 $C_5$ 和 $C_7$ 的证明完全相同。

Remark 13.

事实上，这么推广的话， $G[A]$ 和 $G[B]$ 都不包含奇圈，除非奇圈 $C_{2m+1}$ 的 $m$ 足够大。

∎

原文这里只排除了 $C_3,C_5,C_7$ ，是因为后面调用 (lem:no-357-edge-bound) 时已经足够了。不过上面的计算其实还能继续往后推：每沿奇圈前进两个顶点，相应邻域与前一个邻域之间至多多损失 $7\alpha(G)$ 个点，我给出了对于一般奇圈的版本，具体请见 (prop4.3)。

Lemma 2.

若图 $F$ 不含长度为 $3,5,7$ 的圈，则

e(F)\le \alpha(F)^2.

Note.

（这个引理来自\cite[Lemma 7.1]{LudersReiher2019}，在本论文中没有给出证明，我补充出证明。）

我们按如下操作取 $F$ 中一列互不相同的顶点

z_1,z_2,\ldots,z_k.

先令 $z_1$ 是 $F$ 中一个度最大的顶点。若已经选出了

z_1,z_2,\ldots,z_i,

就考虑集合 $Q_i$ ，它由所有与这些顶点的距离都至少为 $4$ 的顶点组成。若 $Q_i=\emptyset$ ，就令 $k=i$ 并停止；否则就在 $Q_i$ 中取一个度最大的顶点作为 $z_{i+1}$ 。

令

Q_0=V(F), W_i=Q_{i-1}\setminus Q_i (1\le i\le k).

由于

Q_0\supseteq Q_1\supseteq \cdots \supseteq Q_k=\emptyset,

于是

V(F)=W_1\sqcup W_2\sqcup\cdots\sqcup W_k

由 $z_i$ 在 $Q_{i-1}$ 中度最大可知

2e(F)=\sum_{x\in V(F)}d(x)\le \sum_{i=1}^k |W_i|\,d(z_i).

下面我们来说明：对每个 $i\in [k]$ ，集合 $W_i$ 中每个顶点到 $z_i$ 的距离都至多为 $3$ 。

事实上，若 $x\in W_i$ ，因为 $x\notin Q_i$ ，所以存在某个 $j\le i$ ，使得 $x$ 到 $z_j$ 的距离至多为 $3$ 。而若 $j<i$ ，则 $x\notin Q_{i-1}$ ，这与 $x\in W_i\subseteq Q_{i-1}$ 矛盾。因此只能是 $j=i$ 。

于是 $W_i$ 可分成两部分：一部分由到 $z_i$ 的距离为 $0$ 或 $2$ 的顶点组成，另一部分由到 $z_i$ 的距离为 $1$ 或 $3$ 的顶点组成。下面说明 这两部分都是独立集。

若前一部分中有两个相邻顶点 $x,y$ ，那么设

\operatorname{dist}(z_i,x)=2, \operatorname{dist}(z_i,y)=2

时，沿着从 $z_i$ 到 $x$ 、 $y$ 的最短路再加上边 $xy$ ，就会得到长度为 $5$ 或 $7$ 的奇圈；若其中一个顶点就是 $z_i$ ，则得到三角形。类似地，若后一部分中有两个相邻顶点，也会得到长度为 $3,5$ 或 $7$ 的奇圈。这与 $F$ 的假设矛盾。

因此这两部分都是独立集，从而

|W_i|\le 2\alpha(F) (1\le i\le k).

代回前面的估计，得到

e(F)\le \alpha(F)\sum_{i=1}^k d(z_i).

最后，由构造可知任意两个 $z_i,z_j$ 之间的距离都至少为 $4$ 。我们先说明 这些顶点的邻域两两不交。 若存在某个顶点

x\in N(z_i)\cap N(z_j) (i\neq j),

那么

z_i-x-z_j

就是一条长度为 $2$ 的路，这与 $z_i,z_j$ 之间的距离至少为 $4$ 矛盾。因此

N(z_i)\cap N(z_j)=\emptyset (i\neq j).

再说明

N(z_1)\cup N(z_2)\cup\cdots\cup N(z_k)

是一个独立集。若不然，设其中有一条边 $xy$ 。若 $x,y\in N(z_i)$ 对某个 $i$ 成立，那么

z_i,x,y

构成一个三角形，这与假设矛盾。若 $x\in N(z_i)$ 、 $y\in N(z_j)$ 且 $i\neq j$ ，那么

z_i-x-y-z_j

是一条连接 $z_i$ 和 $z_j$ 的长度为 $3$ 的路，这同样与 $z_i,z_j$ 之间的距离至少为 $4$ 矛盾。故上述邻域的并确实是独立集。

由于这些邻域两两不交，便有

\sum_{i=1}^k d(z_i)=\sum_{i=1}^k |N(z_i)| =\left|N(z_1)\cup N(z_2)\cup\cdots\cup N(z_k)\right|.

而上式右边是一个独立集的大小，所以不超过 $\alpha(F)$ 。于是

\sum_{i=1}^k d(z_i)\le \alpha(F).

综上，

e(F)\le \alpha(F)\sum_{i=1}^k d(z_i)\le \alpha(F)^2.

Step 5

把 $A$ 分为

A=I_A\cup L_A\cup M_A,

把 $B$ 分为

B=I_B\cup L_B\cup M_B.

其中

I_A=\{v\in A:\deg(v,B)>|B|/2+4\alpha(G)\}, L_A=\{v\in A\setminus I_A:(|B|+\alpha(G))/2<\deg(v,B)\le |B|/2+4\alpha(G)\}, M_A=A\setminus (I_A\cup L_A),

而 $I_B,L_B,M_B$ 的定义与之完全类似。

Claim.

集合 $I_A\cup L_A$ 在 $G[A]$ 中是独立集，集合 $I_B\cup L_B$ 在 $G[B]$ 中也是独立集；此外， $I_A$ 中的顶点在 $A$ 内没有邻点， $I_B$ 中的顶点在 $B$ 内也没有邻点。

Proof.

任取两个不同的顶点

u,v\in I_A\cup L_A.

由定义可知，它们在 $B$ 中的度之和满足

\deg(u,B)+\deg(v,B)> |B|+\alpha(G).

若 $uv\in E(G)$ ，在 (obs:edge-neighborhood-sum) 取边 $uv$ 与 $S=B$ ，则有

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

矛盾！因此

uv\notin E(G),

这说明 $I_A\cup L_A$ 在 $G[A]$ 中是独立集，同理也有 $I_B\cup L_B$ 在 $G[B]$ 中也是独立集。

Note.

（关于证明 $I_A$ 中的顶点在 $A$ 内没有邻点，论文中只给了一个简要的思路，我把整个证明过程补充出来）

由 (clm:step4-a-degree-alpha) 可知， $A$ 中每个顶点在 $A$ 内至多有 $\alpha(G)$ 个邻点，又由 (clm:step4-balance) 可知

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

因此对任意 $v\in A$ ，由最小度条件 $\delta(G)\ge n/4$ 得

\deg(v,B)\ge \frac n4-\alpha(G).

再由

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

推出

\frac n4-\alpha(G)>\frac{|B|}{2}-3\alpha(G).

于是若 $u\in I_A$ ，则

\deg(u,B)> \frac{|B|}{2}+4\alpha(G).

若 $u$ 在 $A$ 中还有某个邻点 $v$ ，则

\deg(u,B)+\deg(v,B)> \left(\frac{|B|}{2}+4\alpha(G)\right)+\left(\frac{|B|}{2}-3\alpha(G)\right) =|B|+\alpha(G).

再对边 $uv$ 与 $S=B$ 用 (obs:edge-neighborhood-sum)，可得

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

矛盾！因此 $u$ 在 $A$ 中没有邻点。

同理， $I_B$ 中的顶点在 $B$ 内也没有邻点。

∎

接下来，我们进行这样一个操作：

对每个 $v\in L_A$ ，删去所有连接 $v$ 与 $A$ 中其他顶点的边，并加入所有形如

vu (u\in B)

的边。对 $L_B$ 中的顶点也做同样的操作：删去其在 $B$ 内部的边，并加入其与 $A$ 之间的所有边。

对每个 $v\in I_A$ ，加入所有形如

uv (u\in B)

的边。类似地，对每个 $u\in I_B$ ，加入所有形如

uv (v\in A)

的边。

Remark 14.

注意到，由于 $G[A]$ 与 $G[B]$ 都不含长度为 $3,5,7$ 的圈，而在上述操作中我们只会从 $A$ 与 $B$ 的内部删边，所以 $G'[A]$ 与 $G'[B]$ 也仍然不含长度为 $3,5,7$ 的圈。

Claim.

经过上述操作后得到的新图 $G'$ 的总边数不会比原图 $G$ 边数更少，而且 $G'$ 仍然是 $K_4$ -free 的。

Proof.

我们先来估计在操作过程中 删掉的边数：

对任意 $v\in L_A$ ，按定义它在 $B$ 中至多有

\frac{|B|}{2}+4\alpha(G)

个邻点，而在 $A$ 中至多有 $\alpha(G)$ 个邻点，并且这些 $A$ 中的邻点都属于 $M_A$ 。因此

e(G[M_A,L_A])\le \alpha(G)\,|L_A|.

同理，

e(G[M_B,L_B])\le \alpha(G)\,|L_B|.

也就是说，在整个操作中，我们至多失去

\alpha(G)|L_A|+\alpha(G)|L_B|

条内部边。

下面我们来估计 新加入的边数。任取 $v\in L_A$ 。由定义， $v$ 在 $M_B$ 中至多有

\frac{|B|}{2}+4\alpha(G)

个邻点，因此我们在 $v$ 处至少加入

|M_B|-\left(\frac{|B|}{2}+4\alpha(G)\right)

条新边。又由 $\text{clm:step5-independent}$ 我们可知 $I_B\cup L_B$ 是独立集，故

|M_B|=|B|-|I_B|-|L_B|\ge |B|-\alpha(G),

于是

|M_B|-\left(\frac{|B|}{2}+4\alpha(G)\right) \ge |B|-\alpha(G)-\left(\frac{|B|}{2}+4\alpha(G)\right) =\frac{|B|}{2}-5\alpha(G).

因此每个 $v\in L_A$ 至少贡献

\frac{|B|}{2}-5\alpha(G)

条新边。同理，对每个 $v\in L_B$ ，至少加入

\frac{|A|}{2}-5\alpha(G)

条新边。

所以，总边数的变化至少为

\left(\frac{|B|}{2}-5\alpha(G)\right)|L_A| \;+\; \left(\frac{|A|}{2}-5\alpha(G)\right)|L_B| \;-\; \alpha(G)(|L_A|+|L_B|).

也就是

\left(\frac{|B|}{2}-6\alpha(G)\right)|L_A| \;+\; \left(\frac{|A|}{2}-6\alpha(G)\right)|L_B|.

再由 (clm:step4-balance) 得

|A|,|B|\ge \frac n2-3\alpha(G),

从而

\frac{|A|}{2}-6\alpha(G)\ge \frac n4-\frac{15}{2}\alpha(G), \frac{|B|}{2}-6\alpha(G)\ge \frac n4-\frac{15}{2}\alpha(G).

结合 (fact:alpha-small) 中 $\alpha(G)\ll n$ ，上面两个系数都为正，因此总边数变化非负。于是

e(G')\ge e(G).

下面证明 \keypart{ $G'$ 仍然是 $K_4$ -free} 。假设 $G'$ 中存在一个 $K_4$ 。由 (clm:step5-independent) 我们可知 $I_A\cup L_A$ 和 $I_B\cup L_B$ 都是独立集，故 $K_4$ 不可能包含上面两个集合的点。

其次，这个 $K_4$ 也不可能同时包含一个来自 $I_A\cup L_A$ 的顶点和一个来自 $I_B\cup L_B$ 的顶点，因为在 $G'$ 中，前者只与 $B$ 中顶点相邻，后者只与 $A$ 中顶点相邻，它们不可能再与另外两个顶点一起构成 $K_4$ 。

此外，由于 $G'[A]$ 与 $G'[B]$ 都不包含 $C_3$ 。因此 $K_4$ 不可能包含任何来自

I_A\cup L_A\cup I_B\cup L_B

的顶点。

于是唯一剩下的可能是这个 $K_4$ 的四个顶点全部属于

M_A\cup M_B.

但在 $M_A\cup M_B$ 上，我们并没有删去或添加边，又因为任意四个在 $M_A\cup M_B$ 的顶点在原图 $G$ 中不可能构成 $K_4$ ，矛盾！

因此 $G'$ 仍然是 $K_4$ -free 的。

∎

Claim.

有

e(G'[M_A])\le \bigl(\alpha(G)-(|I_A|+|L_A|)\bigr)^2,

以及

e(G'[M_B])\le \bigl(\alpha(G)-(|I_B|+|L_B|)\bigr)^2.

Proof.

由 (lem:no-357-edge-bound) 以及 (clm:step5-independent) 可知， $I_A\cup L_A$ 在 $G'[A]$ 中是独立集， $I_B\cup L_B$ 在 $G'[B]$ 中也是独立集；并且

e\bigl(G'[M_A,\,I_A\cup L_A]\bigr)=0, e\bigl(G'[M_B,\,I_B\cup L_B]\bigr)=0.

因此， $G'[M_A]$ 的最大独立集至多有

\alpha(G)-|I_A|-|L_A|

个顶点；同理， $G'[M_B]$ 的最大独立集至多有

\alpha(G)-|I_B|-|L_B|

个顶点。

又由于 $G'[M_A]$ 与 $G'[M_B]$ 仍然都不含长度为 $3,5,7$ 的圈，由 (lem:no-357-edge-bound) 我们可得

e(G'[M_A])\le \bigl(\alpha(G)-(|I_A|+|L_A|)\bigr)^2,

以及

e(G'[M_B])\le \bigl(\alpha(G)-(|I_B|+|L_B|)\bigr)^2.

∎

有了前面这么多的准备，我们下面来完成对主定理 (thm1.3) 的证明。

(thm1.3) 的证明.

我们记

a=|A|, b=|B|, m_A=|M_A|, m_B=|M_B|.

由 (clm:step4-balance)，我们设

a=\frac n2+k, b=\frac n2-k

其中

0\le k\le 3\alpha(G).

定义

f_A(x)=x\cdot \frac{b+\alpha(G)}{2}+(a-x)b+2\bigl(\alpha(G)-(a-x)\bigr)^2, f_B(x)=x\cdot \frac{a+\alpha(G)}{2}+(b-x)a+2\bigl(\alpha(G)-(b-x)\bigr)^2.

我们断言

\sum_{v\in A}d_{G'}(v)\le f_A(m_A).

Note.

（论文中关于这个结论一笔带过，我补充出证明）

M_A

中每个顶点在 $B$ 中至多有

\frac{|B|+\alpha(G)}{2}=\frac{b+\alpha(G)}{2}

个邻点；而 $A\setminus M_A=I_A\cup L_A$ 中的每个顶点在 $G'$ 中都与 $B$ 的所有顶点相邻，所以这部分对 $A$ 中度数和的贡献至多为

(a-m_A)b.

此外， $A$ 内部的边只可能出现在 $M_A$ 中，并且由 (clm:step5-ma-mb) 有

e(G'[M_A])\le \bigl(\alpha(G)-(a-m_A)\bigr)^2.

因此这些内部边对 $A$ 中度数和的贡献至多为

2\bigl(\alpha(G)-(a-m_A)\bigr)^2.

合并即得

\sum_{v\in A}d_{G'}(v)\le f_A(m_A).

同理

\sum_{u\in B}d_{G'}(u)\le f_B(m_B).

于是

2e(G')\le f_A(m_A)+f_B(m_B).

另一方面，由 (clm:step5-independent) 可知 $I_A\cup L_A$ 与 $I_B\cup L_B$ 都是独立集，因此

|I_A|+|L_A|\le \alpha(G), |I_B|+|L_B|\le \alpha(G).

于是

m_A\ge a-\alpha(G), m_B\ge b-\alpha(G).

下面我们说明 $f_A$ 与 $f_B$ 在相应区间上都是单调递减的。对 $f_A$ 求导，

f_A'(x)=\frac{\alpha(G)-b}{2}+4\bigl(\alpha(G)-a+x\bigr).

由 $b\ge n/2-3\alpha(G)$ 以及 $\alpha(G)\ll n$ ，我们可知当 $a-\alpha(G)\le x\le a$ 时，

f_A'(x)\le \frac{\alpha(G)-b}{2}+4\alpha(G)=\frac{9\alpha(G)-b}{2}<0,

因此 $f_A$ 在 $[a-\alpha(G),a]$ 上单调递减，同理 $f_B$ 在 $[b-\alpha(G),b]$ 上也单调递减。

所以

f_A(m_A)\le f_A(a-\alpha(G)), f_B(m_B)\le f_B(b-\alpha(G)).

代入可得

f_A(a-\alpha(G)) =\left(a-\alpha(G)\right)\frac{b+\alpha(G)}{2}+\alpha(G)b, f_B(b-\alpha(G)) =\left(b-\alpha(G)\right)\frac{a+\alpha(G)}{2}+\alpha(G)a.

即

f_A(a-\alpha(G))=f_B(b-\alpha(G)) =\frac{ab+\alpha(G)n-\alpha(G)^2}{2}.

从而

2e(G')\le ab+\alpha(G)n-\alpha(G)^2.

再由 (clm:step5-gprime) 知

e(G)\le e(G'),

故

2e(G)\le ab+\alpha(G)n-\alpha(G)^2.

又因为

ab=\left(\frac n2+k\right)\left(\frac n2-k\right)=\frac{n^2}{4}-k^2,

所以

e(G)\le \frac{n^2}{8}+\frac{\alpha(G)n}{2}-\frac{\alpha(G)^2}{2}-\frac{k^2}{2} \le \frac{n^2}{8}+\frac{\alpha(G)n}{2}-\frac{\alpha(G)^2}{2}.

而主定理的条件是

e(G)>\frac{n^2+n}{8}+\frac{\alpha(G)n-\alpha(G)^2}{2},

矛盾！这表明从一开始我们关于 $G$ 中包含 $K_4$ 的假设是错的，即 $G$ 中不包含 $K_4$ 。

∎

PDF

Download the original write-up here.

K₄ Ramsey–Turán IV — Proof, Steps 4–5

Search

K₄ Ramsey–Turán IV — Proof, Steps 4–5

Step 4

Step 5

PDF