超图容器方法 | Codeboy's Blog

形式陈述

设 $\mathcal H$ 是有限顶点集 $V$ 上的 $r$ -一致超图， $r\ge2$ 。集合 $I\subseteq V$ 称为独立集，若没有超边 $e\in E(\mathcal H)$ 完全包含于 $I$ 。容器方法在适当码度条件下构造一个远小于幂集的集合族 $\mathcal C$ ，使

\forall I\text{ 独立},\quad \exists C\in\mathcal C, I\subseteq C,

同时每个容器 $C$ 在 $\mathcal H$ 中诱导的超边很少。独立集仍可很多，容器并不逐个列举它们；它把它们按共享的粗结构分组。

一个常用的平衡码度推论如下。记 $N=|V|$ 、平均度 $d=r e(\mathcal H)/N$ ，并令

\Delta_j(\mathcal H)= \max_{S\in\binom{V}{j}}\left|\{e\in E(\mathcal H):S\subseteq e\}\right|.

假设 $d>0$ 。固定 $r\ge2$ 、 $K\ge1$ 与 $0<\varepsilon<1/2$ 后，存在常数 $c,C>0$ ：若某个 $0<\tau<c$ 满足

\Delta_j(\mathcal H) \le K\tau^{j-1}d, \qquad 1\le j\le r,

则存在容器族 $\mathcal C$ ，每个独立集都包含于某个 $C\in\mathcal C$ ，每个容器满足

e(\mathcal H[C])\le\varepsilon e(\mathcal H),

并且

\log|\mathcal C|\le C N\tau\log(1/\tau).

这是 Saxton–Thomason Corollary 3.6 的一个便于应用的推论。原文使用 Definition 3.2 的加权共度函数，要求 $\delta(\mathcal H,\tau')\le\varepsilon/(12r!)$ 。由本页码度界，将参数放大为 $\tau'=A\tau$ 后，各个 $j\ge2$ 的归一化共度项至多为 $K/A^{j-1}$ ；取依赖 $r,K,\varepsilon$ 的足够大常数 $A$ ，便满足原条件，再令 $c<1/(2A)$ 保证 $\tau'<1/2$ 。常数缩放被吸收到 $C$ 中，而非直接拿同一个 $\tau$ 忽略小共度要求。无超边时可单独取唯一容器 $V$ 。

直觉

把待研究的组合对象编码成 $V$ 的子集，把每个禁用配置编码成一条超边；合法对象就正好是独立集。容器算法反复挑选当前高影响顶点：若独立集包含它，就把它记入一个很小的“指纹”；若不包含，就从候选池排除。每次决定都会因高共度带走大量潜在超边，最终候选池内部只剩少量禁用配置。

两个小型蓝色指纹分别映射到绿色容器，每个容器覆盖多个独立集并满足内部诱导超边数量低的约束 — 超图容器的指纹覆盖

指纹大小通常为 $O(N\tau)$ ，因此可能的指纹数至多约为

\exp\bigl(O(N\tau\log(1/\tau))\bigr),

这就是容器数远少于 $2^N$ 的来源。码度条件确保超边没有过度集中在某个小顶点组上；否则选中一个核心可能同时决定几乎全部约束，平均度无法描述真实分支复杂度。

容器方法的两个输出要分开理解：“少数容器”控制枚举熵，“每个容器内部禁配置少”提供结构入口。后者不等于容器顶点少；要从超边少进一步推出 $|C|$ 小或 $C$ 接近某个模板，核心输入是极值超饱和，必要时再叠加稳定性或移除引理。

例子与边界

要编码 $K_n$ 上的无三角形图，构造三一致超图 $\mathcal H$ ：其顶点是 $K_n$ 的边，每个三角形的三条边组成一条超边。于是

|V(\mathcal H)|=\binom n2,\qquad e(\mathcal H)=\binom n3,\qquad d=n-2.

$\mathcal H$ 的独立集恰是所有无三角形图的边集。一条 $K_n$ 边属于 $n-2$ 个三角形；两条边若能同属三角形，其共度为 $1$ ；三条边的共度至多也为 $1$ 。取 $\tau\asymp n^{-1/2}$ 时， $\Delta_2=1\ll\tau d\asymp\sqrt n$ ，而 $\Delta_3=1\asymp\tau^2d$ ，正落在平衡码度尺度上。

相应容器数的对数至多为 $O(n^{3/2}\log n)=o(n^2)$ ，每个容器只含少量三角形。再用三角形移除引理把容器删改为无三角形图，并用 Turán 上界控制其边数，可得到无三角形标号图数量

2^{n^2/4+o(n^2)}.

这里先对每个固定的小误差参数控制容器边数，再令 $n\to\infty$ ，最后让误差参数趋零；不能把依赖该参数的常数一开始就当作统一常数。匹配下界来自固定一个平衡二部划分后任意选跨部边，共有 $2^{\lfloor n^2/4\rfloor}$ 个无三角形图。上下界合起来给出上述主指数，也是原文 Corollary 2.4 在 $H=K_3$ 时的结论。

若超图只有很小平均度，或大量超边共享同一个固定核心，可能找不到使全部码度不等式成立的有用 $\tau$ 。此时盲目套用容器结论只会得到接近 $2^V$ 的平凡族。非一致超图、加权对象与稀疏随机宿主都有扩展版本，但参数函数和结论需重新声明。

推论与应用

容器方法统一处理禁子图图族、无算术进展集合、和自由集合、独立集与随机离散结构。若另有稳定性定理说明少超边的集合必须接近有限个极值模板，容器便会继承这种典型结构：不仅数出合法对象，还能证明随机选取的合法对象以高概率接近某种分部或代数形态。

它与概率方法常协同但角色不同。随机选择通常证明某个对象存在；容器是确定性的全体覆盖机制，可在覆盖之后对每个容器分别施加概率估计。应用的关键不是为每个新问题重造容器算法，而是验证编码后的超图具有合适平均度、码度与超饱和性质。

参考资料

József Balogh, Robert Morris, and Wojciech Samotij, “Independent sets in hypergraphs,” Journal of the American Mathematical Society 28 (2015), 669–709.
David Saxton and Andrew Thomason, “Hypergraph containers”, Inventiones Mathematicae 201 (2015), 925–992，Definition 3.2、Corollary 3.6（共度与覆盖计数），Theorem 2.3、Corollary 2.4（禁子图计数）。
Robert Morris, “The method of hypergraph containers,” in Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018, Vol. IV, World Scientific, 2018, 3059–3092.

形式陈述 ​

形式陈述