3. 然后呢?

我们的目标之一是理解 Roth 定理的两种不同证明, Roth 定理可以改写为:

定理 3.1 (Roth 定理). $[N]$ 中不包含长度为 3 的等差数列的子集的大小一定为 $o(N)$.

Roth 最初使用 Fourier 分析技术证明了他的结果, 我们将在本书的后半部分看到. 1978 年, 在 Szemerédi 证明其具有里程碑意义的结果之前, Szemerédi 提出了一个称为图正则性引理的重要工具. Ruzsa 和 Szemerédi 使用图正则性引理给出了 Roth 定理的新图论证明 (1978) . 我们的首要目标之一是理解这个图论证明. 正如在 Schur 定理的证明中一样, 我们将构造一个图论问题, 解决了该问题就意味着解决了 Roth 定理. 这一话题应当称为组合学领域中的极值图论, 极值图论的起源 (历史上和教学上) 是以下问题:

问题 3.2. $n$ 个顶点的无三角形图最多可以有多少条边?

这个问题相对简单, Mantel 在 20 世纪早期回答了这个问题 (后来被 Turán 重新发现和概括) . 这将是我们接下来要解决的第一个问题. 然而, 尽管听起来与 Roth 定理相似, 但它不能用于推导出 Roth 定理. 稍后, 我们将构建一个对应于 Roth 定理的图, 正确的问题是:

问题 3.3. 每条边都包含在一个唯一三角形中的 $n$ 顶点图的最大边数是多少?

这个看似简单的问题竟然是不可思议的神秘. 我们离了解真相还很远. 我们稍后将使用 Szemerédi 的正则性引理证明, 任何这样的图都必须有 $o\left(n^2\right)$ 边, 然后我们将从这个图论断言中推导出 Roth 定理.