6. 导出子图的删除引理

我们现在将考虑不同版本的图删除引理. 我们现在考虑 $H$ 的导出子图的副本, 而不是 $H$ 的副本. 说明一下, 如果可以通过删除 $G$ 的顶点获得 $H$, 我们说 $H$ 是 $G$ 的导出子图. 如果 $G$ 不包含与 $H$ 同构的导出子图, 则 $G$ 是 $\text{induced}-H-\text{free}$ 的.

定理 6.1 (导出子图的删除引理). 对于任意图 $H$ 和常数 $ϵ>0$, 存在一个常数 $\delta >0$ 使得如果 $n$ 顶点图的 $H$ 副本数少于 $\delta n^{v(H)}$ , 则可以通过添加或删除少于 $ϵn^2$ 条边变成 $\text{induced}-H-\text{free}$.

我们首先尝试使用图删除引理证明中的策略 (定理 5.0.5) .

划分. 使用 Szemerédi 正则性引理对顶点集正则划分.

清除. 删除边密度低的对 (边密度小于 $ϵ$ ) 之间的所有边, 并添加边密度高的对 (边密度大于 $1-ϵ$ ) 之间的所有边. 但是, 我们不清楚如何处理非正则对. 之前, 我们只是删除了非正则对之间的所有边. 问题是这可能会创建许多以前并不存在的 $H$ 导出副本 (请注意, 这对于一般的子图而言并非如此) , 并且在这种情况下, 没有希望表明在计数过程中没有 (或只有非常少的) $H$ 副本. 如果我们要在非正则对之间添加所有边, 情况也是如此.

这就提出了一个问题, 是否有一种方法可以保证划分没有非正则对. 答案是否定的, 可以看出半图 $H_n$ 就无法做到这一点. 半图 $H_n$ 是顶点集为 $\left\{a_1,\dots ,a_n,b_1,\dots ,b_n\right\}$ 上的二部图, 边的集合为 $\left\{a_i{b}_j:i\le j\right\}$.

我们的策略是证明存在另一种很好的划分, 即另一个正则性引理. 首先我们注意到, 导出子图的删除引理是下面定理的一个特例.

定理 6.2 (染色图删除引理). 对于所有正整数 $k,r$ 和常数 $ϵ>0$, 存在一个常数 $\delta >0$, 如果 $\mathcal{H}$ 是 $K_k$ 的一组色数为 $r$ 的边着色方案, 则任意一组 $K_n$ 的色数为 $r$ 的边着色 (该着色方案的所有 $k$ 顶点子图的着色方案有 $\delta$ 占比包含于 $\mathcal{H}$) , 可以通过对 $m$ 条边进行的重新 $r$-着色变成 $\mathcal{H}-\text{free}$ . 其中, $m$ 小于 $ϵ$ 乘以边的总数.

要说明的是, 导出子图的删除引理是 $r=2$ 的特殊情况. $K_k$ 的边红蓝着色, 蓝色边形成的图与 $H$ 同构, 红色边形成的图是它的补图. 我们不会证明染色图的删除引理, 但我们将证明导出子图的删除引理, 并且染色图的删除引理的证明思路与之类似.

为了证明导出子图的删除引理, 我们将用到一个新的正则性引理. 回想一下, 对于 $V(G)$ 的划分 $\mathcal{P}=\left\{V_1,\dots ,V_k\right\}$, 其中 $n=|V(G)|$, 我们定义了能量

$$q(\mathcal{P})=\sum _{i,j=1}^n\frac{\left|V_i\right|\left|V_j\right|}{n^2}d{\left(V_i,V_j\right)}^2$$

在 Szemerédi 的正则性引理 (定理 1.1.5) 的证明中, 我们从能量递增的角度入手, 即如果 $\mathcal{P}$ 不是 $ϵ$ -正则的, 那么存在一个 $\mathcal{P}$ 的加细 $\mathcal{Q}$, 使得 $|\mathcal{Q}|\le |\mathcal{P}|2^{|\mathcal{P}|}$ 且 $q(\mathcal{Q})\ge q(\mathcal{P})+{ϵ}^5$. 新的正则引理如下.

定理 6.3 (强正则性定理).

对于任意的常数序列 ${ϵ}_0\ge {ϵ}_1\ge {ϵ}_2\dots >0$, 存在一个整数 $M$, 使得每个图都有两个顶点的划分 $\mathcal{P},\mathcal{Q}$ 满足:

•	$\mathcal{Q}$ 是 $\mathcal{P}$ 的加细,
•	$|\mathcal{Q}|\le M$,
•	$\mathcal{P}$ 是 ${ϵ}_0$ -正则的,
•	$\mathcal{Q}$ 是 ${ϵ}_{|\mathcal{P}|}$ -正则的,
•	$q(\mathcal{Q})\le q(\mathcal{P})+{ϵ}_0$ .

证明.

我们反复应用下面版本的 Szemerédi 正则引理 (定理 1.1.5) :

对于任意 $ϵ>0$, 存在一个整数 $M_0=M_0(ϵ)$ 使得对于 $V(G)$ 的任意划分 $\mathcal{P}$, 存在 $\mathcal{P}$ 的加细 ${\mathcal{P}}^{\prime }$ 将 $\mathcal{P}$ 中的每个部分加细为 $\le M_0$ 个块, 使得 ${\mathcal{P}}^{\prime }$ 是 $ϵ$ -正则的.

上述版本的证明与我们定理 1.1.5 给出的证明基本完全相同, 除了不是从平凡划分开始而是从划分 $\mathcal{P}$ 开始.

通过迭代应用上述引理, 我们获得了 $V(G)$ 的一系列划分 ${\mathcal{P}}_0,{\mathcal{P}}_1,\dots$ . 其中, ${\mathcal{P}}_0$ 是一个平凡的划分. 由定理知, 每个 ${\mathcal{P}}_{i+1}$ 是 ${\mathcal{P}}_i$ 的加细, ${\mathcal{P}}_{i+1}$ 是 ${ϵ}_{|{\mathcal{P}}_i|}$ -正则的, 而 $\left|{\mathcal{P}}_{i+1}\right|\le \left|{\mathcal{P}}_i\right|M_0\left({ϵ}_{|{\mathcal{P}}_i|}\right)$.

由于 $0\le q(i)\le 1$, 存在 $i\le {ϵ}_0^{-1}$ 使得 $q\left({\mathcal{P}}_{i+1}\right)\le q\left({\mathcal{P}}_i\right)+{ϵ}_0$. 令 $\mathcal{P}={\mathcal{P}}_i,Q={\mathcal{P}}_{i+1}$. 因为我们最多迭代 ${ϵ}_0^{-1}$ 次, 每次加细增加有限数量个部分 (仅取决于相应的 ${ϵ}_{|{\mathcal{P}}_i|}$) , 我们有 $|\mathcal{Q}|=O_{\overrightarrow{ϵ}}(1)$.

$\square$

这个证明给出的常数 $M$ 的界是什么? $M$ 取决于序列 ${ϵ}_i$. 例如, 如果 ${ϵ}_i=\frac{ϵ}{i+1}$, 则 $M$ 本质上是 $M_0$ 连续迭代 $\frac{1}{ϵ}$ 次. 注意, $M_0$ 是一个塔函数 ¹, 所以 $M$ 是迭代 $i$ 次的塔函数 $\text{Tower}(\text{Tower}(\text{Tower}(\cdots )))$. 我们把这个迭代的塔函数称为 wowzer 函数.

事实上, 我们可以进一步保证 $\mathcal{P}$ 和 $\mathcal{Q}$ 的划分是均衡的, 其证明思路与定理 1.1.6 相同.

接下来, 我们给出如下形式的强正则性引理, 它将帮助我们证明导出子图的删除引理.

推论 6.4. 对于任意常数序列 ${ϵ}_0\ge {ϵ}_1\ge {ϵ}_2\dots >0$, 存在一个常数 $\delta >0$ 使得每个 $n$ 顶点图有一个均衡的顶点划分 $V_1,\dots ,V_k$ 和 $W_i\subset V_i$ 使得

1.	$\left|W_i\right|\ge \delta n$
2.	对于所有 $1\le i\le j\le k$, $\left(W_i,W_j\right)$ 是 ${ϵ}_k$ -正则对
3.	对于所有的 $(i,j)\in [k{]}^2$, $\left|d\left(V_i,V_j\right)-d\left(W_i,W_j\right)\right|\le {ϵ}_0$ 成立的次数少于 ${ϵ}_0{k}^2$

[H](...) 具有正则子集的顶点划分

概要.

让我们首先解释如何获得几乎满足 (b) 的划分. 请注意, 在不要求 $\left(W_i,W_i\right)$ 是正则的情况下, 我们可以通过在均衡强正则引理中 $\mathcal{P}$ 的每个块中均匀随机选取 $Q$ 的块来得到 $W_i\subseteq V_i$. 因为 $\mathcal{Q}$ 是强正则的, 所以 $i\ne j$ 的所有 $\left(W_i,W_j\right)$ 都是正则的概率很高. 更进一步, 我们也可以使得每个 $\left(W_i,W_i\right)$ 都是正则的, 细节留给读者.

通过这种构造, (c) 可由 $q(\mathcal{Q})\le q(\mathcal{P})+$ ${ϵ}_0$ 推导出. 回想一下引理 1.1.8 的证明, 能量 $q$ 是随机变量 $Z$ 的平方的期望. 对于随机的 $i,j$, $Z_{\mathcal{P}}=d\left(V_i,V_j\right)$ . 所以 $q(\mathcal{Q})-q(\mathcal{P})=\mathbb{E}\left[Z_{\mathcal{Q}}^2\right]-\mathbb{E}\left[Z_{\mathcal{P}}^2\right]=\mathbb{E}\left[{\left(Z_{\mathcal{Q}}-Z_{\mathcal{P}}\right)}^2\right]$, 其中最后一个等号是通过等式 $\mathbb{E}\left[{\left(X-\mu \right)}^2\right]=\mathbb{E}\left[X^2\right]-{\mu }^2$ 得到的, 下面我们会详细说明. 为了证明最后一个等号, 我们将期望扩展为 $\mathcal{P}$ 的所有对的总和. 在每一对上, $Z_{\mathcal{P}}$ 是常数, 而 $Z_{\mathcal{Q}}$ 是它的平均值, 因此每一对和总和都遵循等式. 然后将随机变量重新解释为边密度便得到 (c) .

最后, 注意到 $|\mathcal{Q}|\le M$ , 又因为划分是均衡的, 所以存在 $\delta$ 满足 (a).

$\square$

我们现在将使用推论 6.4 证明导出子图的删除引理.

定理 6.1. 我们将分 $3$ 步进行.

1.	划分 我们应用推论得到一个划分 $V_1\cup \dots \cup V_k$ 和 $W_1\subset V_1,\dots ,W_k\subset V_k$, 使得下面的内容成立: ∘ 对于所有 $i\le j$ , $\left(W_i,W_j\right)$ 是 $\frac{1}{(v(H))}{\left(\frac{ϵ}{4}\right)}^{\left(\genfrac{}{}{0ex}{}{(v(H)}{2}\right)}$-正则的 ∘ 对于所有的 $(i,j)\in [k{]}^2$, $\left|d\left(V_i,V_j\right)-d\left(W_i,W_j\right)\right|\le \frac{ϵ}{2}$ 成立的对数小于 $\frac{ϵk^2}{2}$ ∘ $\left|W_i\right|\ge {\delta }_{0}n$, 其中 ${\delta }_0={\delta }_0(ϵ,H)>0$
2.	删除 对于所有 $i\le j$ (包括 $i=j$ ) : ∘ 如果 $d\left(W_i,W_j\right)\le \frac{ϵ}{2}$, 我们移除 $\left(V_i,V_j\right)$ 之间的所有边. ∘ 如果 $d\left(W_i,W_j\right)\ge 1-\frac{ϵ}{2}$, 那么我们添加 $\left(V_i,V_j\right)$ 之间的所有边. 根据构造, 从 $G$ 添加/删除的边总数小于 $2ϵn^2$ .
3.	计数 我们只需证明完成删除步骤后 $G$ 中没有导出子图 $H$ 的副本. 假设有导出子图 $H$ 的副本. 令 $\varphi :V(H)\to [k]$ 是 $H$ 副本的每个顶点所在的块的函数. 换句话说, 对于 $H$ 的副本, 顶点 $v\in V(H)$ 位于 $V_{\varphi (v)}$ 中. 现在的目标是应用计数引理来证明实际上在 $G$ 中有很多 $H$ 的副本, 其中 $v\in V(H)$ 映射到 $W_{\varphi (v)}$ 中的一个顶点. 我们将使用以下技巧: 修改 $G$ 得到图 $G^{\prime }$. 对于该图 $G^{\prime }$, 当且仅当在 $G$ 上出现导出子图 $H$ 的副本时, 存在 $V(H)$ 顶点上的完全图, 该完全图的顶点来自 $\varphi$ 给出的块. 我们以如下方式构造 $G^{\prime }$. $H$ 中同一顶点的两个拷贝之间的边将永远不会出现在 $G^{\prime }$. 对于 $G^{\prime }$ 中的所有其他顶点对, 它们之间是否存在边由以下方式确定: 如果 $uv$ 是边, 则 $G^{\prime }$ 中的 $V_{\varphi (v)}$ 和 $V_{\varphi (u)}$ 之间的边与 $G$ 中的相同. 如果 $uv$ 不是边, 则 $G^{\prime }$ 中的 $V_{\varphi (v)}$ 和 $V_{\varphi (u)}$ 之间的边与 $G$ 的补图中的相同. 请注意, 此 $G^{\prime }$ 确实满足所需的属性——如果 $G^{\prime }$ 在这些块 $V_{\varphi (v)}$ 的顶点上存在完全子图, 则 $G$ 在相同的顶点上有一个导出子图 $H$ . 现在通过图计数引理 (定理 5.0.3) , $K_{v(H)}$ (每一个 $u\in V(H)$ 来自 $W_{\varphi (u)}$) 的数量大约为$$\prod _{uv\in E(H)}d\left(W_{\varphi (u)},W_{\varphi (v)}\right)\prod _{uv\in E(\bar{H})}\left(1-d\left(W_{\varphi (u)},W_{\varphi (v)}\right)\right)\prod _{u\in V(H)}\left|W_{\varphi (u)}\right|$$误差最大不超过$${\left(\frac{ϵ}{4}\right)}^{\left(\genfrac{}{}{0ex}{}{v(H)}{2}\right)}\prod _{u\in V(H)}\left|W_{\varphi (u)}\right|$$因此, 在 $G$ 中导出子图 $H$ 的数量至少是 $$\left({\left(\frac{ϵ}{2}\right)}^{\left(\genfrac{}{}{0ex}{}{v(H)}{2}\right)}-{\left(\frac{ϵ}{4}\right)}^{\left(\genfrac{}{}{0ex}{}{v(H)}{2}\right)}\right){\delta }_0^{v(H)}{n}^{v(H)}$$矛盾. 所以删除边之后的图不存在导出子图 $H$ 的副本.

$\square$

值得一提的是, 强正则性引理很有用, 因为它允许我们在有限的意义上摆脱非正则划分的限制.

定理 6.5 (无限版本删除引理 Alon and Shapira 2008 ). 对于任意 (可能是无限的) 图 $\mathcal{H}$ 和 $ϵ>0$, 都存在 $h_0$ 和 $\delta >0$, 使得对于任意 $n$ 顶点图, 如果它的 $H$ 副本数少于 $\delta n^{v(H)}$ (其中 $H\in \mathcal{H}$ 且 $v(H)\le h_0$) , 则可以通过添加或删除少于 $ϵn^2$ 条边变成 $\text{induced}-H-\text{free}$.

该定理的的证明与导出子图的删除引理的证明类似.