8. 超图的删除引理

对于图的每一个有趣的结论, 一个自然的问题就是如何推广到超图上. 我们现在介绍定理 5.0.5 的扩展版本, 超图删除引理. 回想一下 $r-\text{uniform}$ 超图, 简称 $r$-图 ( $r$-graph) , 是一对 $(V,E)$, 其中 $E\subset \left(\genfrac{}{}{0ex}{}{V}{r}\right)$, 即边是 $V$ 中 $r$ 个元素构成的的子集.

定理 8.1 (超图删除引理 Rödl et al. 2005 , Gowers 2007). 对于任意的 $r$ - 图 $H$ 和任意的 $ϵ>0$, 存在 $\delta >0$ 使得, 如果 $n$ 顶点图 $G$ 中 $H$ 的副本数少于 $\delta n^{V(H)}$ , 则可以通过从 $G$ 中删除少于 $ϵn^r$ 条边来使 $G$ 变成 $H-\text{free}$.

为什么我们关注这个引理? 回想一下, 我们从三角形删除引理的推论中推导出了 Roth 定理 (定理 3.0.1) , 即每一条边恰好位于一个三角形的图都有 $o\left(n^2\right)$ 条边. 我们可以在这里做相同的操作, 使用定理 8.1 来证明 Roth 定理的推广版本, 即 Szemerédi 定理 (定理 2.4) . 该定理告诉我们, 对于固定的 $k$, 如果 $A\subset [N]$ 是 $k-AP-\text{free}$ 的, 则 $|A|=o(N)$.

你可能会问: 我们能否对普通的图做同样的事情吗? 事实上, 我们不能这样做! 原因在于一个叫做 “线性模式的复杂性” 的想法, 我们在此不再详述. 事实证明, $4-AP$ 的复杂度为 $2$, 而 $3-AP$ 的复杂度为 $1$. 到目前为止, 我们介绍的技术对于复杂度为 $1$ 的模式非常有效, 但很难处理更高复杂度的模式.

我们现在介绍定理 8.1 的推论, 它与推论 2.0.7 非常相似:

推论 8.2. 如果 $G$ 是一个 $3$-图, 且满足每条边都包含在一个唯一的四面体中, 则 $G$ 有 $o\left(n^3\right)$ 条边.

这个推论可由超图删除引理直接推导得到. 我们现在使用这个推论来证明 Szemerédi 定理:

定理 2.4.

我们将证明等差数列长度 $k=4$ 的情形, $k$ 取更大的值时证明是类似的. 令 $M=6N+1$ (这里重要的是保证 $M>3N$ 并且 $M$ 与 $6$ 互质) . 用 $X,Y,Z,W$ 四部分构建一个 4 部的 $3$ -图 $G$, 每一个部分都是包含 $M$ 个元素的集合, 顶点的标号由 $\mathbb{Z}/M\mathbb{Z}$ 构成. 假设 $x,y,z,w$ 分别代表 $X,Y,Z,W$ 中的元素, 我们按照如下规则来定义边: $$\begin{array}{rl}xyz\in E(G)& \text{当且仅当}3x+2y+z\in A\\ xyw\in E(G)& \text{当且仅当}2x+y-w\in A\\ xzw\in E(G)& \text{当且仅当}x-z-2w\in A\\ yzw\in E(G)& \text{当且仅当}-y-2z-3w\in A\end{array}$$

请注意, $xyzw$ 是四面体当且仅当 $3x+2y+z,2x+$ $y-w,x-z-2w,-y-2z-3w\in A$. 但是, 这些值构成了公差为 $-x-y-z-w$ 的 $4-AP$. 由于 $A$ 不含 $4-AP$, 所以 $A$ 中的四面体是平凡的 $4-AP$ (公差为 $0$) . 因此, 每条边都恰好位于一个四面体中. 由上面的推论, 边的数量为 $o\left(M^3\right)$. 但是根据构造, 边的数量是 $4M^2|A|$, 所以我们可以得出 $|A|=o(M)=o(N)$ .

$\square$

与上述证明类似的思路可用于证明定理 2.5, 该定理保证了任意正上密度的 ${\mathbb{Z}}^d$ 的子集都包含任意星座. 一个简单的例子是 ${\mathbb{Z}}^2$ 中的正方形, 由点 $(x,y),(x+d,y),(x,y+d),(x+d,y+d)$ 组成, 其中 $x,y\in \mathbb{Z}$ 且 $d$ 为正整数.