9. 超图的正则性

超图正则性是一个比普通图正则性更难的概念. 我们不会详细讨论, 但会简单地讨论一些核心思想. 请参阅 Gowers (2006) 以了解一份精彩的证明.

定义超图正则性的一个简单的尝试是将其定义为类似于普通图正则性, 如下所示:

定义 9.1 (3-graph 正则性的简单版本). 给定一个 $3$ -graph $G^{(3)}$ 和三个子集 $V_{1}, V_{2}, V_{3} \subset V (G^{(3)})$ , 我们说 $(V_{1}, V_{2}, V_{3})$ 是 $ϵ$ -正则的, 如果对于所有满足 $∣ A_{i} ∣ \geq ϵ ∣ V_{i} ∣$ 的 $A_{i} \subset V_{i}$ , 我们有 $∣ d (V_{1}, V_{2}, V_{3}) - d (A_{1}, A_{2}, A_{3}) ∣ \leq ϵ$ . 其中, $d (X, Y, Z) = \frac{e _{G^{(3)}} ( X , Y , Z )}{∣ X ∣∣ Y ∣∣ Z ∣}$ $e_{G^{(3)}} (X, Y, Z) = ∣ ∣ {(x, y, z) \in X \times Y \times Z ∣ x yz \in E (G^{(3)})} ∣ ∣$

如果你用这个定义来完成 Szemerédi 正则引理的证明, 你可以构造一个非常相似的超图版本的证明. 它表明, 对于任意 $ϵ > 0$ , 存在 $M = M (ϵ)$ 使得每个图最多可划分为 $M$ 个部分, 且不是 $ϵ$ -正则的三元组的占比小于 $ϵ$ (回顾定义 1.1.4) . 事实上, 如果愿意, 我们甚至可以做到划分是均衡的.

那么我们将遇到什么问题呢? 回想一下, 我们涉及 Szemerédi 正则引理的证明通常包含三个步骤: 分区、清理和计数. 事实上, 我们在计数步骤将遇到麻烦.

回想一下, 正则性应该代表着伪随机性. 正因为如此, 我们为什么不尝试真正的随机超图, 一起看看会发生什么? 让我们考虑两种不同的随机 $3$ -图结构:

1.	首先选择常量 $p, q \in [0, 1]$ . 构建一个随机图 $G^{(2)} = G (n, p)$ , 这是一个普通的 Erdös-Renyi 图. 然后通过将 $G^{(2)}$ 中的每个三角形作为 $G^{(3)}$ 的边以概率 $q$ 放进 $G^{(3)}$ . 将此称为 $3$ -图 $A$ .
2.	对于每条可能的边 (即顶点集的所有三元组) , 以概率 $p^{3} q$ 生成边, 不同边的生成是独立的. 将此称为 $3$ -图 $B$ .

$A$ 和 $B$ 的每个三元组都以概率 $p^{3} q$ 独立出现, 并且两个图都大概率满足我们上述 $ϵ$ -正则性的概念. 然而, 我们可以在这两个图中计算 $K_{4}^{(3)}$ (四面体) 的密度, 发现它们的概率并不相同. 在图 $B$ 中, 每条边出现的概率为 $p^{3} q$ , 并且边独立出现, 所以四面体出现的概率为 $(p^{3} q)^{4}$ . 然而, 在图 $A$ 中, 四面体要求 $G^{(2)}$ 中存在 $K_{4}$ . 由于 $K_{4}$ 有 $6$ 条边, 它以概率 $p^{6}$ 出现在 $G^{(2)}$ 中, 然后构成四面体的每个三角形以 $q$ 独立出现. 因此, 任何给定的四面体出现在 $A$ 中的概率是 $p^{6} q^{4}$ , 这显然与 $(p^{3} q)^{4}$ 不同. 因此, 上述超图正则性的概念并没有很好地限制子图的出现频率.

然而, 这种超图正则性的概念仍然有用. 事实证明, 如果 $H$ 是线性的, 则超图 $H$ 有一个计数引理, 它告诉我们每对边最多与 1 个顶点相交. 该定理的证明类似于图计数引理 (定理 5.0.3) . 但现在, 让我们把目标转向寻找更好的超图正则性概念.

定义 9.2 (Triple density on top of 2-graphs).

给定 $A, B, C \subset E (K_{n})$ (将 $A, B, C$ 视为子图) 和一个 3-图 $G$ , $d_{G} (A, B, C)$ 被定义为三元组 ${x yz ∣ yz \in A, x z \in B, x y \in C}$ 的数量除以 $G$ 中三元组的数量.

使用上面的定义, 我们可以定义一个正则的边子集三元组和一个正则划分, 我们在这里非正式地描述这两者. 考虑一个划分 $E (K_{n}) = G_{1}^{(2)} \cup \dots \cup G_{l}^{(2)}$ , 满足对大多数三元组 $(i, j, k)$ , $(G_{i}^{(2)}, G_{j}^{(2)}, G_{k}^{(2)})$ 上有许多三角形. 我们认为 $(G_{i}^{(2)}, G_{j}^{(2)}, G_{k}^{(2)})$ 是正则的, 如果对于任意满足 $(A_{i}^{(2)}, A_{j}^{(2)}, A_{k}^{(2)})$ 上没有太少三角形的子图 $A_{i}^{(2)} \subset G_{i}^{(2)}, A_{j}^{(2)} \subset G_{j}^{(2)}, A_{k}^{(2)} \subset G_{k}^{(2)}$ , 有

$∣ ∣ d (G_{i}^{(2)}, G_{j}^{(2)}, G_{k}^{(2)}) - d (A_{i}^{(2)}, A_{j}^{(2)}, A_{k}^{(2)}) ∣ ∣ \leq ϵ$

接着, 我们将正则划分定义为这样的一个划分, 该划分中非正则的三元组最多占划分中所有三元组的 $ϵ$ 倍 (参考定理 1.1.4) . 除此之外, 我们还需要对顶点集进行划分来进一步正则化 $G_{1}^{(2)}, \dots, G_{l}^{(2)}$ . 因此, 我们得到超图正则性的信息如下:

1.	给出 $E (K_{n})$ 的一个划分 (每一部分是一个子图) , 使得 $G^{(3)}$ 是伪随机的;
2.	给出 $V (G)$ 的一个划分, 使得上述步骤中的图是强伪随机的 (类似于定理 6.0.3) .

需要提醒的是, 文献中存在许多版本的超图正则性, 并非所有版本都是明显等价的. 事实上, 在某些情况下, 证明它们之间的等价性需要做很多工作. 我们仍然不太确定哪种超图正则性的概念 (如果有的话) 是最 “自然的”.

与一般图正则性类似, 我们可以询问超图正则性的上界是什么, 该问题的答案同样令我们苦恼. 对于 $2 - uniform$ 超图, 即一般图, 上界需要一个 TOWER 函数. 对于 $3 - uniform$ 超图, 上界要求我们在 Ackermann 层级向上一步, 到达 WOWZER 函数 (重复应用 TOWER) , 也称作 Pentation. 对于 $4 - uniform$ 超图, 我们必须在 Ackermann 层级向上再多一步, 依此类推. 因此, 超图正则性的应用往往会给我们提供非常差的关于逆 Ackermann 的定量上界. 事实上, 最著名的 $k - A P$ 上界如下:

定理 9.3 (Gowers 2001). 对于任意 $k \geq 3$ , 存在 $c_{k} > 0$ 使得 $[N]$ 的所有 $k - A P - free$ 子集至多有 $N (lo g lo g N)^{- c_{k}}$ 个元素.

笔记 9.4. $k \geq 5$ 时, 这是已知最好的的上界, 但对于 $k = 3, 4$ 有已知更好的上界.

对于高维 Szemerédi 定理 (定理 2.5) , 已知最好的上界一般通过超图正则性引理得到. 第一个证明来自遍历理论, 由于依赖于紧致性论证, 它实际上没有给出定量的上界. 使用超图正则性的一个主要动机是去获得定理 2.5 的定量上界.

名字空间

视图

9. 超图的正则性