计算图中的独立集

摘要。

在这篇简短的调查文章中，我们提出了一种基本但非常强大的方法来枚举图中的独立集合。 三十多年前，克莱特曼和温斯顿首次采用了这种方法，随后被许多研究人员在不同的情况下多次使用。 我们对该方法的介绍通过其在“现实生活”组合问题中的几种应用进行了说明。 特别是，我们推导了正则图、$\{1,\mathrm{\dots },n\}$ 的无和子集和 $C_4$ 无图中独立集数量的界限，并给出了 Roth 的类似物的简短证明稀疏随机整数集中 $3$ 项算术级数定理最初由 Kohayakawa、Łuczak 和 Rödl 提出并证明。

1. 介绍

组合学中许多经过充分研究的问题都涉及表征满足某些“局部”约束的离散结构。 例如，著名的 Szemerédi [42] 定理给出了前一个 $n$ 整数子集最大大小的上限，该子集不包含固定的算术级数。长度$k$。再举一个例子，极值图论中研究的原型问题可以追溯到 Mantel [32] 和 Turán [43] 的工作，它是表征图的问题不包含固定图 $H$ 作为子图。

此类问题属于以下总体框架。 我们得到一个有限集 $V$ 和 $V$ 子集的集合 $\mathscr{H}$。对于不包含 $\mathscr{H}$ 任何成员的集合 $I\subseteq V$ 可以说什么呢？ 这样的集合$\mathscr{H}$通常称为超图，其顶点集$V$,$\mathscr{H}$的成员称为边，任何不包含边的集合$I\subseteq V$称为独立集合。 鉴于此，人们可能会说组合学的很大一部分涉及研究各种超图中的独立集。 例如，在上一段的第一个示例中，$V$是集合$\{1,\mathrm{\dots },n\}$,$\mathscr{H}$是所有$k$的集合 - $V$ 中包含的算术级数项；用这种语言表述，Szemerédi 定理表明，对于每个正常数 $\delta$,$\mathscr{H}$ 中的每个独立集合都少于 $\delta n$ 个元素，前提是 $n$ 足够大。 在第二个例子中，$V$ 是给定 $n$ 顶点集合上完整图的边集，$\mathscr{H}$ 是完整图中构成 $H$ 副本的 $|E(H)|$ 边的所有 $\left(\genfrac{}{}{0pt}{}{n}{|V(H)|}\right)$ 集的族；在此符号中，如果 $H$ 是一个具有 $k+1$ 个顶点的簇，那么图兰定理指出，$\mathscr{H}$ 中最大的独立集正是具有边集 $V$ 的完整图的完整平衡 $k$ 部分子图的边集，以及 Kolaitis、Prömel、和 Rothschild [29]指出，$\mathscr{H}$ 的几乎所有独立集都是 $k$ 部分图，也就是说，$\mathscr{H}$ 中不是完整图的边集 $V$ 部分子图 $k$ 的边集的独立集的数目 $i^{\ast }(\mathscr{H})$ 满足 $i^{\ast }(\mathscr{H})/i(\mathscr{H})\to 0$ 即 $n\to \mathrm{\infty }$。

对于超图$\mathscr{H}$，令$ℐ(\mathscr{H})$表示$\mathscr{H}$中所有独立集的族，令$i(\mathscr{H})=|ℐ(\mathscr{H})|$，令$\alpha (\mathscr{H})$为$ℐ(\mathscr{H})$元素的最大基数，通常称为$\mathscr{H}$的独立数。 对于特定的超图$\mathscr{H}$，人们通常会提出两个自然问题：

1. 确定$\alpha (\mathscr{H})$并用$\alpha (\mathscr{H})$元素描述所有$I\in ℐ(\mathscr{H})$。

2. 估计$i(\mathscr{H})$并描述$ℐ(\mathscr{H})$的“典型”成员。

让我们在此指出，提供 $ℐ(\mathscr{H})$ 典型元素的精确表征通常会产生对 $i(\mathscr{H})$ 的精确估计。

在以下两个不等式中可以很容易地观察到问题 (i) 和 (ii) 之间的明显联系，它们是上述定义的微不足道的结果以及家庭的事实$ℐ(\mathscr{H})$ 在取子集时是封闭的：

$$2^{\alpha (\mathscr{H})}⩽i(\mathscr{H})⩽\sum _{m=0}^{\alpha (\mathscr{H})}\left(\genfrac{}{}{0pt}{}{|V(\mathscr{H})|}{m}\right).$$ (1)

请注意，除非 $\alpha (\mathscr{H})$ 非常接近 $|V(\mathscr{H})|$，否则 (1) 中给出的 $i(\mathscr{H})$ 的下限和上限相当离的远。 由于对于许多有趣的超图$\mathscr{H}$来说，这个朴素的下界实际上相当接近最好的可能，因此许多研究人员的努力一直集中在改进上限上。

在这篇简短的调查文章中，我们提出了一种基本但非常强大的方法，用于在 $\mathscr{H}$ 的所有边都具有大小 2（即 $\mathscr{H}$)的情况下证明更强的上限是一个图表。 三十多年前，Kleitman 和 Winston 首次描述了这种方法，他们用它来获得格子数量的上限 [25] 和没有长度为四的循环的图 [26]。 随后，几位研究人员（尤其是 Sapozhenko）在枚举正则图 [1, 36] 中的独立集和交换群中的无和集 [ 中的独立集时，重新发现了该方法的变体。 1, 31, 37]。 我们将通过该方法在“现实生活”组合问题中的几种应用来说明我们对该方法的介绍。 我们想在这里强调，这里提出的结果或证明技术都不是新的，但我们希望将它们放在一起看到有一定的价值。

2. 克莱特曼-温斯顿算法

假设给定一个带有 $n$ 顶点的任意图 $G$。 我们的目标是给出 $i(G)$ 的上限，即 $G$ 中独立集合的数量。 Kleitman 和 Winston 的想法是设计一种算法，在给定特定的独立集 $I\in ℐ(G)$ 的情况下，将以可逆的方式对 $I$ 进行编码。 至关重要的是，编码的执行方式应易于估计算法的输出总数。 由于对于每个可逆编码，输出的总数恰好是 $i(G)$，这样就可以得出该数量的上限。

Kleitman 和 Winston 的关键思想是考虑根据度数排序的 $G$ 顶点，并将每个独立集合 $I$ 编码为 $I$ 我们在下面对此进行了精确说明。

Definition。

令 $G$ 为一个图，并在 $V(G)$ 上固定任意全序。 对于每个$A\subseteq V(G)$,$A$的最大度排序是$A$所有元素的排序$(v_1,\mathrm{\dots },v_{|A|})$ >，其中对于每个$j\in \{1,\mathrm{\dots },|A|\}$,$v_j$是由$A\setminus \{v_1,\mathrm{\dots },v_{j-1}\}$诱导的$G$子图中的最大度顶点；通过优先考虑 $V(G)$ 上固定总顺序中较早出现的顶点来打破联系。

The Algorithm。

假设给出了一个图$G$、一个$I\in ℐ(G)$和一个整数$q⩽|I|$。 设置$A=V(G)$和$S=\mathrm{\varnothing }$。 对于 $s=1,\mathrm{\dots },q$，执行以下操作：

1. 令 $(v_1,\mathrm{\dots },v_{|A|})$ 为 $A$ 的最大度数排序。

2. 假设 $j_s$ 是最小索引 $j$，使得 $v_j\in I$.

3. 将 $v_{j_s}$ 从 $A$ 移动到 $S$。

4. 从$A$中删除$v_1,\mathrm{\dots },v_{j_s-1}$。

5. 从$A$中删除$N_G(v_{j_s})\cap A$。

输出$(j_1,\mathrm{\dots },j_q)$和$A\cap I$。

对于每个输出序列 $(j_1,\mathrm{\dots },j_q)$ 和每个 $s\in \{1,\mathrm{\dots },q\}$，用 $A(j_1,\mathrm{\dots },j_s)$ 和 $S(j_1,\mathrm{\dots },j_s)$ 表示集合 $A$ 和 $S$ 分别在算法的第 $s$ 次迭代结束时（在生成此特定序列 $(j_1,\mathrm{\dots },j_q)$ 的某些输入 $I$ 上运行）。 请注意，这些定义并不依赖于 $I$ 的选择，因为序列 $(j_1,\mathrm{\dots },j_q)$ 唯一地确定了集合 $S$ 和 $A$ 在整个过程中如何演变算法。 更准确地说，如果在两个输入 $I,I^{\prime }\in ℐ(G)$ 上运行算法产生相同的序列 $(j_1,\mathrm{\dots },j_q)$，那么这两个执行也将产生相同的集合 $S$ 和 $A$。 事实上，在算法的第 $s$ 次迭代中，集合 $S$ 和 $A$ 的所有修改仅取决于 $j_s$。

请务必注意每个 $s$ 的 $S(j_1,\mathrm{\dots },j_s)\subseteq I$ 和 $I\setminus S(j_1,\mathrm{\dots },j_s)\subseteq A(j_1,\mathrm{\dots },j_s)$。事实上，根据 $j_s$ 的极小性和 $I$ 独立的假设，从 $A$ 中删除的 $I$ 的唯一顶点是移至$S$。由此可见，我们可以从算法的输出中恢复集合$I$，如$I=S(j_1,\mathrm{\dots },j_q)\cup (A(j_1,\mathrm{\dots },j_q)\cap I)$。 我们还注意到序列$(j_1,\mathrm{\dots },j_q)$可以从集合$S(j_1,\mathrm{\dots },j_q)$中恢复以供将来参考。 事实上，如果在某个输入 $I\in ℐ(G)$ 上运行该算法会产生一个序列 $(j_1,\mathrm{\dots },j_q)$ 和 $S=S(j_1,\mathrm{\dots },j_q)$，那么在运行该算法时，如果将 $I$ 替换为 $S$，也会产生相同的序列。最后，让我们注意一下 $j_1+\mathrm{\dots }+j_q⩽|V(G)|-|A(j_1,\mathrm{\dots },j_q)|$，因为在主循环第 $s$ 次迭代的步骤 (c) 和步骤 (d) 中，我们从 $A$ 中删除了一些 $j_s$ 顶点。

令 $i(G,m)$ 为 $G$ 中精确具有 $m$ 元素的独立集的数量。 上述观察结果很容易表明，对于每个 $m$ 和 $q$ 以及 $m⩾q$，

$$i(G,m)⩽\sum _{(j_s)}i(G[A(j_1,\mathrm{\dots },j_q)],m-q)⩽\sum _{(j_s)}\left(\genfrac{}{}{0pt}{}{|A(j_1,\mathrm{\dots },j_q)|}{m-q}\right),$$ (2)

其中上述总和涵盖所有输出序列$(j_1,\mathrm{\dots },j_q)$。 特别是，让$n=|V(G)|$，

$$i(G)⩽\sum _{m=0}^{q-1}\left(\genfrac{}{}{0pt}{}{n}{m}\right)+\sum _{(j_s)}i\left(G[A(j_1,\mathrm{\dots },j_q)]\right)⩽\sum _{m=0}^{q-1}\left(\genfrac{}{}{0pt}{}{n}{m}\right)+\sum _{(j_s)}{2}^{|A(j_1,\mathrm{\dots },j_q)|}.$$ (3)

鉴于 (2) 和 (3)，使集合 $A(j_1,\mathrm{\dots },j_q)$ 尽可能小、对所有值统一是符合我们的利益的$(j_1,\mathrm{\dots },j_q)$。 这就是为什么我们考虑根据最大度排序列出 $A$ 的顶点。 （细心的读者可能已经注意到，这种特定的排序在算法的每次迭代中最大化 ${\mathrm{deg}}_G(v_{j_s},A)$。） 假设我们处于算法主循环的第 $s$ 次迭代，并令 $A^{\prime }=A\setminus \{v_1,\mathrm{\dots },v_{j_s-1}\}$（其中 $A$ 与本次迭代开始时相同），即是，$A=A(j_1,\mathrm{\dots },j_{s-1})$。 根据最大度排序的定义，

$$|N_G(v_{j_s})\cap A^{\prime }|=\underset{v\in A^{\prime }}{\max }{\mathrm{deg}}_G(v,A^{\prime })⩾\frac{2e_G(A^{\prime })}{|A^{\prime }|}.$$

特别是，如果$e_G(A^{\prime })=\beta \left(\genfrac{}{}{0pt}{}{|A^{\prime }|}{2}\right)$，则上述不等式的右侧为$\beta (|A^{\prime }|-1)$。 因此，在算法主循环的第$s$次迭代期间，从$A$中移除的顶点数量至少为$j_s+\beta (|A^{\prime }|-1)$，即至少为$\beta |A|$，如$|A^{\prime }|-1=|A|-j_s$和$\beta ⩽1$。 换句话说，只要集合 $A$ 导出的子图的密度超过某个 $\beta$，算法主循环的每次迭代都会收缩 $A$至多 $1-\beta$ 倍。

以下两个引理都隐含在克莱特曼和温斯顿的著作中，总结了上述讨论。 第一个引理给出了满足特定局部密度条件的图中给定大小的独立集合的数量的简单界限。 该引理的确切陈述取自[27]。 第二个引理描述了这样一个局部稠密图中所有独立集合的族。 该引理的表述受到[7]主要结果的表述的启发。

Lemma 1.

令 $G$ 为 $n$ 顶点上的图，并假设整数 $q$ 和实数 $R$ 和 $\beta \in [0,1]$ 满足

$$R⩾e^{-\beta q}n.$$ (4)

假设每个集合$U\subseteq V(G)$与$|U|⩾R$在$G$中引出的边数满足

$$e_G(U)⩾\beta \left(\genfrac{}{}{0pt}{}{|U|}{2}\right).$$ (5)

然后，对于每个带有 $m⩾q$ 的整数 $m$，

$$i(G,m)⩽\left(\genfrac{}{}{0pt}{}{n}{q}\right)\left(\genfrac{}{}{0pt}{}{R}{m-q}\right).$$ (6)

证明。

由于恰好有 $\left(\genfrac{}{}{0pt}{}{n}{q}\right)$ 序列 $(j_1,\mathrm{\dots },j_q)$ 满足 $j_1+\mathrm{\dots }+j_q⩽n$ 和 $j_s⩾1$ 的每个 $s$，因此 (2) 右侧的和最多有 $\left(\genfrac{}{}{0pt}{}{n}{q}\right)$ 项。 因此，只要证明算法输出的每个序列$(j_1,\mathrm{\dots },j_q)$，集合$A(j_1,\mathrm{\dots },j_q)$最多有$R$个元素即可。 如果不是这种情况，那么就会有一些序列 $(j_1,\mathrm{\dots },j_q)$，这样对于每个 $s\in \{1,\mathrm{\dots },q\}$,$s$ 中的集合 $A\setminus \{v_1,\mathrm{\dots },v_{j_s-1}\}$算法主循环的第次迭代（在导致此特定序列的某些输入上运行）将具有多个 $R$ 元素，因此会在 $G$ 中引入边缘密度为至少$\beta$。 根据我们的讨论，每次 $q$ 迭代都会将集合 $A$ 缩小至多 $1-\beta$ 倍。 由于 $|A|=|V(G)|=n$ 在算法开始时，那么，通过 (4)，

$$|A(j_1,\mathrm{\dots },j_q)|⩽{(1-\beta )}^{q}n⩽e^{-\beta q}n⩽R,$$

矛盾。 ∎

Lemma 2.

令 $G$ 为 $n$ 顶点上的图，并假设整数 $q$ 和实数 $R$ 和 $D$ 满足

$$R+qD⩾n.$$ (7)

假设每个集合$U\subseteq V(G)$与$|U|⩾R$在$G$中引出的边数满足

$$2e_G(U)⩾D|U|.$$ (8)

然后存在 $q$ 元素子集 $V(G)$ 的集合 $𝒮$ 以及两个映射 $g:ℐ(G)\to 𝒮$ 和 $f:𝒮\to 𝒫(V(G))$，例如每个 $S\in 𝒮$ 的 $|f(S)|⩽R$ 和每个 $I\in ℐ(G)$ 的 $g(I)\subseteq I\subseteq f(g(I))\cup g(I)$ 至少包含 $q$ 元素。

证明。

我们定义映射 $f$ 和 $g$ 以及系列 $𝒮$ 如下。 我们只需为每个至少包含 $q$ 元素的 $I\in ℐ(G)$ 运行输入 $I$ 的算法，并让 $g(I)$ 和 $f(g(I))$ 分别为最终集合$S$和$A$。 此外，我们让 $𝒮$ 是所有此类 $S$ 的族，即 $g$ 所采用的值的集合。算法描述后面的段落中的讨论应该让我们相信这是 $f$ 的有效定义，对于每个 $I$ 的 $g(I)\subseteq I\subseteq f(g(I))\cup g(I)$ 如上所述，并且$𝒮$ 仅由 $V(G)$ 的 $q$ 元素子集组成。 只需检查每个这样的 $I$ 的 $|f(g(I))|⩽R$ 就足够了。 如果不是这种情况，那么就会有一些序列 $(j_1,\mathrm{\dots },j_q)$，这样对于每个 $s\in \{1,\mathrm{\dots },q\}$,$s$ 中的集合 $A\setminus \{v_1,\mathrm{\dots },v_{j_s-1}\}$算法主循环的第 th 次迭代（在生成此序列的输入 $I$ 上运行）将具有多个 $R$ 元素，因此会在 $G$ 中引入平均度数至少为 $D$ 的子图。但是，每次 $q$ 迭代都会从 $A$ 中删除至少 $D+1$ 由于 $|A|=|V(G)|=n$ 在算法开始时，然后通过 (7)，

$$|A(j_1,\mathrm{\dots },j_q)|⩽n-Dq⩽R,$$

矛盾。 ∎

在结束本节之前，让我们做一些最后的评论。 首先，引理2的结论比引理1的结论更强。 这只是因为第二个引理的陈述中 $f$ 和 $g$ 的存在意味着第一个引理所断言的 $i(G,m)$ 上的界限。 此外，从证明中应该清楚地看出，两个引理的假设在以下意义上是“可互换的”。 如果图形 $G$ 满足 Lemma 1 的假设，且包含某些 $q$、$R$ 和 $\beta$，则 Lemma 2 的结论对 $G$ 以及相同的 $q$ 和 $R$ 成立；反之亦然，如果图 $G$ 满足 Lemma 2 的假设，且具有某些 $q$、$R$ 和 $D$，则 Lemma 1 的结论对具有相同 $q$ 和 $R$ 的 $G$ 成立。(后一个陈述是多余的，因为正如我们在前面已经指出的，Lemma 2 的结论比 Lemma 1 的结论更强）。

3. 应用领域

3.1. 正则图中的独立集

1988 年在班夫举行的数论会议上，格兰维尔猜想（参见 [1])，一个 $n$-顶点 $d$-正则图不能再有比 $2^{(1+o(1))\frac{n}{2}}$ 独立集合，其中 $o(1)$ 是一些趋向于 $0$ 作为 $d\to \mathrm{\infty }$ 的函数。 几年后，阿隆[1]证明了这一点，他证明了事实上

$$i(G)⩽2^{(1+O(d^{-0.1}))\frac{n}{2}}$$

对于每个 $n$ - 顶点 $d$ - 常规图 $G$。作为我们对引理 1 的第一次应用，我们得出了一个更强的估计，这是几年后由 Sapozhenko [36] 获得的，使用的参数与第 5 节中提出的参数非常相似2。

Theorem 3 ([36]).

存在绝对常数$C$，使得每个$n$-顶点$d$-正则图$G$满足

$$i(G)⩽2^{\left(1+C\sqrt{\frac{\log d}{d}}\right)\frac{n}{2}}.$$

Alon [1]推测当$n$能被$2d$整除时，则$\frac{n}{2d}$完全二分图的不相并并$K_{d,d}$ 在所有具有 $n$ 顶点的 $d$ 正则图中具有最大数量的独立集。 后来 Kahn [23] 猜想出一个稍强的陈述（下面的定理 4)，他在 $G$ 是二部的附加假设下证明了这一点，使用美丽的熵论证。 最近，Zhao [45] 证明了这一假设是不必要的，他给出了一个简短而优雅的论证，表明对于每个 $n$-vertex $d$-regular图$G$，存在一个$2n$-顶点$d$-正则二分图$G^{\prime }$，使得$i(G)⩽i{(G^{\prime })}^{1/2}$。 卡恩和赵的结果如下。

Theorem 4 ([23, 45]).

对于每个$n$-顶点$d$-正则图$G$，

$$i(G)⩽i{(K_{d,d})}^{\frac{n}{2d}}={\left(2^{d+1}-1\right)}^{\frac{n}{2d}}.$$

现在我们从引理 1 导出定理 3。

定理证明3。

令 $G$ 为 $n$-顶点 $d$-正则图。 事实上，我们将为每个 $m$ 估计 $i(G,m)$，并通过对所有 $m$ 求和来推断 $i(G)$ 上声明的界限。由于 $i(G)⩽2^n$ 和 $C$ 是任意常数，因此我们可以假设 $d$ 足够大（因此 $n$ 足够大）。 我们考虑两种情况。 首先，如果 $m⩽n/10$，那么我们只需注意

$$i(G,m)⩽\left(\genfrac{}{}{0pt}{}{n}{\frac{n}{10}}\right)⩽{(10e)}^{\frac{n}{10}}⩽2^{0.48n},$$ (9)

其中我们使用了众所周知的不等式 $\left(\genfrac{}{}{0pt}{}{a}{b}\right)⩽{(ea/b)}^b$，该不等式对所有 $a$ 和 $b$ 均有效。

在互补的情况下，$m>n/10$，我们将应用引理1。 为此，令 $B\subseteq V(G)$ 并注意

$$d|B|=\sum _{v\in B}{\mathrm{deg}}_G(v)=2e(B)+e(B,B^c)⩽2e(B)+\sum _{v\in B^c}{\mathrm{deg}}_G(v)=2e(B)+d(n-|B|).$$ (10)

固定任意 $\beta$，设 $R=\frac{n}{2}+\frac{\beta n^2}{2d}$，并观察如果 $|B|⩾R$，则 (10) 产生

$$e(B)⩾\frac{d}{2}(2|B|-n)⩾\frac{d}{2}(2R-n)⩾\frac{\beta n^2}{2}⩾\beta \left(\genfrac{}{}{0pt}{}{|B|}{2}\right).$$ (11)

假设$\beta >10/n$并让$q=\lceil 1/\beta \rceil$。 通过引理 1，因为

$$e^{-\beta q}n⩽e^{-1}n⩽R,$$

然后对于每个 $m$ 和 $m⩾\lceil n/10\rceil ⩾q$，

$$i(G,m)⩽\left(\genfrac{}{}{0pt}{}{n}{q}\right)\left(\genfrac{}{}{0pt}{}{\frac{n}{2}+\frac{\beta n^2}{2d}}{m-q}\right)⩽{\left(\frac{en}{q}\right)}^q\left(\genfrac{}{}{0pt}{}{\frac{n}{2}+\frac{\beta n^2}{2d}}{m-q}\right)⩽{(e\beta n)}^{\lceil 1/\beta \rceil }\cdot \left(\genfrac{}{}{0pt}{}{\frac{n}{2}+\frac{\beta n^2}{2d}}{m-q}\right).$$ (12)

对所有 $m$ 求和 (9) 和 (12) 得出

$$i(G)⩽2^{0.49n}+2^{\frac{n}{2}+\frac{\beta n^2}{2d}+\lceil 1/\beta \rceil {\log }_2(e\beta n)}$$

我们通过让 $\beta =\frac{\sqrt{d\log d}}{n}$ 获得声明的界限；我们注意到 $\sqrt{d\log d}>10$ 因为我们假设 $d$ 很大。 ∎

我们应该在此指出，通过对克莱特曼-温斯顿算法的执行进行比定理 1 的证明更仔细的分析，我们可以大大改进定理 3 所给出的上限。 我们之所以期待这种改进是可能的，主要是因为在 $|B|-n/2$ 远大于 $R-n/2$ 的情况下， (11) 中的第二个不等式非常粗糙。 引理1的证明使用(11)来表明在算法的每一步中，集合$A$至少损失$\beta |A|$ 元素，而实际上，只要 $|A|$ 与 $n/2+\beta n^2/(2d)$ 不是很接近，$A$ 就会丢失更多元素。 通过考虑将 $|A|$ 的“演化”划分为“二元”区间 $(n/2+n/2^{i+1},n/2+n/2^i]$（其中 $1⩽i⩽{\log }_{2}d-{\log }_2{\log }_{2}d$)，可以证明存在绝对常数 $C$ 使得每个 $n$-顶点 $d$-正则图 $G$ 满足

$$i(G)⩽2^{\left(1+C\frac{{(\log d)}^2}{d}\right)\frac{n}{2}}.$$

跟踪 $|A|$ 的这种 "演变 "的一种严谨方法是，反复引用 Lemma 2 与 $R_i=n/2+n/2^{i+1}$ 和 $D_i=d/2^i$ 的 $i=1,\mathrm{\dots },{\log }_{2}d-{\log }_2{\log }_{2}d$ 。 我们将填写详细信息作为读者的练习。

3.2. 无和集

上一节提到的格兰维尔猜想是由卡梅伦和埃尔多斯在同一数论会议上提出的一个问题引发的。 如果没有满足$x+y=z$的$x,y,z\in A$，则阿贝尔群的元素集合$A$称为无和。 让$[n]$表示集合$\{1,\mathrm{\dots },n\}\subseteq \mathbb{Z}$。 Cameron 和 Erdős 提出了确定集合 $[n]$ 中包含的无和集合 $\mathrm{SF}([n])$ 数量的问题。 他们指出，任何仅包含奇数整数或仅包含大于 $n/2$ 的整数的集合都是无和集合，并且不太可能存在另一个大的无和集合集合，这些集合本质上不是以下之一以上两种类型。 鉴于此，他们推测$\mathrm{SF}([n])=O(2^{n/2})$。 不久之后，Alon [1] 表明，前述的 Granville 猜想意味着以下对 $\mathrm{SF}([n])$ 的较弱估计，这将作为引理 1

Theorem 5 ([1]).

集合$\{1,\mathrm{\dots },n\}$最多有$2^{(1/2+o(1))n}$个无和子集。

大约十五年后，Green [18] 和 Sapozhenko [38] 独立解决了卡梅伦-埃尔多斯猜想。 Sapozhenko 提出的解决方案使用类似于 2 节中介绍的 Kleitman-Winston 算法的方法，而 Green 提出的解决方案则使用离散傅立叶分析。 我们在这里不讨论他们的任何一个论点，而是让感兴趣的读者参考原始论文。 最后，我们提到最近在 [3] 中获得了对具有给定元素数量的 $[n]$ 的无和子集数量的强估计，这暗示了猜想；那里的证明采用了第 2 节中提出的想法。

定理证明5。

首先观察 $[n]$ 中包含 $\{1,\mathrm{\dots },\lceil n/2\rceil -1\}$ 中少于 $n^{2/3}$ 个元素的所有子集的数量最多为 ${(n/2)}^{n^{2/3}}{2}^{n/2+1}$。 因此，我们可以将注意力限制在至少包含严格小于 $n/2$ 的 $n^{2/3}$ 元素的无和集合上。 对于每个这样的集合$A$，令$S_A$为$A$的$\lfloor n^{2/3}\rfloor$最小元素的集合。

给定一个集合$S\subseteq \{1,\mathrm{\dots },\lceil n/2\rceil -1\}$，定义一个带有顶点集$[n]$的辅助图$G_S$，方法是让

$$E(G_S)=\{xy:x+s\equiv y(modn)\text{for some}s\in S\cup (-S)\}$$

并注意 $G_S$ 是 $2|S|$ - 规则的，因为 $n-(\lceil n/2\rceil -1)>\lceil n/2\rceil -1$ ，因此 $S$ 和 $-S$ 包含不同的残基模$n$。关键的观察是，对于上面的每个无和 $A$，集合 $A\setminus S_A$ 是图中 $G_{S_A}$ 中的独立集合。 事实上，否则就会有 $x,y\in A\setminus S_A$ 和 $s\in S_A\cup (-S_A)$ 以及 $x+s\equiv y(modn)$；由于，这仅在$x+s=y$时才可能。 特别是，对于给定的$S\subseteq \{1,\mathrm{\dots },\lceil n/2\rceil -1\}$，最多有$i(G_S)$个满足$S=S_A$的无和集$A$。 根据定理3，我们得出结论

$$\mathrm{SF}([n])⩽{(n/2)}^{n^{2/3}}{2}^{n/2+1}+\left(\genfrac{}{}{0pt}{}{n/2}{n^{2/3}}\right)\cdot 2^{\left(1+O(n^{-1/3}\sqrt{\log n})\right)\frac{n}{2}}⩽2^{\left(1/2+O(n^{-1/3}\log n)\right)n}.\mathit{∎}$$

在结束本节之前，我们注意到 Alon [1] 的论文对确定任意有限交换群中包含的无和集的数量这一密切相关的问题进行了非常成功的研究;例如，参见[2,19,20,31,37]。 在许多这样的作品中，2 节中提出的想法的变体发挥着重要作用。

3.3. 正则图中没有小特征值的独立集

由于每个 $n$ 顶点双方形图 $G$ 都满足 $\alpha (G)⩾n/2$，因此它至少包含 $2^{n/2}$ 个独立集，因此只要 $G$ 是双方形图，第 3.1 节中证明的 $i(G)$ 上限基本上就是最佳可能。 当人们假设 $G$ 距离二分“很远”时，很自然会问这些界限是否可以改进。 Alon和Rödl[5]对此问题给出了肯定的回答。

回想一下，$n$ 顶点图 $G$ 的邻接矩阵是实值对称 $n\times n$ 矩阵，因此它具有 $n$ 实数特征值。 用 ${\lambda }_1,\mathrm{\dots },{\lambda }_n$ 表示这些特征值，其中 ${\lambda }_1⩾\mathrm{\dots }⩾{\lambda }_n$。 众所周知，数量$\max \{|{\lambda }_2|,|{\lambda }_n|\}$，称为$G$的第二特征值，与$G$。我们只对 $G$ 的最小特征值 ${\lambda }_n$ 感兴趣，用 $\lambda (G)$ 表示。 Hoffman[21]首先证明了每个$d$-正则$n$-顶点图$G$满足$\alpha (G)⩽\frac{-\lambda (G)}{d-\lambda (G)}n$。 后来这一点得到了显着加强 由 Alon 和 Chung [4] 提出，他们在 $\lambda (G)$ 和 $G$ 中由大量顶点引起的边数之间建立了以下关系，参见：扩展器混合引理（参见，例如[22])。

Lemma 6 ([4]).

令 $G$ 为 $n$-顶点 $d$-正则图。 对于所有$A\subseteq V(G)$，

$$2e_G(A)⩾\frac{d}{n}{|A|}^2+\frac{\lambda (G)}{n}|A|\left(n-|A|\right).$$

Alon 和 Rödl [5] 是第一个证明如果 $\lambda (G)$ 远大于 $-d$，那么每个这样的 $G$ 有远少于 $2^{n/2}$ 独立集。 作为引理 1 的下一个应用，我们得出了类似的估计，最初在 [2] 中证明。

Theorem 7 ([2]).

对于每个$\epsilon >0$，都存在一个常数$C$，使得以下内容成立。 如果$G$是一个$n$-顶点$d$-带有$\lambda (G)⩾-\lambda$的正则图，那么

$$i(G,m)⩽\left(\genfrac{}{}{0pt}{}{\left(\frac{\lambda }{d+\lambda }+\epsilon \right)n}{m}\right),$$

前提是$m⩾Cn/d$。

定理证明7。

修复一些$\epsilon >0$，令$G$为$n$-顶点$d$-正则图，并令$\lambda =-\lambda (G)$。 我们可以假设，否则没有什么可以证明的。 令 $U\subseteq V(G)$ 为 $|U|⩾\left(\frac{\lambda }{d+\lambda }+\frac{\epsilon }{2}\right)n$ 的任意集合。 引理 6 意味着

$$2e_G(U)⩾\frac{d}{n}{|U|}^2-\frac{\lambda }{n}|U|\left(n-|U|\right)=\frac{|U|}{n}\left((d+\lambda )|U|-\lambda n\right)⩾\frac{\epsilon d}{2}|U|⩾\frac{\epsilon d}{n}\left(\genfrac{}{}{0pt}{}{|U|}{2}\right).$$

让 $\beta =\frac{\epsilon d}{n}$、$q=\lceil \frac{\log (2/\epsilon )}{\epsilon }\cdot \frac{n}{d}\rceil$ 和 $R=\left(\frac{\lambda }{d+\lambda }+\frac{\epsilon }{2}\right)n$ 并观察 $R⩾e^{-\beta q}n$。 如果从引理 1 得出，对于每个带有 $m⩾q$ 的 $m$，

$$i(G,m)⩽\left(\genfrac{}{}{0pt}{}{n}{q}\right)\left(\genfrac{}{}{0pt}{}{R}{m-q}\right).$$ (13)

让 $r(t)$ 表示 (13) 的右侧，用 $t$ 替换 $q$。我们可以清楚地假设$m⩽\alpha (G)⩽\frac{\lambda }{d+\lambda }n$，否则$i(G,m)=0$。 初步计算表明

$$\frac{r(t+1)}{r(t)}=\frac{n-t}{t+1}\cdot \frac{m-t}{R-m+t+1}⩽\frac{nm}{(t+1)(R-m)}⩽\frac{2m}{\epsilon (t+1)}$$

因此

$$i(G,m)=r(q)=\prod _{t=0}^{q-1}\frac{r(t+1)}{r(t)}\cdot r(0)⩽\frac{{(2m)}^q}{{\epsilon }^{q}q!}\cdot \left(\genfrac{}{}{0pt}{}{R}{m}\right)⩽{\left(\frac{2em}{\epsilon q}\right)}^q\cdot {\left(\frac{R}{R+\epsilon n/2}\right)}^m\left(\genfrac{}{}{0pt}{}{R+\epsilon n/2}{m}\right),$$

我们使用的不等式 $a!>{(a/e)}^a$ 和 $\left(\genfrac{}{}{0pt}{}{a}{c}\right)⩾{(a/b)}^c\left(\genfrac{}{}{0pt}{}{b}{c}\right)$ 在 $a⩾b⩾c⩾0$ 时有效。 最后，如果 $K$ 足够大（作为 $\epsilon$ 的函数）和 $C⩾K\cdot \lceil \frac{\log (2/\epsilon )}{\epsilon }\rceil$，则对于每个 $m$ 和 $m⩾Cn/d⩾Kq$,

$${\left(\frac{2em}{\epsilon q}\right)}^{q/m}\cdot \frac{R}{R+\epsilon n/2}⩽{\left(\frac{2Ke}{\epsilon }\right)}^{1/K}\cdot \left(1-\frac{\epsilon }{2}\right)⩽1,$$

从而完成了定理的证明。 ∎

我们以几句话结束本节。 首先，定理断言中的常数 $\frac{\lambda }{d+\lambda }$ 对于 $n$、$d$ 和 $\alpha$ 的许多值来说是最优的，有是$n$-顶点$d$-带有$\alpha (G)=\frac{-\lambda (G)}{d-\lambda (G)}n=\alpha n$的正则图。 其次，不能放宽 $m⩾Cn/d$ 的假设，因为对于每个 $\epsilon >0$，每个 $n$ 顶点 $d$ 不规则图 $G$ 只要 $m⩽\epsilon n/(d+1)$ 就满足 $i(G,m)⩾\left(\genfrac{}{}{0pt}{}{(1-\epsilon )n}{m}\right)$。 （要看到这一点，请考虑构造一个独立集合的贪婪过程，该独立集合重复选择 $G$ 的任意顶点并将其及其所有邻居从 $G$ 中删除。）第三，上面的定理意味着 3.1 节中对于每个 $d$-正则图 $G$ 的 Granville 猜想为 $\lambda (G)⩾-d$。最后，我们向感兴趣的读者推荐[2]和[5]，其中定理7用于获取数量的上限分别是偶数阶阿贝尔群中的无和集以及一些多色拉姆齐数的下界。

3.4. 无$C_4$图的数量

作为我们的下一个示例，我们展示了 Kleitman 和 Winston [26] 的一篇论文的主要结果，该论文介绍了第 2 节中描述的方法。 如果一个图不包含长度为 4 的循环，则称该图为 $C_4$free ；让 $\mathrm{ex}(n,C_4)$ 表示具有 $n$ 个顶点的 $C_4$free 图中的最大边数。 Kővári、Sós 和 Turán [30] 的经典结果以及 Brown [10] 和 Erdős、Rényi 和 Sós [16] 的构造 意味着

$$\mathrm{ex}(n,C_4)=\left(\frac{1}{2}+o(1)\right)n^{3/2}.$$

令$f_n(C_4)$为顶点集$\{1,\mathrm{\dots },n\}$上的（标记的）$C_4$自由图的数量。 由于$C_4$自由图的每个子图本身都是$C_4$自由的，所以我们有

$$2^{\mathrm{ex}(n,C_4)}⩽f_n(C_4)⩽\sum _{m=0}^{\mathrm{ex}(n,C_4)}\left(\genfrac{}{}{0pt}{}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}{m}\right)=2^{\mathrm{\Theta }(\mathrm{ex}(n,C_4)\log n)},$$

这产生

$$\mathrm{ex}(n,C_4)⩽{\log }_2{f}_n(C_4)⩽O\left(\mathrm{ex}(n,C_4)\log n\right).$$ (14)

回答 Erdős、Kleitman 和 Winston [26] 的问题表明 (14) 中的下界严格达到常数因子。

Theorem 8 ([26]).

有一个正常数$C$使得

$${\log }_2{f}_n(C_4)⩽C{n}^{3/2}.$$

在继续证明定理之前，让我们先做一些评论。 事实上，Erdős 询问 ${\log }_2{f}_n(H)=(1+o(1))\mathrm{ex}(n,H)$ 是否为包含循环的任意 $H$。 Erdős、Frankl 和 Rödl [15] 在假设 $\chi (H)⩾3$ 的情况下证明了这一点。 最近，莫里斯和萨克斯顿[33]证明了${\log }_2{f}_n(C_6)⩾1.0007\cdot \mathrm{ex}(n,C_6)$对于无穷多个$n$。但是，除了以下两种特殊情况外，确定每个二分 $H$ 是否不是森林的 ${\log }_2{f}_n(H)=O(\mathrm{ex}(n,H))$ 问题仍然悬而未决：$H$是循环长度 4 个 [26]、6 个 [24] 或 10 个 [33] 或 $H$ 是一个不平衡完全二分图[8, 9]0>。 更准确地说，在[9]和[33]中证明了每当$2⩽s⩽t$时${\log }_2{f}_n(K_{s,t})=O(n^{2-1/s})$并且${\log }_2{f}_n(C_{2\mathrm{\ell }})=O(n^{1+1/\mathrm{\ell }})$ 分别对应每个 $\mathrm{\ell }⩾2$。 人们普遍认为，每当 $s⩽t$ 和 $\mathrm{ex}(n,C_{2\mathrm{\ell }})=\mathrm{\Omega }(n^{1+1/\mathrm{\ell }})$ 时，$\mathrm{ex}(n,K_{s,t})=\mathrm{\Omega }(n^{2-1/s})$ 都可能是最好的结果。 最后，我们提到本段中提到的大多数结果的证明使用引理 1 的变体或将 2 节中提出的想法扩展到超图，请参阅第 4.2 节。

定理证明8。

请注意，可以将每个 $n$-顶点图 $G$ 的顶点排序为 $v_1,\mathrm{\dots },v_n$，对于每个 $i\in \{2,\mathrm{\dots },n\}$，让$G_i=G[\{v_1,\mathrm{\dots },v_i\}]$，

$$\delta (G_{i-1})⩾{\mathrm{deg}}_{G_i}(v_i)-1.$$

事实上，可以通过迭代地让$v_i$为$i=n,\mathrm{\dots },2$的$G-\{v_{i+1},\mathrm{\dots },v_n\}$的最小度数顶点来获得这样的排序。 特别地，每个标记的$n$-顶点图$G$可以通过以下方式构造。 首先，选择顶点的排序$v_1,\mathrm{\dots },v_n$，并让$G_1$为具有顶点集$\{v_1\}$的空图。 其次，对于每个 $i\in \{2,\mathrm{\dots }n\}$，通过向图形 $G_{i-1}$ 添加一个标记为 $v_i$ 的顶点来构建图形 $G_i$，其方式如下：度$d_i$（在$G_i$中）满足$d_i⩽\delta (G_{i-1})+1$。 最后，我们让$G=G_n$。 观察到 $G$ 是 $C_4$ 自由的，当且仅当 $G_i$ 对于每个 $i$ 都是 $C_4$ 自由的。

现在，给定整数 $d$ 和 $i$ 以及 $d⩽i$，令 $g_i(d)$ 表示附加度数为 $d$ 到一个无 $i$ 顶点 $C_4$ 的图，最小度数至少为 $d-1$，结果图仍为 $C_4$-免费。 这个数字被明确定义为$g_i(d)⩽\left(\genfrac{}{}{0pt}{}{i}{d}\right)$。 此外，设$g_i=\max \{g_i(d):d⩽i\}$。 上一段给出的论证证明

$$f_n(C_4)⩽n!\cdot n!\cdot \prod _{i=2}^n{g}_{i-1}.$$ (15)

确实有$n!$ 将 $[n]$ 排序为 $v_1,\mathrm{\dots },v_n$ 的方法，对于每个这样的排序，最多有 $n!$ 度数序列 $d_2,\mathrm{\dots },d_n$ 的选择。 鉴于(15)，下面的主张很容易暗示该定理的断言。

Claim。

存在一个常量$C$，使得所有$n$的$g_n⩽\exp (C\sqrt{n})$。

不失一般性，我们可以假设$n$很大。 因此，如果$d⩽\sqrt{n}/\log n$，那么

$$g_n(d)⩽\left(\genfrac{}{}{0pt}{}{n}{d}\right)⩽\left(\genfrac{}{}{0pt}{}{n}{\frac{\sqrt{n}}{\log n}}\right)⩽{\left(e\sqrt{n}\log n\right)}^{\frac{\sqrt{n}}{\log n}}⩽\exp (\sqrt{n}).$$

因此，我们从现在开始假设$d>\sqrt{n}/\log n$。 令 $G$ 为具有 $\delta (G)⩾d-1$ 的 $n$ 顶点上的 $C_4$ 无图。 令 $H$ 为 $G$ 的平方，即具有 $V(H)=V(G)$ 的图形，

$$E(H)=\{xy:xz,yz\in E(G)\text{for some}z\in V(G)\}.$$

重要的是，如果且仅当 $v$ 的邻域是 $H$ 中的独立集合时，将 $v$ 添加到 $G$ 将产生一个无 $C_4$ 的图。因此，$i(H,d)$ 是 $G$ 的顶点度数为 $d$ 的无 $C_4$ 扩展的数量上限。我们将使用定理 1 估计 $i(H,d)$。

为此，我们证明由 $V(H)$ 的大子集引起的 $H$ 子图具有相当高的密度。 由于 $G$ 与 $C_4$ 无关，因此 $H$ 的每条边 $xy$ 都对应一个唯一的顶点 $z\in V(G)$，这样$xz$和$yz$是$G$的边缘。因此，对于每个$B\subseteq V(H)$，

$$e_H(B)=\sum _{z\in V(G)}\left(\genfrac{}{}{0pt}{}{{\mathrm{deg}}_G(z,B)}{2}\right)⩾n\cdot \left(\genfrac{}{}{0pt}{}{\sum _z\mathrm{deg}(z,B)/n}{2}\right),$$

其中最后一个不等式是应用于凸函数 $x\mapsto \left(\genfrac{}{}{0pt}{}{x}{2}\right)$ 的 Jensen 不等式。 自从

$$\sum _{z\in V(G)}{\mathrm{deg}}_G(z,B)=\sum _{x\in B}{\mathrm{deg}}_G(x)⩾|B|\cdot \delta (G)⩾(d-1)|B|,$$

然后假设 $|B|⩾\frac{2n}{d-1}$ 意味着

$$e_H(B)⩾n\cdot \frac{(d-1)|B|}{2n}\left(\frac{(d-1)|B|}{n}-1\right)⩾\frac{{(d-1)}^2}{2n}\left(\genfrac{}{}{0pt}{}{|B|}{2}\right).$$

最后，让$R=\frac{2n}{d-1}$、$\beta =\frac{{(d-1)}^2}{2n}$和$q=\lceil 3{(\log n)}^3\rceil$。 由于 $d>\sqrt{n}/\log n$ 和 $n$ 较大，因此 $\beta q⩾\log n$ 较大，因此 $e^{-\beta q}n⩽1⩽R$ 也较大。 如果从引理 1 得出

$$i(H,d)⩽\left(\genfrac{}{}{0pt}{}{n}{q}\right)\left(\genfrac{}{}{0pt}{}{\frac{2n}{d-1}}{d-q}\right)⩽e^{4{\log }^{4}n}\cdot {\left(\frac{2en}{{(d-q)}^2}\right)}^{d-q}⩽\underset{k>0}{sup}{\left(\frac{e\sqrt{n}}{k}\right)}^{2k}=e^{2\sqrt{n}},$$

我们使用 $n$ 很大的假设和 $sup\{{\left(\frac{e}{x}\right)}^x:x>0\}=e$ 的事实。 ∎

3.5. 随机集中的罗斯定理

作为我们的最后一个例子，我们提供了 Kohayakawa、Łuczak 和 Rödl [28] 众所周知的结果的简短证明。 回想一下，$[n]$ 表示集合 $\{1,\mathrm{\dots },n\}$。 Roth 的一个著名定理 [34] 断言，对于每个正 $\delta$，任何来自 $[n]$ 的至少 $\delta n$ 个整数的集合都包含$3$ 项算术级数($3$ 项 AP），前提是 $n$ 足够大（仅作为 $\delta$ 的函数）。 给定正 $\delta$，我们可以说集合 $A\subseteq \mathbb{Z}$ 是 $\delta$-Roth 如果每个 $B\subseteq A$满足$|B|⩾\delta |A|$包含$3$项AP。 现在我们可以将罗斯定理重述如下。 对于每个正数$\delta$，都存在一个$n_0$，使得只要$n⩾n_0$，集合$[n]$就是$\delta$-Roth 。 为了表明存在“更小”和“更稀疏”$\delta$-Roth 集 Kohayakawa、Łuczak 和 Rödl [28] 证明了以下结果。

Theorem 9 ([28]).

对于每个正$\delta$，都存在一个常数$C$，这样如果$C\sqrt{n}⩽m⩽n$，则均匀选择的随机$m$元素的概率$\{1,\mathrm{\dots },n\}$ 的子集是 $\delta$ - Roth 倾向于将 $1$ 视为 $n\to \mathrm{\infty }$。

我们将推导出定理 9 作为以下上限的简单推论，该上限是给定基数的 $[n]$ 的子集数量，不包含 $3$ -term AP，最初在 [7] 和 [39] 中以更通用的形式证明。 该上限将使用引理 2 以及之前在 [2] 中考虑过的一个附加扭曲从罗斯定理中导出。

Theorem 10。

对于每个正数 $\epsilon$，都存在一个常数 $D$，这样如果 $D\sqrt{n}⩽m⩽n$，

$$\left|\{A\subseteq [n]:|A|=m\text{and}A\text{contains no}3\text{-term AP}\}\right|⩽\left(\genfrac{}{}{0pt}{}{\epsilon n}{m}\right).$$

定理证明9。

固定一个正数$\delta$，令$\epsilon =\delta /6$，并令$D$为定理10陈述中的常数。 让 $C=D/\delta$ 并假设 $C\sqrt{n}⩽m⩽n$。 由于$\lceil \delta m\rceil ⩾D\sqrt{n}$，定理10意味着集合$𝒜$定义为

$$𝒜=\{A\subseteq [n]:|A|=\lceil \delta m\rceil \text{and}A\text{contains no}3\text{-term AP}\}$$

至多有 $\left(\genfrac{}{}{0pt}{}{\epsilon n}{\lceil \delta m\rceil }\right)$ 元素。 现在，令 $R$ 为随机均匀选择的 $[n]$ 的 $m$ 元素子集。 清楚地，

我们的定理 10 证明将使用罗斯定理的以下简单推论，首先由 Varnavides [44] 观察到，作为“黑匣子”。

Proposition 11 ([34, 44]).

对于每个正数 $\delta$，都存在一个整数 $n_0$ 和一个正数 $\beta$，这样，如果 $n⩾n_0$，那么从 $\{1,\mathrm{\dots },n\}$ 开始的每个至少包含 $\delta n$ 整数的集合都至少包含 $\beta n^2$ $3$项 AP。

定理证明10。

固定一个正数 $\epsilon$，让 $n_0$ 和 $\beta$ 是命题 11 的陈述中用 $\delta =\epsilon /2$ 调用的常数，并假设 $n⩾n_0$。 给定任意集合 $B\subseteq [n]$ 和整数 $m$ 和 $n^{\prime }$，令

$a(B,m)$ $=\left|\{I\subseteq B:|I|=m\text{and}I\text{contains no}3\text{-term AP}\}\right|,$

$a(n^{\prime },m)$ $=\max \left\{a(B,m):B\subseteq [n]\text{with}|B|=n^{\prime }\right\}.$

我们的目标是证明 $a([n],m)=a(n,m)⩽\left(\genfrac{}{}{0pt}{}{\epsilon n}{m}\right)$，前提是 $m⩾C\sqrt{n}$ 对于某个仅依赖于 $\epsilon$ 的常量 $C$。 这种不等式可以从对所有 $n^{\prime }$ 和 $m$ 的 $a(n^{\prime },m)⩽\left(\genfrac{}{}{0pt}{}{n^{\prime }}{m}\right)$ 的简单观察以及以下声明得出。

Claim。

如果$n^{\prime }⩾\epsilon n/2$和$m⩾2\lfloor \sqrt{n}\rfloor$，则$a(n^{\prime },m)⩽2{\left(\genfrac{}{}{0pt}{}{n}{\lfloor \sqrt{n}\rfloor }\right)}^2\cdot a(n^{\prime }-\lceil \beta n/12\rceil ,m-2\lfloor \sqrt{n}\rfloor )$。

令 $\mathscr{H}$ 为 $3$ 均匀超图，其顶点集 $[n]$ 的边都是形成 $3$ 项 AP 的数字三元组。 令 $B$ 为 $[n]$ 的任意 $n^{\prime }$ 元素子集。 根据命题11,$e_{\mathscr{H}}(B)⩾\beta n^2$。 设$Z\subseteq B$为$\mathscr{H}[B]$的所有顶点的集合，$\mathscr{H}$由$B$导出的子超图，其度至少为$\beta n$。 换句话说，$Z$是$B$中至少属于$B$中包含的$\beta n$个三项AP的所有数字的集合。 由于 $\mathscr{H}$ 的最大次数最多为 $2n$，因此我们有 $|Z|⩾\beta n$。

我们首先估计 $B$ 的 $m$ 元素子集的数量，其中没有 $3$ 项 AP 包含少于 $\sqrt{n}$ 元素的 $Z$。 由于每个这样的集合$A$可以分为$A_1$和$A_2$，其中$|A_1|=\lfloor \sqrt{n}\rfloor$和$A_2\subseteq B\setminus Z$，有至多 $\left(\genfrac{}{}{0pt}{}{n}{\lfloor \sqrt{n}\rfloor }\right)\cdot a(n^{\prime }-\lceil \beta n\rceil ,m-\lfloor \sqrt{n}\rfloor )$ 这样的集合。 因此，我们可以重点关注至少包含 $Z$ 的 $\sqrt{n}$ 元素的 $B$ 子集的计数。 我们将使用引理 2 获得其数量的合适上限。

令$W$为$Z$的任意子集，并考虑具有顶点集$B$的辅助图$G_W$，其边都是对$\{x,y\}$ 使得$\{x,y,z\}\in \mathscr{H}$ 适合某些$z\in W$。 由于对于给定的对$\{x,y\}\subseteq [n]$，最多有三个不同的$z$，使得$\{x,y,z\}\in \mathscr{H}$，因此可以得出$e(G_W)⩾|W|\beta n/3$和最大度数$G_W$ 不超过 $3|W|$。 由此可见，对于 $B$ 的任意子集 $U$ 且至少具有 $n^{\prime }-\beta n/12$ 元素，

$$e_{G_W}(U)⩾e(G_W)-|B\setminus U|\cdot \mathrm{\Delta }(G_W)⩾\frac{\beta n|W|}{3}-\frac{\beta n}{12}\cdot 3|W|=\frac{\beta n|W|}{12}.$$ (16)

关键的是，如果某个集合 $I\cup W$ 不包含 $3$ 项 AP，则 $I$ 是图中 $G_W$ 中的一个独立集合。

让 $w=\lfloor \sqrt{n}\rfloor$ 并用 $|W|=w$ 修复一些 $W\subseteq Z$ 。 我们将证明将 $W$ 扩展到 $B$ 的 $m$ 元素子集（不包含 $3$)的方式数量上限> 期限 AP。 通过我们上面的讨论，如果$I\cup W$是这样一个集合，那么$I$就是$G_W$与$m-w$元素的独立集合。 令 $𝒮$ 为集合族，并令 $f$ 和 $g$ 为映射，其存在由引理 2 和 $G=G_W$、$q=\lfloor \sqrt{n}\rfloor$、$R=n^{\prime }-\lceil \beta n/12\rceil$ 和 $D=\beta w/6$。 请注意，我们上面的讨论满足了引理的假设，请参见 (16)。 由于显然对于 $W$ 的每个扩展 $I$ 到 $B$ 的 $m$ 元素子集，没有 $3$ - term AP，$I\cap f(g(I))$不包含$3$term AP，$W$的扩展数量$E_W$满足

$$E_W⩽\sum _{S\in 𝒮}a(f(S),m-w-q)⩽\left(\genfrac{}{}{0pt}{}{n}{q}\right)\cdot a(R,m-w-q).$$

我们的结论是

由于 $B$ 是 $[n]$ 的任意 $n^{\prime }$ 元素子集，因此证明了这一说法。

让 $K=\lceil (12-6\epsilon )/\beta \rceil$ 并假设 $m⩾\sqrt{n}$。 我们递归调用声明 $K$ 次以获得

$$a(n,m)⩽2^K{\left(\genfrac{}{}{0pt}{}{n}{\lfloor \sqrt{n}\rfloor }\right)}^{2K}\left(\genfrac{}{}{0pt}{}{\epsilon n/2}{m-2K\lfloor \sqrt{n}\rfloor }\right)⩽2^K\left(\genfrac{}{}{0pt}{}{2Kn}{2K\lfloor \sqrt{n}\rfloor }\right)\left(\genfrac{}{}{0pt}{}{\epsilon n/2}{m-2K\lfloor \sqrt{n}\rfloor }\right).$$ (17)

如定理 7 的证明，用 $r(t)$ 表示 (17) 的右侧，并将 $2K\lfloor \sqrt{n}\rfloor$ 替换为$t$。根据罗斯定理，我们可以清楚地假设 与 $a(n,m)=0$ 不同（我们可以假设 $n$ 足够大）。 初步计算表明

$$\frac{r(t+1)}{r(t)}=\frac{2Kn-t}{t+1}\cdot \frac{m-t}{\epsilon n/2-m+t+1}⩽\frac{2Knm}{(t+1)(\epsilon n/2-m)}⩽\frac{8Km}{\epsilon (t+1)}$$

因此，让$T=2K\lfloor \sqrt{n}\rfloor$，

$$a(n,m)⩽r(T)⩽2^K\cdot \frac{{(8Km)}^T}{{\epsilon }^{T}T!}\cdot \left(\genfrac{}{}{0pt}{}{\epsilon n/2}{m}\right)⩽2^K\cdot {\left(\frac{8eKm}{\epsilon T}\right)}^T\cdot {\left(\frac{1}{2}\right)}^m\left(\genfrac{}{}{0pt}{}{\epsilon n}{m}\right).$$

最后，如果 $D$ 作为 $K$ 和 $\epsilon$ 的函数足够大，那么对于每个 $m$ 和 $m⩾D\sqrt{n}⩾D/(2K)\cdot T$，我们有

$$2^{K/m}\cdot {\left(\frac{8eKm}{\epsilon T}\right)}^{T/m}⩽2,$$

从而完成了定理的证明。 ∎

4. 结束语和进一步阅读

4.1. 克莱特曼-温斯顿方法的其他应用

除了 3 节中介绍的方法之外，Kleitman-Winston 方法还有很多成功的应用。 特别是，以下著作中使用了定理 1 的变体：Kleitman 和 Wilson [24] 证明了周长大于 $2\mathrm{\ell }$ 的 $n$ 顶点图的数量为 $2^{O(n^{1+1/\mathrm{\ell }})}$；Dellamonica、Kohayakawa、Lee、Rödl 和作者 [13，14，27] 证明了具有给定心数的 $[n]$ 子集的数目的尖锐边界，对于每个 $h⩾2$，这些子集不包含方程 $a_1+\mathrm{\dots }+a_h=b_1+\mathrm{\dots }+b_h$ 的非小解；Balogh、Das、Delcourt、Liu 和 Sharifzadeh [6]以及 Gauy、Hàn、和奥利维拉 [17]证明了具有给定心数的 $[n]$ 元素子集 $k$ 的相交族的数目，以及 $k$ 元素子集 $[n]$ 的随机集合中包含的最大相交子族的典型大小的锐界。

4.2. 克莱特曼-温斯顿方法对超图的扩展

寻求克莱特曼-温斯顿方法的推广似乎很自然，该方法将为更高均匀性的超图中的独立集合的数量产生非平凡的上限。 也许有些令人惊讶的是，这种概括直到最近才被考虑。 据我们所知，这是首先在 [8, 9] 中完成的，其中 $n$ 顶点图的数量有明显的上限，这些顶点图不包含使用 3.4 节中提出的论证的推广来证明固定的完整二分子图。 大约在同一时间，Saxton 和 Thomason 提出了类似的想法，他们用它们来建立正则一致超图的列表色数的下界[40]。 受到 Conlon 和 Gowers [12] 以及 Schacht [41] 开创性工作的启发，这些努力最终将 Kleitman-Winston 方法广泛推广到任意一致超图，由 Saxton 和 Thomason [39] 以及 Balogh、Morris 和作者 [7] 独立获得。 如需了解更多详细信息，感兴趣的读者请参阅[7,11,12,35,39,41]。

致谢。 我要感谢 Noga Alon、Józsi Balogh、Domingos Dellamonica、Yoshi Kohayakawa、Sang June Lee、Rob Morris 和 Vojta Rödl，他们就图中的独立集、Kleitman-Winston 方法及其应用等主题进行了许多有趣的讨论。过去几年。 这些讨论极大地影响了本文的内容。 我还要感谢戴维·康伦 (David Conlon)、阿萨夫·费伯 (Asaf Ferber) 和罗布·莫里斯 (Rob Morris) 仔细阅读了这份手稿的早期版本，并提出了许多宝贵的意见，这些意见帮助我改进了阐述，并避免了我犯下一些令人尴尬的错误。 最后，特别感谢 Jarik Nešetřil 鼓励我们撰写这份调查报告。