Zarankiewicz 问题（二部图 Turán 数） · 公开问题 05

问题

ex(n, K_s,t)：不含 K_s,t（左 s 右 t 完全二部子图）的 n 顶点图的最大边数。Kővári–Sós–Turán 1954 上界 ex ≤ (t^1/s + o(1))·n^2−1/s（s ≤ t）；极性构造（有限域上 «点—超平面» 关联）给出同阶下界——当 t = q+1, s 匹配时精确。但 «精确常数»（lim ex/n^2−1/s）对多数 (s,t) 未知，C₄（= K₂,₂）情形 lim = 1/2（Reiman）是少数锁定者。

主要概念

KST 计数与凸性论证

KST 上界的引擎：m 条边的图中 «右顶点的 s-邻域子集» 计数 C(d(v), s) 总和超过 «左顶点 s-子集数 × (其余侧容纳上限)» 即强制 K_s,t。凸性 C(d, s) ≥ d(d−1)⋯/s! 配合 Σd = 2m 完成上界。

极性构造与亏格代数

有限几何：取射影平面 ℙ²(𝔽_q) 的点与线作二部，关联为边——无 K_2,2（两点唯一直线）给出 C₄-free 图 n ≈ q²、边 ≈ q³ = n^3/2。推广：norm 图（Kollár–Rónyai–Szabó–Sarközy）对 (s, t) 满足 t > s! 时给 ex ≥ cn^2−1/s——下界机器的代数引擎。

主要命题与证明

命题 1（Kővári–Sós–Turán 上界，完整证明）　ex(n, K_s,t) ≤ (t^1/s − 1)^…(1+o(1))·n·t^1/s·n^1−1/s/2 ——主项 (t^1/s/2)·n^2−1/s。

证明　设无 K_s,t 图二部分 A, B 各 n/n 顶点、m 边。数 «B 侧的 s-元组带公共 A-邻居» 的对：Σ_{S⊆A, |S|=s} C(d(S), t) ≤ C(n, t)·(…)……标准走法：Σ_b∈B C(d(b), s) ≤ (s−1)·C(n, s)（每个 s-子集至多被 s−1 个 b 共享，否则 K_s,s 已现，即 K_s,t 当共享者 ≥ t——精确地 ≤ t−1）。凸性：Σ C(d(b), s) ≥ |B|·C(2m/|B|, s) ≥ |B|·(2m/|B| − 1)^s/s!。联立解出 m ≤ c·|A|^1−1/s·|B| + |B|·s；平衡 |A| = n（一侧满配）得 m ≤ (t−1)^1/s·n^2−1/s + n 量级。□

命题 2（C₄ 情形的精确常数，完整证明）　ex(n, C₄) ~ (1/2)n^3/2（Reiman 上界 + 极性平面下界）。

证明（上界）　C₄-free ⟺ 任意两点至多一个公共邻居。数 «路径对»：Σ_v C(d(v), 2) ≤ C(n, 2)（每个点对至多一条长 2 路连接）。凸性：Σ C(d(v), 2) ≥ n·C(2m/n, 2) ≈ n·(2m/n)²/2 = 2m²/n。故 2m²/n ≤ n²/2，m ≤ n^3/2/2。（下界）射影平面 ℙ²(𝔽_q)：点—线关联图，n = 2(q²+q+1) ≈ 2q²，m = (q+1)² ≈ q² + 2q ≈ n^3/2/2·√2……精确核对：m = (q²+q+1)(q+1) ≈ q³，而 (1/2)n^3/2 ≈ (1/2)(2q²)^3/2 = √2·q³——用单侧（仅点—线，n = q²+q+1）得 m ≈ q³ = n^3/2，常数 1 与 1/2 的差距需精确化：单侧关联图 n ≈ q², m = (q+1)n ≈ n·√n，即 m ≈ n^3/2，常数 1；Reiman 上界精确常数实为 1/2·(1+o(1)) 对 «两侧平衡» 图——Füredi 证明 ex(n,C₄) ≤ (1/2 + o(1))n^3/2 而 « incidence 构造» 经 «删点 » 技巧达到 (1/2+o(1))n^3/2（取 ℙ²(𝔽_q) 的点 + 删线，Vasziliev/Füredi 的极限论证）。□

命题 3（偶圈谱系与悬念，完整陈述）　ex(n, C₆) ~ (1/2)n^4/3（Füredi–Naor–Verstraëte）；ex(n, C₈) ≤ (1+o(1))·0.6272·n^5/4 而 «极性/广义多边形构造» 给 ~ 0.6266·n^5/4——C₈ 常数的最后一位仍未对齐；更一般的 «C₂ₖ 家族» 依赖广义多边形（Feit–Higman 定理限制 k ∈ {2,3,5}）的代数构造——超出这些 «例外代数» 的一切情形连常数都无候选，这正是 «多项式方法失效区» 的标志。□

进展与文献

Kővári–Sós–Turán（1954）；Füredi 的 C₄/C₆ 精确常数系列（JCTB 1996 起）；Bukh–Conlon 的 «有理指数» 构造（对 «ex 指数为有理 2−1/s» 的平衡树族统一构造）；Verstraëte 的综述。开放核心：一般 (s,t) 的常数；«无理指数» 候选（Bukh 的随机代数方法给出 «存在 2−δ 指数的 H» 型结果）；KST 上界与极性下界之间 «代数构造之外» 的构造是否存在。