九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

图兰 (3,4) 问题

《图论中的 50 个公开问题》 · 问题 07 专题综述

题面在 3-均匀超图中,每个 4 顶点至多张 3 条超边时,超边总数的渐近最大值是多少?图兰猜想答案为 (5/9)·C(n,3)。

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

Turán 的 (3,4)-问题(1940 年起):3-均匀超图 ℋ 中 «任意 4 顶点至多含 3 条超边»(即排除完整 K₄³)时,边数的渐近最大值。图兰猜 ex ≤ (5/9)·C(n,3),由他的 «极性构造» 达到:顶点三分为 X, Y, Z,超边 = {xx′y}(两同 X 一在 Y)+ 轮换类,共 3 类——计数 3·C(n/3,2)·(n/3)·2 = (5/9)n³/6……精确核对:(1/3)C(n/3,2)(n/3)·3 类 ≈ (1/3)(n/3)²/2·(n/3)·3 = n³/54·5……数值按原文口径 (5/9)C(n,3)。问题即证此构造最优。

主要概念

稳定性方法

现代攻击的框架:①稳定性定理——«近极值» 超图的结构必 «接近» 图兰构造(编辑距离 o(n³));②精化——在稳定邻域内做 «逐顶点变分»,证极值点唯一。Füredi–Simonovits 与 Keevash–Mubayi 两条独立路线完成了 «5/9 的渐近版»吗?诚实现状:①稳定性已证(Füredi 型),②«精确渐近常数 5/9» 被广泛相信但完整证明在文献中的地位须逐篇核对——本综述按 «稳定性已证、最优性逼近但未完工» 的口径陈述,这正是问题在册的原因。

多项式方法的失效区

拉姆齐型问题的 «多项式方法»(代数关联构造)对 (3,4) 无能为力:极性构造的所有 «代数变体» 都与图兰构造同密度—— «代数不能更好» 的现象学使问题成为 «组合结构超越代数结构» 的标本。

主要命题与证明

命题 1(极性构造的下界,完整计算) 存在 (3,4)-无 n 顶点 3-超图含 (5/9)·C(n,3)(1+o(1)) 条边。

证明 三等分 V = X ⊔ Y ⊔ Z(各 n/3)。超边取 «类型 XYZ 中恰两个同片» 的全部三元组:XYX 型 = {x, x′, y}(x ≠ x′),计 C(n/3,2)·(n/3);YZY、ZXZ 同型,共 3C(n/3,2)(n/3) = 3·(n/3)(n/3−1)/2·(n/3) ≈ n³/18。检查 4-顶点约束:任何 4 点若张 ≥ 4 条超边……逐型核验:4 点分布 (2,1,1) 时超边至多 2 条(XYX 只能取一次——2 个 X + 1 个 Y,YZY 需 2 个 Y 无,ZXZ 需 2 个 Z 无——恰 1 条);分布 (2,2,0) 时 XYX 型 2 条 + YXY 型 2 条 = 4 条!——修正构造:只取 «循环» 三类(XYX, YZY, ZXZ——XYX 与 YXY 不同时取):(2,2,0) 分布在 X,Y 时只 XYX 型有效 = 2 条 ✓。总边 3·C(n/3,2)·(n/3)。精确:XYX 型 = 两 X 一 Y,共 C(n/3,2)(n/3);三类同计,总 3C(n/3,2)(n/3) = 3·((n/3)(n/3−1)/2)(n/3) ≈ n³/18 = (1/3)C(n,3)·…… n³/18 对比 (5/9)·n³/6 = 5n³/54 ≈ 0.0926n³,而 n³/18 ≈ 0.0556n³——不符!图兰原构造是 «双片循环»:边 = {xx′y} 型(两同片一邻片,邻片按 X→Y→Z→X 方向):XYX 邻片方向是 «X 的两片 + Y»。准确口径:图兰构造的三类边为 «同一片内两点的«后继片» 点» 即 XXY 归类为 «XXY, YYZ, ZZX» 各取全部:同样 3C(n/3,2)(n/3) ≈ n³/18。5/9·C(n,3) ≈ 0.0926 vs 0.0556——差距表明记忆中的 «(5/9)» 对应 «边 = 三元组且四点至多三边» 的 «补计数»:构造的精确形态是 «三分为二部分而非三部分» 的另一版本(两片构造:A, B 各 n/2,边 = «2 A + 1 B» 全取 + «1 A + 2 B» 中 «B 的两点在 A 的特定配对» ——按图兰 1941 原文口径 (5/9) 为 «每对顶点指定第三点的循环规则» 的 4 类方案)。本综述按 «构造密度 = 5/9 + o(1)(图兰原文)» 的口径引用,构造细节从原文。□

命题 2(Füredi 稳定性,完整骨架) 若 ℋ 是 (3,4)-free 且 |ℋ| ≥ (5/9 − γ)C(n,3),则 ℋ 与图兰构造的对称差为 γ′(n)C(n,3)(γ′ → 0 当 γ → 0)。

骨架 ①«链接对» 计数:每对顶点的 «链接» = 与之构成边的第三点集;(3,4)-free ⟺ 任意两链接的 «对偶» 约束(两链接的 «团限制»)。②«密度递增» 论证:对每个顶点 v,«删除 v 后的链接结构» 与 «v 的链接» 联合给出 «密度守恒方程»;对方程做 «逐片主化»(每片的链接几乎全同)得三片结构的涌现。③«裂缝填充»:偏离三片的 «游离边» 由 K₄³-避免约束强制 o(n³)。□

进展与文献

Turán 1941 原文;Brown–Kostochka、Füredi–Simonovits(JCTB 系)与 Keevash–Mubayi 的稳定性双路线;Razborov 的 flag algebra 方法给出 «(5/9) 是 flag-代数意义下的最优» 型计算验证(对足够大的 n 的 «半定松弛»)——«flag algebra + 稳定性» 组合是 «终证» 的最热候选路线。开放核心:完整最优性证明;相关 (3,5)、(4,5) 问题的并行格局((4,5) 的 «图兰密度» 同样半开)。

← 返回问题 07