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

图兰数 T(n,5,4) 及超图图兰问题

《组合设计中的 50 个公开问题》 · 问题 07 专题综述

题面最小多少个 4-子集能击中每个 5-子集——T(n,5,4) 的精确渐近常数是多少?

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

问题

图兰数 T(n,k,t)(覆盖口径):最少多少个 t-子集,使每个 k-子集至少含有一个(击中性质)。本问题聚焦 T(n,5,4):击中所有 5-子集的最少 4-子集族。它与 «k-一致超图图兰问题» 互为补集:设 𝒢 为全体 4-子集中不属于击中族的那些,则 «每个 5-子集含一个击中块» ⟺ 𝒢 不含任何 K₅⁴(5 个顶点上全部 5 个 4-面皆属 𝒢 的配置)。于是 T(n,5,4) = C(n,4) − ex(n,K₅⁴),而 ex/n⁴ 的极限(图兰密度 π(K₅⁴))正是超图图兰问题的圣杯级未知量——它与图论分册 07 号的 K₄³ 问题同族。图兰本人 1941 年给出的构造(击中族的显式方案)至今未被任何改进压低;其最优性五十年未证。

主要概念

补集恒等式

击中族 𝒯 与 «自由» 族 𝒢 = 全体 4-子集 ∖ 𝒯 的关系:每个 5-子集 S 的 5 个 4-面中至少一个在 𝒯 ⟺ 没有任何 5-子集的 5 个 4-面全在 𝒢 ⟺ 𝒢 是 K₅⁴-自由。故最小化 |𝒯| = 最大化 |𝒢|:T(n,5,4) 与 ex(n,K₅⁴) 是同一枚硬币的两面。推论:π(K₅⁴) 已知 ⟺ T(n,5,4) 的渐近常数已知;一般超图图兰密度 π(ℋ) 的存在性(lim ex/nr)由 Katona–Nemetz–Simonovits 保证,故渐近常数存在、只是值未知。

超图图兰的一般格局

图(2-一致)情形由图兰定理完全解决;超图(≥3-一致)几乎全部打开:图兰 (3,4) 问题(π(K₄³) 是否 5/9)、(4,5) 问题(本问题)等。已有的通用工具:模糊幂(blow-up)、flag algebra(半定规划对密度的系统约束)、稳定性定理( Razborov–Reiher 型)。它们的共同局限:能给 «逼近某构造» 的稳定性,却给不出 «该构造最优» 的判定。

主要命题与证明

命题 1(补集恒等式,完整证明) 对一切 n ≥ 5:T(n,5,4) = C(n,4) − ex(n,K₅⁴),其中 ex 为 K₅⁴-自由 4-一致超图的最大边数。

证明 设 𝒯 ⊆ C(V,4) 击中所有 5-子集,令 𝒢 = C(V,4)∖𝒯。(⟹)若 𝒢 含 K₅⁴:存在 5-子集 S,其全部 5 个 4-面在 𝒢 中,即无一在 𝒯——与 𝒯 击中 S 矛盾。(⟸)设 𝒯 未击中某 5-子集 S:S 的 5 个 4-面全不在 𝒯,即全在 𝒢——𝒢 含 K₅⁴,矛盾。故 «击中 ⟺ 补集 K₅⁴-自由» 是双射对应,取最大 𝒢 即得恒等式。□

命题 2(渐近常数的存在性,Katona–Nemetz–Simonovits 1964,完整证明) 对任何固定 r-一致超图 ℋ,极限 π(ℋ) = limn→∞ ex(n,ℋ)/C(n,r) 存在。

证明 关键引理:ex(n+m,ℋ) ≥ ex(n,ℋ) + ex(m,ℋ) + n m·O(n+m)r−2——把两个 ℋ-自由超图放在不相交顶点集上、再 «补上» 跨越两部分的边中至多含 (r−1) 个 «一侧» 顶点者:任何 ℋ 的 r+1? 顶点拷贝若同时使用两侧的 «内部结构»,其 r-面中必有某面完全落在一侧(鸽笼),拷贝即已在该侧出现,矛盾——精确地说,ℋ 的拷贝的所有面中,至多一面是 «跨边»,其余各面完全在某一侧;把跨边删去仍得 ℋ-自由族,故上界可改为 «两侧内部分别最优+跨边全保留» 的构造而保持自由,引理成立。由超加性,ex(n,ℋ)/C(n,r) 递增到极限(分母用 C(n,r) 的规范化后单调有界)。□

命题 3(图兰构造的地位;陈述) 图兰 1941 年的循环分部构造给出 T(n,5,4) 的上界(对偶地给出 π(K₅⁴) 的下界);半个多世纪以来没有任何构造改进此界,flag algebra 的半定规划界也只是 «温和» 地夹逼。构造的最优性等价于 π(K₅⁴) 的取值判定——超图图兰纲领的主峰之一。

说明 对比图情形:图兰定理(K₃ 图兰密度 1/2)由 Erdős 完整证明;超图情形连 «候选密度» 的分数形式都要靠构造反推——这正是 «构造五十年不被击败、却无人能证最优» 的结构性原因。□

进展与文献

Turán 1941 的原始文与 «三难构造»;Katona–Nemetz–Simonovits 1964 的密度存在性;Keevash 2011 的超图图兰综述(K₄³ 等族的权威整理);Razborov flag algebra 系列、Reiher–Wagner 的稳定性工作。开放核心:π(K₅⁴) 的取值(等价于本问题渐近常数);(3,4) 问题的 5/9 判定(图论分册 07 号);一般 «图兰密度可计算性» 的超图推广。

← 返回问题 07