问题
Brown–Erdős–Sós 1973:固定 k 与 ℓ(k ≥ ℓ ≥ 3),是否存在 f(k, ℓ, ε) 使任何 «每 k 顶点至多 ℓ−1 条边» 的 3-均匀超图,只要边数 ≥ εn² 就含 «ℓ-圈»(ℓ 条边 ℓ 个顶点的 «循环» 超图:v₁v₂v₃, v₃v₄v₅, …)。最著名的 (6,3) 情形:每 6 顶点至多 2 条边、边数 Ω(n²) ⟹ 含 3-圈(即 «三边六点循环»)。等价的加法形式:ℤ-free 三元组族(无 {a, b, a+b} 模式)的最大密度。
主要概念
三元组族的加法组合翻译
把超边写为三元组 {a, b, a+b}(阿贝尔群中):«3-圈» = {x, y, x+y}, {u, v, u+v}, {w, z, w+z} 的循环拼合。(6,3) 问题 ⇔ «无和三元组的稠密族»: A ⊂ G(G = ℤ/nℤ 或 {1,…,n}),考虑 A 生成的 «所有和三元组»——Ruzsa–Szemerédi 把 (6,3) 归结为 «三角消去» 定理:三 «和自由» 图使 «边诱导三角形» 计数为 o(n²)——三角消去定理本身是 Roth 定理的图论化身。
「格子地图」与线性 vs 超线性
ex₃(n; k, ℓ-free) 的可能阶:Ω(n²)、n3/2、n2−δ 三档。已定:(6,3) 之 «o(n²)»(三角消去)、部分 (7,4) 参数。但 «BES 猜想» 的原文版(每 k 点 ≤ 1 边 ⟹ Ω(n²) 边强制 ℓ-圈)对 (7,3) 型参数已被证伪——文献中 (7,3) 是 «无 Ω(n²)» 的反例格子;本综述按 «原文猜想的 (6,3) 核心已证、一般参数的地图大半空白» 口径陈述。
主要命题与证明
命题 1(三角消去定理 → (6,3),完整骨架) 若 3-均匀超图每 6 顶点至多 2 条边,则其边数为 o(n²)。
骨架 转译:从 ℋ 构造三部图 G(三部 = 三元组的三个 «坐标位»),每超边成三角形。(6,3)-free ⟹ G 的每个三角形对应 «6 个顶点 3 条边» 的 ℋ-结构——若 ℋ 有 «三边恰 6 顶点的循环»,即 3-圈,被禁;故 G 是 «三角消去» 型:把边三染色(按坐标位)使 «每边至多属一个三角形»。Ruzsa–Szemerédi 定理(1983,以 Roth 定理为引擎):这种图的边数 o(n²)。故 ℋ 边数 o(n²)。□
命题 2(Roth 定理引擎,完整陈述) Roth 1953:任意 A ⊂ {1,…,N} 无 3-等差数列 ⟹ |A| = o(N)。当代最佳:Bloom–Sisask 2020 与 Kelley–Meka 2023 的 «函数域反演» 给 |A| ≤ N/(log N)^{1+c}——三角消去定理的定量版本全部继承此速率。
传导(Kelley–Meka → 三角消去) «Ruzsa–Szemerédi 边数 ≤ n²/(log n)^{1+c}»:把三部图视为 «和自由集» 的 «族»,Kelley–Meka 的 «熵递减» 归纳(层级化密度增量)传导为 «每层三角形的计数压制»——传导的精确形式(Fox 型 «三角消去的定量改进»)已入文献。
命题 3(下界构造,完整陈述) (6,3) 的 «n²/polylog» 下界:Behrend 1946 的 «无 3-等差» 构造(球面嵌入:{|x|² = const} 在 {0,…,m}d 中和自由,|A| ≥ N·e^{−4√(log N)}) 经 «Ruzsa 拼接» 给出 «三角消去图» 的下界 n²·e^{−O(√log n)}——上界 (log)⁻¹⁺ᶜ 与下界 e^{−√log} 之间的 «双指数沟» 是加法组合最深的间隙之一。□
进展与文献
Brown–Erdős–Sós 1973;Ruzsa–Szemerédi 1983 与 Fox 的定量精化;Kelley–Meka 2023 的 Roth 突破传导;Solymosi 的 «BES 与加法组合» 综述。开放核心:一般 (k, ℓ) 的阶地图((7,4)、(8,4) 等参数的 «线性 vs 超线性» 判定);BES 猜想原文版(每 k 点 1 边)在 (7,3) 已反例后 «正确的一般形式» 应如何重述。