K₄ Ramsey–Turán II — Tools

Loading…

K₄ Ramsey–Turán II — Tools

Part 2 of 5. ← Survey · Proof →

定义与主要工具

关于图

G 的最小度

我们从原图 G 中取一个最小子集 V1\subseteq V，令 G1=G[V1]，并记 n1=|V1|、\alpha1=\alpha(G1)/n1，其中 V_1 满足：

e(G1)>\frac{|V1|^2+|V_1|}{8}+\frac{\alpha-\alpha^2}{2}n^2,

Remark 7.

我觉得这一步是整篇论文最关键的地方。

主定理中的条件是：

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

然后在这里，我们之所以先这样取一个极小的诱导子图 G1，主要是为了同时保留“边数仍然足够多”和“结构更容易控制”这两个特点。这样的话，我们一旦删去任意一个顶点就会破坏边数条件，于是在此基础上可以反推出 G1 具有较好的最小度下界，而且这样删能够方便后续的计数。换句话说，这一步的作用就是把原问题约化到一个更适合后续构造和计数的情形。

Claim.

子图 G_1 的顶点数严格大于

\sqrt{\alpha(G)n/2},

从而在 n\ge N 时也有

|V(G_1)|>\sqrt{\alpha(G)N/2}.

Proof.

由 V_1 的选取方式可知

e(G_1)>\frac{\alpha-\alpha^2}{2}n^2.

又因为 \alpha\le \gamma<1/2，于是

\frac{\alpha-\alpha^2}{2}n^2=\frac{\alpha(1-\alpha)}{2}n^2>\frac{\alpha n^2}{4}=\frac{\alpha(G)n}{4}.

另一方面，G_1 是简单图，故 |V(G_1)|>\sqrt{\alpha(G)n/2}。 **Note.** (这里原文的细节没有写完整，我自己补充一下) 我们记 t=|V(G_1)|，由于G_1 是简单图，故

e(G_1)\le \binom{t}{2}<\frac{t^2}{2}.

假设

t\le \sqrt{\alpha(G)n/2},

那么就有

e(G_1)<\frac{1}{2}\cdot \frac{\alpha(G)n}{2}=\frac{\alpha(G)n}{4},

这与上面的下界矛盾。因此必有

|V(G_1)|>\sqrt{\alpha(G)n/2}.

再结合 n\ge N，立即得到

|V(G_1)|>\sqrt{\alpha(G)N/2}.

∎

(clm:minimal-subgraph-size) 中的下界，是把 1-\alpha 直接粗略估成了 1/2。虽然这一步对后面的证明没有影响，但如果我们保留原式中的 \alpha(1-\alpha)，可以直接得到更强的

|V(G_1)|>\sqrt{\alpha(G)(n-\alpha(G))}.

Claim.

图 G1 的最小度至少为 n1/4。此外，

e(G1)>\frac{n1^2+n1}{8}+\frac{\alpha1-\alpha1^2}{2}n1^2.

Proof.

由 V1 的最小性可知，对任意 v\in V1，删去 v 之后得到的图都不再满足定义 V_1 时所要求的边数条件，因此

e\bigl(G1[V1-v]\bigr)\le \frac{(n1-1)^2+n1-1}{8}+\frac{\alpha-\alpha^2}{2}n^2.

另一方面，

\deg{G1}(v)=e(G1)-e\bigl(G1[V_1-v]\bigr).

于是

\deg{G1}(v)\ge \left(\frac{n1^2+n1}{8}+\frac{\alpha-\alpha^2}{2}n^2\right) -\left(\frac{(n1-1)^2+n1-1}{8}+\frac{\alpha-\alpha^2}{2}n^2\right) =\frac{n_1}{4}.

由 v 的任意性，所以 G1 的最小度至少为 n1/4。

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

\alpha(G)n-\alpha(G)^2\ge \alpha(G1)n-\alpha(G1)^2,

Note.

(这里原文的细节没有写完整，我自己补充一下)

这里之所以“只需证明”这一点，是因为我们最终想要推出的是

e(G1)>\frac{n1^2+n1}{8}+\frac{\alpha1-\alpha1^2}{2}n1^2,

其中 \alpha1=\alpha(G1)/n1。而由 G1 的定义已经知道

e(G1)>\frac{n1^2+n_1}{8}+\frac{\alpha-\alpha^2}{2}n^2

并且

\frac{\alpha-\alpha^2}{2}n^2 = \frac{1}{2}\bigl(\alpha(G)n-\alpha(G)^2\bigr).

另一方面，

\frac{\alpha1-\alpha1^2}{2}n1^2 = \frac{1}{2}\bigl(\alpha(G1)n1-\alpha(G1)^2\bigr).

因此，我们只要证明

\alpha(G)n-\alpha(G)^2\ge \alpha(G1)n1-\alpha(G_1)^2,

因为由 n_1\le n 可知

\alpha(G1)n-\alpha(G1)^2\ge \alpha(G1)n1-\alpha(G_1)^2.

将前一个不等式除以 n^2，得到

\frac{\alpha(G)}{n}-\frac{\alpha(G)^2}{n^2} \ge \frac{\alpha(G1)}{n}-\frac{\alpha(G1)^2}{n^2}.

由于 \alpha(G_1)\le \alpha(G)<n/2，而函数 f(x)=x-x^2 在区间 (0,1/2) 上单调递增，因此上式成立。

∎

Remark 8.

在证明主定理时，我们不妨设 \alpha(G)\ge 2；否则 \alpha(G)=1，这时 G 是完全图，结论是平凡的。我们结合前面两个断言可知，我们所研究的问题到后面实际上只需考虑这样一类图：它们的顶点数满足

n\ge \sqrt{\alpha(G)N/2}\ge \sqrt{N} =\exp!\left(\frac{5\log(1/\nu)}{\nu}\right) =\exp(2500\log 500),

并且最小度至少为 n/4。

寻找一个大的拟随机二分对

Definition 1.

如果二部图 $F$ 的两部分是 $A,B$ ，并且对任意满足

|A'|\ge \varepsilon |A|, |B'|\ge \varepsilon |B|

的子集 $A'\subseteq A$ 、 $B'\subseteq B$ ，都有

\bigl|d_F(A,B)-d_F(A',B')\bigr|\le \varepsilon,

那么就称 $F$ 是一个 \keypart{ $\varepsilon$ -regular pair}。

Definition 2.

若二部图 $F$ 的两部分为 $A,B$ ，并且对任意满足

|A'|\ge \varepsilon |A|, |B'|\ge \varepsilon |B|

的子集 $A'\subseteq A$ 、 $B'\subseteq B$ ，都有

d_F(A',B')\ge \varepsilon,

则称 $F$ 是一个 \keypart{ $\varepsilon^+$ -regular pair}。

Claim.

若 $F=F(A,B)$ 是一个二部图，且 $1\le k\le |A|$ 、 $1\le m\le |B|$ ，则

d_F(A,B)=\frac{1}{\binom{|A|}{k}\binom{|B|}{m}} \sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} d_F(X,Y).

Note.

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

对所有满足 $|X|=k$ 、 $|Y|=m$ 的子集对 $(X,Y)$ ，我们考虑二部图 $F[X,Y]$ 中边的总数之和。固定一条边 $ab\in E(A,B)$ ，其中 $a\in A$ 、 $b\in B$ 。它恰好会在

\binom{|A|-1}{k-1}\binom{|B|-1}{m-1}

个子集对 $(X,Y)$ 中出现，因为我们需要在 $A\setminus\{a\}$ 中再选出 $k-1$ 个点，在 $B\setminus\{b\}$ 中再选出 $m-1$ 个点。因此

\sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} e_F(X,Y) = e_F(A,B)\binom{|A|-1}{k-1}\binom{|B|-1}{m-1}.

左右两边同时除以

\binom{|A|}{k}\binom{|B|}{m}\,km

又因为

\frac{\binom{|A|-1}{k-1}}{\binom{|A|}{k}}=\frac{k}{|A|}, \frac{\binom{|B|-1}{m-1}}{\binom{|B|}{m}}=\frac{m}{|B|},

就得到

\frac{1}{\binom{|A|}{k}\binom{|B|}{m}} \sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} \frac{e_F(X,Y)}{km} = \frac{e_F(A,B)}{|A||B|}.

这也就是我们所要证明的等式。

Lemma 1.

设 $F[A,B]$ 是一个二部图，其中 $|A|=a$ 、 $|B|=b$ ，并且 $A$ 中每个顶点在 $B$ 中至少有 $\delta b$ 个邻点。若 $0<\varepsilon\le \delta/6$ ，则 $F$ 含有一个 $\varepsilon^+$ -regular pair 子图 $F[X,Y]$ ，满足

|X|\ge \exp\!\left(-\frac{2\log(2/\varepsilon)\log(2/\delta)}{\varepsilon}\right)a, |Y|\ge (\delta-2\varepsilon)b,

并且对每个 $v\in X$ 都有

\deg(v,Y)\ge (\delta-2\varepsilon)b.

Proof.

我们构造两列集合

X_0,X_1,\dots,X_\ell, Y_0,Y_1,\dots,Y_\ell,

其中 $X_0=A$ 、 $Y_0=B$ ，并要求 $F[X_\ell,Y_\ell]$ 是一个 $\varepsilon^+$ -regular pair，而且对每个 $1\le i\le \ell$ ，都有

X_i\subset X_{i-1}, Y_i\subset Y_{i-1},

并满足

\varepsilon |X_{i-1}|/2\le |X_i|\le \varepsilon |X_{i-1}|

以及

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

这样最后只需取 $X=X_\ell$ 、 $Y=Y_\ell$ 即可。

我们通过一个迭代来构造这些集合：若在第 $i$ 步时 $F[X_i,Y_i]$ 已经是 $\varepsilon^+$ -regular pair，那么过程停止。另一个停止条件是：若对某个 $i$ 有

|Y_i|\le (\delta(1+\varepsilon/2)-2\varepsilon)b,

也停止。

Remark 9.

后面我们会说明，在这种情形下 $F[X_i,Y_i]$ 同样必然是一个 $\varepsilon^+$ -regular pair。

开始时先检查 $F[X_0,Y_0]$ 是否已经是 $\varepsilon^+$ -regular pair。若是，则停止。若不是，则存在 $S\subseteq X_0$ 、 $T\subseteq Y_0$ ，满足

|S|\ge \varepsilon |X_0|, |T|\ge \varepsilon |Y_0|,

并且

d_F(S,T)<\varepsilon.

令

k=\varepsilon |X_0|, m=\varepsilon |Y_0|,

于是， $S$ 的所有 $k$ 元子集与 $T$ 的所有 $m$ 元子集之间的平均密度小于 $\varepsilon$ 。

Note.

平均密度小于 $\varepsilon$ 是由 (clm:density-convexity)，

d_F(S,T)=\frac{1}{\binom{|S|}{k}\binom{|T|}{m}} \sum_{X\in\binom{S}{k},\,Y\in\binom{T}{m}} d_F(X,Y).

又因为 $d_F(S,T)<\varepsilon$ ，所以

\frac{1}{\binom{|S|}{k}\binom{|T|}{m}} \sum_{X\in\binom{S}{k},\,Y\in\binom{T}{m}} d_F(X,Y)<\varepsilon.

这就是说，在所有满足 $|X|=k$ 、 $|Y|=m$ 的子集对 $(X,Y)$ 中，密度 $d_F(X,Y)$ 的平均值小于 $\varepsilon$ 。因此必存在某一对子集 $X_1'\subseteq S$ 、 $Y_1'\subseteq T$ ，满足 $|X_1'|=k$ 、 $|Y_1'|=m$ ，并且

d_F(X_1',Y_1')<\varepsilon.

也就是：

e(F[X_1',Y_1'])<\varepsilon |X_1'||Y_1'|.

因此存在

X_1'\subseteq S, Y_1'\subseteq T

使得

|X_1'|=\varepsilon |X_0|, |Y_1'|=\varepsilon |Y_0|,

并且

e(F[X_1',Y_1'])<\varepsilon |X_1'||Y_1'|.

定义

X_1''=\{x\in X_1':\deg(x,Y_1')>2\varepsilon |Y_1'|\}.

我们可得

|X_1''|\le |X_1'|/2.

Note.

这里我们用简单的反证法即可说明。首先由 $X_1''$ 的定义我们有：

e(F[X_1',Y_1'])>|X_1''|\cdot2|Y_1'|.

若

|X_1''|> |X_1'|/2,

则

\varepsilon>\frac{e(F[X_1',Y_1'])}{|X_1'||Y_1'|}>\frac{|X_1''|\cdot2|Y_1'|}{2|X_1''|\cdot |Y_1'|}=\varepsilon.

矛盾！

令

X_1=X_1'-X_1'',

也就是说， $X_1$ 由 $X_1'$ 中那些在 $Y_1'$ 中至多有 $2\varepsilon |Y_1'|$ 个邻点的顶点组成。于是

|X_1'|/2\le |X_1|\le |X_1'|.

再令

Y_1=Y_0-Y_1'.

同时由 $X_1',Y_1'$ 的定义我们有

\varepsilon |X_0|/2\le |X_1|\le \varepsilon |X_0|, |Y_1|=(1-\varepsilon)|Y_0|.

对 $i\ge 2$ ，完全类似。若 $F[X_{i-1},Y_{i-1}]$ 不是 $\varepsilon^+$ -regular pair，我们的做法和前面相同，由 (clm:density-convexity) 可以找到

X_i'\subset X_{i-1}, Y_i'\subset Y_{i-1},

使得

|X_i'|=\varepsilon |X_{i-1}|, |Y_i'|=\varepsilon |Y_{i-1}|,

并且

e(F[X_i',Y_i'])<\varepsilon |X_i'||Y_i'|.

同样定义

X_i''=\{x\in X_i':\deg(x,Y_i')>2\varepsilon |Y_i'|\},

则有

|X_i''|\le |X_i'|/2.

接着令

X_i=X_i'-X_i'', Y_i=Y_{i-1}-Y_i'.

于是

|X_i'|/2\le |X_i|\le |X_i'|,

也就是

\varepsilon |X_{i-1}|/2\le |X_i|\le \varepsilon |X_{i-1}|, |Y_i|=(1-\varepsilon)|Y_{i-1}|.

这就证明了对每个 $i$ ，上面要求的关于 $|X_i|$ 与 $|Y_i|$ 的估计都成立。

接下来我们由 (clm:iterative-neighbor-bound)。若 $u\in X_\ell$ ，则它在

Y_1'\cup \cdots \cup Y_\ell'

中的邻点数至多为

2\varepsilon\bigl(|Y_1'|+\cdots+|Y_\ell'|\bigr).

因此

\deg(u,Y_\ell)\ge (\delta-2\varepsilon)b.

这同时也说明

|Y_\ell|\ge (\delta-2\varepsilon)b.

Remark 10.

下面说明，如果

(\delta-2\varepsilon)b\le |Y_\ell|\le (\delta(1+\varepsilon/2)-2\varepsilon)b,

那么 $F[X_\ell,Y_\ell]$ 必然是一个 $\varepsilon^+$ -regular pair。

我们任取 $u\in X_\ell$ ，则 $u$ 在 $Y_\ell$ 中的非邻点数至多为

|Y_l|-(\delta-2\varepsilon)b\le(\delta(1+\varepsilon/2)-2\varepsilon)b-(\delta-2\varepsilon)b=\delta\varepsilon b/2.

任取 $Y'\subset Y_\ell$ ，满足

|Y'|=\varepsilon |Y_\ell|.

则 $u$ 在 $Y'$ 中的邻点数至少为

\varepsilon |Y_\ell|-\delta\varepsilon b/2.

接下来，我们来验证

\varepsilon |Y_\ell|-\delta\varepsilon b/2\ge \varepsilon |Y'|=\varepsilon^2|Y_\ell|=\varepsilon|Y'|.

Remark 11.

如果我们需要验证的这个是成立的，那么对任意满足 $|Y'|=\varepsilon |Y_\ell|$ 的子集 $Y'\subset Y_\ell$ ，以及任意 $u\in X_\ell$ ，\keypart{它在 $Y'$ 中至少有 $\varepsilon |Y'|$ 个邻点。}于是对任意 $X'\subset X_\ell$ 、 $Y'\subset Y_\ell$ ，只要

|Y'|=\varepsilon |Y_\ell|,

就有

e(X',Y')\ge \varepsilon |X'||Y'|.

这就说明如果迭代过程是因为第二个停止条件而停止，那么最终得到的二分对一定是 $\varepsilon^+$ -regular 的。

我们要验证的等价于

|Y_\ell|(1-\varepsilon)\ge \delta b/2.

由于

|Y_\ell|\ge (\delta-2\varepsilon)b,

故我们只需证明

(\delta-2\varepsilon)(1-\varepsilon)\ge \delta/2.

而由 $\varepsilon\le \delta/6\le 1/6$ 可知

(\delta-2\varepsilon)(1-\varepsilon)\ge \frac{2\delta}{3}\cdot \frac56>\frac{\delta}{2}.

故成立。这就说明，如果迭代过程是因为第二个停止条件而停止，那么最终得到的二分对一定是 $\varepsilon^+$ -regular 的。

下面我们来估计迭代步数 \keypart{ $l$ } 。在每一次迭代中， $Y$ 一侧都缩小 $(1-\varepsilon)$ 倍。同时我们又知道

|Y_\ell|\ge (\delta-2\varepsilon)b.

因此

(1-\varepsilon)^\ell\ge (\delta-2\varepsilon)>\delta/2.

于是

\ell<\frac{\log(2/\delta)}{\log(1/(1-\varepsilon))}<\frac{\log(2/\delta)}{\varepsilon},

Note.

这里是由于

e^\varepsilon<\frac{1}{1-\varepsilon} (0<\varepsilon<1).

两边取对数就有

\log\left(\frac{1}{1-\varepsilon}\right)>\varepsilon

最后我们来估计 $|X_\ell|$ 。对每个 $i\ge 1$ ，都有

|X_i|/|X_{i-1}|\ge \varepsilon/2.

因此

|X_\ell|\ge \left(\frac{\varepsilon}{2}\right)^\ell a \ge \exp\!\left(-\frac{2\log(2/\varepsilon)\log(2/\delta)}{\varepsilon}\right)a.

这就完成了我们的证明。

(lem:large-regular-pair) 可以说是支撑这整个证明的最重要的一个引理。相比 (lem:large-regular-pair) ，我们引入了一个新参数进行推广，得到了一个更精细的下界，具体请见 (prop4.2)。

∎

Claim.

若 $i\ge 1$ 且 $u\in X_i$ ，那么 $u$ 在

Y_1'\cup Y_2'\cup \cdots \cup Y_i'

中的邻点数至多为

2\varepsilon\bigl(|Y_1'|+\cdots+|Y_i'|\bigr).

Note.

(这里原文没有证明，说是留给读者自己去证明，我自己补充一下)

对每个 $j\in \{1,\dots,i\}$ ，由于

X_j=X_j'-X_j'', X_j''=\{x\in X_j':\deg(x,Y_j')>2\varepsilon |Y_j'|\},

所以凡是属于 $X_j$ 的顶点 $u$ ，都满足

\deg(u,Y_j')\le 2\varepsilon |Y_j'|.

另一方面，由构造可知

X_i\subseteq X_{i-1}\subseteq \cdots \subseteq X_1,

因此若 $u\in X_i$ ，那么对每个 $1\le j\le i$ 都有 $u\in X_j$ ，从而

\deg(u,Y_j')\le 2\varepsilon |Y_j'|.

又因为

Y_j=Y_{j-1}-Y_j' (1\le j\le i),

所以各个集合 $Y_1',Y_2',\dots,Y_i'$ 两两不交。于是 $u$ 在并集

Y_1'\cup Y_2'\cup \cdots \cup Y_i'

中的邻点数就是它在这些集合中的邻点数之和，因此

\deg\bigl(u,Y_1'\cup Y_2'\cup \cdots \cup Y_i'\bigr) =\sum_{j=1}^i \deg(u,Y_j') \le \sum_{j=1}^i 2\varepsilon |Y_j'| =2\varepsilon\bigl(|Y_1'|+\cdots+|Y_i'|\bigr).

PDF

Download the original write-up here.

Part 2 of 5. ← Survey · Proof →

定义与主要工具

关于图

G 的最小度

我们从原图 G 中取一个最小子集 V1\subseteq V，令 G1=G[V1]，并记 n1=|V1|、\alpha1=\alpha(G1)/n1，其中 V_1 满足：

e(G1)>\frac{|V1|^2+|V_1|}{8}+\frac{\alpha-\alpha^2}{2}n^2,

Remark 7.

我觉得这一步是整篇论文最关键的地方。

主定理中的条件是：

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

Claim.

子图 G_1 的顶点数严格大于

\sqrt{\alpha(G)n/2},

从而在 n\ge N 时也有

|V(G_1)|>\sqrt{\alpha(G)N/2}.

Proof.

由 V_1 的选取方式可知

e(G_1)>\frac{\alpha-\alpha^2}{2}n^2.

又因为 \alpha\le \gamma<1/2，于是

\frac{\alpha-\alpha^2}{2}n^2=\frac{\alpha(1-\alpha)}{2}n^2>\frac{\alpha n^2}{4}=\frac{\alpha(G)n}{4}.

另一方面，G_1 是简单图，故 |V(G_1)|>\sqrt{\alpha(G)n/2}。 **Note.** (这里原文的细节没有写完整，我自己补充一下) 我们记 t=|V(G_1)|，由于G_1 是简单图，故

e(G_1)\le \binom{t}{2}<\frac{t^2}{2}.

假设

t\le \sqrt{\alpha(G)n/2},

那么就有

e(G_1)<\frac{1}{2}\cdot \frac{\alpha(G)n}{2}=\frac{\alpha(G)n}{4},

这与上面的下界矛盾。因此必有

|V(G_1)|>\sqrt{\alpha(G)n/2}.

再结合 n\ge N，立即得到

|V(G_1)|>\sqrt{\alpha(G)N/2}.

∎

|V(G_1)|>\sqrt{\alpha(G)(n-\alpha(G))}.

Claim.

图 G1 的最小度至少为 n1/4。此外，

e(G1)>\frac{n1^2+n1}{8}+\frac{\alpha1-\alpha1^2}{2}n1^2.

Proof.

由 V1 的最小性可知，对任意 v\in V1，删去 v 之后得到的图都不再满足定义 V_1 时所要求的边数条件，因此

e\bigl(G1[V1-v]\bigr)\le \frac{(n1-1)^2+n1-1}{8}+\frac{\alpha-\alpha^2}{2}n^2.

另一方面，

\deg{G1}(v)=e(G1)-e\bigl(G1[V_1-v]\bigr).

于是

\deg{G1}(v)\ge \left(\frac{n1^2+n1}{8}+\frac{\alpha-\alpha^2}{2}n^2\right) -\left(\frac{(n1-1)^2+n1-1}{8}+\frac{\alpha-\alpha^2}{2}n^2\right) =\frac{n_1}{4}.

由 v 的任意性，所以 G1 的最小度至少为 n1/4。

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

\alpha(G)n-\alpha(G)^2\ge \alpha(G1)n-\alpha(G1)^2,

Note.

(这里原文的细节没有写完整，我自己补充一下)

这里之所以“只需证明”这一点，是因为我们最终想要推出的是

e(G1)>\frac{n1^2+n1}{8}+\frac{\alpha1-\alpha1^2}{2}n1^2,

其中 \alpha1=\alpha(G1)/n1。而由 G1 的定义已经知道

e(G1)>\frac{n1^2+n_1}{8}+\frac{\alpha-\alpha^2}{2}n^2

并且

\frac{\alpha-\alpha^2}{2}n^2 = \frac{1}{2}\bigl(\alpha(G)n-\alpha(G)^2\bigr).

另一方面，

\frac{\alpha1-\alpha1^2}{2}n1^2 = \frac{1}{2}\bigl(\alpha(G1)n1-\alpha(G1)^2\bigr).

因此，我们只要证明

\alpha(G)n-\alpha(G)^2\ge \alpha(G1)n1-\alpha(G_1)^2,

因为由 n_1\le n 可知

\alpha(G1)n-\alpha(G1)^2\ge \alpha(G1)n1-\alpha(G_1)^2.

将前一个不等式除以 n^2，得到

\frac{\alpha(G)}{n}-\frac{\alpha(G)^2}{n^2} \ge \frac{\alpha(G1)}{n}-\frac{\alpha(G1)^2}{n^2}.

由于 \alpha(G_1)\le \alpha(G)<n/2，而函数 f(x)=x-x^2 在区间 (0,1/2) 上单调递增，因此上式成立。

∎

Remark 8.

n\ge \sqrt{\alpha(G)N/2}\ge \sqrt{N} =\exp!\left(\frac{5\log(1/\nu)}{\nu}\right) =\exp(2500\log 500),

并且最小度至少为 n/4。

寻找一个大的拟随机二分对

Definition 1.

如果二部图 $F$ 的两部分是 $A,B$ ，并且对任意满足

|A'|\ge \varepsilon |A|, |B'|\ge \varepsilon |B|

的子集 $A'\subseteq A$ 、 $B'\subseteq B$ ，都有

\bigl|d_F(A,B)-d_F(A',B')\bigr|\le \varepsilon,

那么就称 $F$ 是一个 \keypart{ $\varepsilon$ -regular pair}。

Definition 2.

若二部图 $F$ 的两部分为 $A,B$ ，并且对任意满足

|A'|\ge \varepsilon |A|, |B'|\ge \varepsilon |B|

的子集 $A'\subseteq A$ 、 $B'\subseteq B$ ，都有

d_F(A',B')\ge \varepsilon,

则称 $F$ 是一个 \keypart{ $\varepsilon^+$ -regular pair}。

Claim.

若 $F=F(A,B)$ 是一个二部图，且 $1\le k\le |A|$ 、 $1\le m\le |B|$ ，则

d_F(A,B)=\frac{1}{\binom{|A|}{k}\binom{|B|}{m}} \sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} d_F(X,Y).

Note.

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

对所有满足 $|X|=k$ 、 $|Y|=m$ 的子集对 $(X,Y)$ ，我们考虑二部图 $F[X,Y]$ 中边的总数之和。固定一条边 $ab\in E(A,B)$ ，其中 $a\in A$ 、 $b\in B$ 。它恰好会在

\binom{|A|-1}{k-1}\binom{|B|-1}{m-1}

个子集对 $(X,Y)$ 中出现，因为我们需要在 $A\setminus\{a\}$ 中再选出 $k-1$ 个点，在 $B\setminus\{b\}$ 中再选出 $m-1$ 个点。因此

\sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} e_F(X,Y) = e_F(A,B)\binom{|A|-1}{k-1}\binom{|B|-1}{m-1}.

左右两边同时除以

\binom{|A|}{k}\binom{|B|}{m}\,km

又因为

\frac{\binom{|A|-1}{k-1}}{\binom{|A|}{k}}=\frac{k}{|A|}, \frac{\binom{|B|-1}{m-1}}{\binom{|B|}{m}}=\frac{m}{|B|},

就得到

\frac{1}{\binom{|A|}{k}\binom{|B|}{m}} \sum_{X\in\binom{A}{k},\,Y\in\binom{B}{m}} \frac{e_F(X,Y)}{km} = \frac{e_F(A,B)}{|A||B|}.

这也就是我们所要证明的等式。

Lemma 1.

|X|\ge \exp\!\left(-\frac{2\log(2/\varepsilon)\log(2/\delta)}{\varepsilon}\right)a, |Y|\ge (\delta-2\varepsilon)b,

并且对每个 $v\in X$ 都有

\deg(v,Y)\ge (\delta-2\varepsilon)b.

Proof.

我们构造两列集合

X_0,X_1,\dots,X_\ell, Y_0,Y_1,\dots,Y_\ell,

其中 $X_0=A$ 、 $Y_0=B$ ，并要求 $F[X_\ell,Y_\ell]$ 是一个 $\varepsilon^+$ -regular pair，而且对每个 $1\le i\le \ell$ ，都有

X_i\subset X_{i-1}, Y_i\subset Y_{i-1},

并满足

\varepsilon |X_{i-1}|/2\le |X_i|\le \varepsilon |X_{i-1}|

以及

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

这样最后只需取 $X=X_\ell$ 、 $Y=Y_\ell$ 即可。

我们通过一个迭代来构造这些集合：若在第 $i$ 步时 $F[X_i,Y_i]$ 已经是 $\varepsilon^+$ -regular pair，那么过程停止。另一个停止条件是：若对某个 $i$ 有

|Y_i|\le (\delta(1+\varepsilon/2)-2\varepsilon)b,

也停止。

Remark 9.

后面我们会说明，在这种情形下 $F[X_i,Y_i]$ 同样必然是一个 $\varepsilon^+$ -regular pair。

开始时先检查 $F[X_0,Y_0]$ 是否已经是 $\varepsilon^+$ -regular pair。若是，则停止。若不是，则存在 $S\subseteq X_0$ 、 $T\subseteq Y_0$ ，满足

|S|\ge \varepsilon |X_0|, |T|\ge \varepsilon |Y_0|,

并且

d_F(S,T)<\varepsilon.

令

k=\varepsilon |X_0|, m=\varepsilon |Y_0|,

于是， $S$ 的所有 $k$ 元子集与 $T$ 的所有 $m$ 元子集之间的平均密度小于 $\varepsilon$ 。

Note.

平均密度小于 $\varepsilon$ 是由 (clm:density-convexity)，

d_F(S,T)=\frac{1}{\binom{|S|}{k}\binom{|T|}{m}} \sum_{X\in\binom{S}{k},\,Y\in\binom{T}{m}} d_F(X,Y).

又因为 $d_F(S,T)<\varepsilon$ ，所以

\frac{1}{\binom{|S|}{k}\binom{|T|}{m}} \sum_{X\in\binom{S}{k},\,Y\in\binom{T}{m}} d_F(X,Y)<\varepsilon.

d_F(X_1',Y_1')<\varepsilon.

也就是：

e(F[X_1',Y_1'])<\varepsilon |X_1'||Y_1'|.

因此存在

X_1'\subseteq S, Y_1'\subseteq T

使得

|X_1'|=\varepsilon |X_0|, |Y_1'|=\varepsilon |Y_0|,

并且

e(F[X_1',Y_1'])<\varepsilon |X_1'||Y_1'|.

定义

X_1''=\{x\in X_1':\deg(x,Y_1')>2\varepsilon |Y_1'|\}.

我们可得

|X_1''|\le |X_1'|/2.

Note.

这里我们用简单的反证法即可说明。首先由 $X_1''$ 的定义我们有：

e(F[X_1',Y_1'])>|X_1''|\cdot2|Y_1'|.

若

|X_1''|> |X_1'|/2,

则

\varepsilon>\frac{e(F[X_1',Y_1'])}{|X_1'||Y_1'|}>\frac{|X_1''|\cdot2|Y_1'|}{2|X_1''|\cdot |Y_1'|}=\varepsilon.

矛盾！

令

X_1=X_1'-X_1'',

也就是说， $X_1$ 由 $X_1'$ 中那些在 $Y_1'$ 中至多有 $2\varepsilon |Y_1'|$ 个邻点的顶点组成。于是

|X_1'|/2\le |X_1|\le |X_1'|.

再令

Y_1=Y_0-Y_1'.

同时由 $X_1',Y_1'$ 的定义我们有

\varepsilon |X_0|/2\le |X_1|\le \varepsilon |X_0|, |Y_1|=(1-\varepsilon)|Y_0|.

对 $i\ge 2$ ，完全类似。若 $F[X_{i-1},Y_{i-1}]$ 不是 $\varepsilon^+$ -regular pair，我们的做法和前面相同，由 (clm:density-convexity) 可以找到

X_i'\subset X_{i-1}, Y_i'\subset Y_{i-1},

使得

|X_i'|=\varepsilon |X_{i-1}|, |Y_i'|=\varepsilon |Y_{i-1}|,

并且

e(F[X_i',Y_i'])<\varepsilon |X_i'||Y_i'|.

同样定义

X_i''=\{x\in X_i':\deg(x,Y_i')>2\varepsilon |Y_i'|\},

则有

|X_i''|\le |X_i'|/2.

接着令

X_i=X_i'-X_i'', Y_i=Y_{i-1}-Y_i'.

于是

|X_i'|/2\le |X_i|\le |X_i'|,

也就是

\varepsilon |X_{i-1}|/2\le |X_i|\le \varepsilon |X_{i-1}|, |Y_i|=(1-\varepsilon)|Y_{i-1}|.

这就证明了对每个 $i$ ，上面要求的关于 $|X_i|$ 与 $|Y_i|$ 的估计都成立。

接下来我们由 (clm:iterative-neighbor-bound)。若 $u\in X_\ell$ ，则它在

Y_1'\cup \cdots \cup Y_\ell'

中的邻点数至多为

2\varepsilon\bigl(|Y_1'|+\cdots+|Y_\ell'|\bigr).

因此

\deg(u,Y_\ell)\ge (\delta-2\varepsilon)b.

这同时也说明

|Y_\ell|\ge (\delta-2\varepsilon)b.

Remark 10.

下面说明，如果

(\delta-2\varepsilon)b\le |Y_\ell|\le (\delta(1+\varepsilon/2)-2\varepsilon)b,

那么 $F[X_\ell,Y_\ell]$ 必然是一个 $\varepsilon^+$ -regular pair。

我们任取 $u\in X_\ell$ ，则 $u$ 在 $Y_\ell$ 中的非邻点数至多为

|Y_l|-(\delta-2\varepsilon)b\le(\delta(1+\varepsilon/2)-2\varepsilon)b-(\delta-2\varepsilon)b=\delta\varepsilon b/2.

任取 $Y'\subset Y_\ell$ ，满足

|Y'|=\varepsilon |Y_\ell|.

则 $u$ 在 $Y'$ 中的邻点数至少为

\varepsilon |Y_\ell|-\delta\varepsilon b/2.

接下来，我们来验证

\varepsilon |Y_\ell|-\delta\varepsilon b/2\ge \varepsilon |Y'|=\varepsilon^2|Y_\ell|=\varepsilon|Y'|.

Remark 11.

|Y'|=\varepsilon |Y_\ell|,

就有

e(X',Y')\ge \varepsilon |X'||Y'|.

这就说明如果迭代过程是因为第二个停止条件而停止，那么最终得到的二分对一定是 $\varepsilon^+$ -regular 的。

我们要验证的等价于

|Y_\ell|(1-\varepsilon)\ge \delta b/2.

由于

|Y_\ell|\ge (\delta-2\varepsilon)b,

故我们只需证明

(\delta-2\varepsilon)(1-\varepsilon)\ge \delta/2.

而由 $\varepsilon\le \delta/6\le 1/6$ 可知

(\delta-2\varepsilon)(1-\varepsilon)\ge \frac{2\delta}{3}\cdot \frac56>\frac{\delta}{2}.

故成立。这就说明，如果迭代过程是因为第二个停止条件而停止，那么最终得到的二分对一定是 $\varepsilon^+$ -regular 的。

下面我们来估计迭代步数 \keypart{ $l$ } 。在每一次迭代中， $Y$ 一侧都缩小 $(1-\varepsilon)$ 倍。同时我们又知道

|Y_\ell|\ge (\delta-2\varepsilon)b.

因此

(1-\varepsilon)^\ell\ge (\delta-2\varepsilon)>\delta/2.

于是

\ell<\frac{\log(2/\delta)}{\log(1/(1-\varepsilon))}<\frac{\log(2/\delta)}{\varepsilon},

Note.

这里是由于

e^\varepsilon<\frac{1}{1-\varepsilon} (0<\varepsilon<1).

两边取对数就有

\log\left(\frac{1}{1-\varepsilon}\right)>\varepsilon

最后我们来估计 $|X_\ell|$ 。对每个 $i\ge 1$ ，都有

|X_i|/|X_{i-1}|\ge \varepsilon/2.

因此

|X_\ell|\ge \left(\frac{\varepsilon}{2}\right)^\ell a \ge \exp\!\left(-\frac{2\log(2/\varepsilon)\log(2/\delta)}{\varepsilon}\right)a.

这就完成了我们的证明。

∎

Claim.

若 $i\ge 1$ 且 $u\in X_i$ ，那么 $u$ 在

Y_1'\cup Y_2'\cup \cdots \cup Y_i'

中的邻点数至多为

2\varepsilon\bigl(|Y_1'|+\cdots+|Y_i'|\bigr).

Note.

(这里原文没有证明，说是留给读者自己去证明，我自己补充一下)

对每个 $j\in \{1,\dots,i\}$ ，由于

X_j=X_j'-X_j'', X_j''=\{x\in X_j':\deg(x,Y_j')>2\varepsilon |Y_j'|\},

所以凡是属于 $X_j$ 的顶点 $u$ ，都满足

\deg(u,Y_j')\le 2\varepsilon |Y_j'|.

另一方面，由构造可知

X_i\subseteq X_{i-1}\subseteq \cdots \subseteq X_1,

因此若 $u\in X_i$ ，那么对每个 $1\le j\le i$ 都有 $u\in X_j$ ，从而

\deg(u,Y_j')\le 2\varepsilon |Y_j'|.

又因为

Y_j=Y_{j-1}-Y_j' (1\le j\le i),

所以各个集合 $Y_1',Y_2',\dots,Y_i'$ 两两不交。于是 $u$ 在并集

Y_1'\cup Y_2'\cup \cdots \cup Y_i'

中的邻点数就是它在这些集合中的邻点数之和，因此

\deg\bigl(u,Y_1'\cup Y_2'\cup \cdots \cup Y_i'\bigr) =\sum_{j=1}^i \deg(u,Y_j') \le \sum_{j=1}^i 2\varepsilon |Y_j'| =2\varepsilon\bigl(|Y_1'|+\cdots+|Y_i'|\bigr).

PDF

Download the original write-up here.

K₄ Ramsey–Turán II — Tools

Search

K₄ Ramsey–Turán II — Tools

定义与主要工具

关于图

寻找一个大的拟随机二分对

PDF

定义与主要工具

关于图

寻找一个大的拟随机二分对

PDF