← 返回 PaperDaily 大模型与智能体

不用GPU也能发顶刊？南大用"树标号"破解图兰问题

纯数学也能这么精彩！这篇来自南京大学数学系的工作，用组合与树结构工具一举证实了Ding等人关于图兰密度的猜想，并把结论从3-图推广到任意k-图。不需要多深的超图背景，也能领略抽象数学化繁为简的美感。

龙哥读论文发布于 2026-08-24 00:20:33 阅读 2 查看原文

#人工智能 #AI科研

原论文信息如下：

论文标题:
Any k-graph with zero ℓ-degree Turán density is layered

发表日期:
2026年08月

发表单位:
南京大学数学系

原文链接
https://arxiv.org/abs/2608.18542

数学里有一类问题，特别像“禁令游戏”：规定一个“违禁品”F，问在n个顶点上最多能铺多少条边而不出现F。这类问题在20世纪中叶从图论里长出来，后来延伸到了超图，演变成了一个庞大的Turán型问题家族。

这个家族里有个特别刁钻的成员叫共度Turán密度，它追问的是：如果限制每条边都必须被大量(k−1)-子集“共享”，你还能不能绕开违禁品？某些情况下答案是0——也就是说，你可以把约束尽可能拉满，仍然找不到那个违禁品。

2025年，Ding等人在《伦敦数学会杂志》上提出了一个猜想：什么样的3-图会有这种“零密度”特性？答案是——分层(layered)的3-图。

南京大学数学系的最新工作，把这个问题彻底解决并推广到了任意k-图。论文标题说得非常直白：Any k-graph with zero ℓ-degree Turán density is layered——任何ℓ-度Turán密度为零的k-图都是分层的。

什么是零余度Turán密度？一个悬而未决的猜想

先补一点基本设定。一个k-图是k-一致超图：每条边恰好包含k个顶点。3-图就是每条边恰好有3个顶点的超图，普通图就是2-图。Turán数ex(n,F)，指的是在n个顶点上、不包含F作为子图的k-图最多能有多少条边。把这个数除以所有可能的边的总数C(n,k)，再让n趋向无穷，得到的就是F的Turán密度π(F)：

Turán密度衡量的是“禁令F的威力”：如果π(F)>0，说明禁止F只能拦住一部分边；如果π(F)=0，说明你可以在n个顶点上构造出几乎完整的超图却仍然不包含F。经典图论中，Erdős-Stone定理告诉我们，对于普通图（k=2），只要F不是森林，π(F)就恒大于0。但在超图（k≥3）中，情况要复杂得多，存在大量π(F)=0的非平凡例子，这也正是超图Turán理论的核心魅力所在。

Mubayi和Zhao引入了共度Turán密度（codegree Turán density）。这里的思路从“边的总数”换成“顶点子集的公共邻域数量”：对k-图H中的任意(k−1)-子集S，记d_H(S)为包含S的边数；最小共度δ_co(H)取遍所有(k−1)-子集中的最小值。共度Turán数ex_co(n,F)就是所有n顶点、不含F的k-图中，δ_co(H)能取到的最大值。再除以n取极限，就得到π_co(F)：

再往中间插一级，ℓ-度Turán密度π_ℓ(F)考察的是所有ℓ-子集的“共同邻居”数量的极限。注意1≤ℓ≤k−1，ℓ=k−1时就是共度密度，ℓ=1时就是经典Turán密度。它们之间有个单调链：

也就是说，共度密度是整个链条里最“严苛”的那一档——它要求和最大，所以数值最小。直观上，共度条件要求每个(k−1)-子集都被大量边覆盖，这比要求每个单点被大量边覆盖要强得多，因此π_co(F)≤π_1(F)=π(F)是自然的。

那么问题来了：什么时候π_co(F)会等于0？也就是说，是否存在一族n任意大的F-free k-图，使得每个(k−1)-子集都被至少γn条边覆盖，而γ可以取任意小？注意，密度为0不代表“边很少”——恰恰相反，共度密度为0意味着可以把公共覆盖的要求调得非常低，让这样的图撑得很大很大，却始终找不到违禁品F。这听起来有点反直觉：既然每个(k−1)-子集都被大量边覆盖，图应该非常“稠密”，怎么还能避开F呢？这正是问题的精妙之处。

Ding、Lamaison、Liu、Wang和Yang在2025年给出了第一个系统性刻画尝试。他们定义了分层3-图并提出猜想：3-图F有π_co(F)=0，当且仅当F是分层的（并且有π_t(F)=0，其中π_t是均匀Turán密度）。要理解这个猜想，得先知道什么是分层k-图。

分层k-图：从3-图到一般k-图的推广

一个k-图F是分层的（layered），如果存在一个顶点标号函数f: V(F)→N，满足两个条件：

(A1)每条边恰好有一个顶点，它的标号是这条边内的最大标号。

(A2)如果有两条边的最大标号相同，那么这两条边上的标号多重集完全相同。

什么叫标号多重集？就是把一条边k个顶点的标号放在一起看作多重集合。举例来说，3-图里一条边三个顶点的标号如果是{0,0,1}，另一条边的标号也是{0,0,1}，两条边的最大标号都是1，且多重集一样，就满足(A2)。注意多重集不要求顺序，{0,0,1}和{0,1,0}是同一个多重集。

直观理解：把相同标号的顶点看成同一“层”。条件(A1)要求每条边有一个唯一的高层顶点，其他顶点在更低的层；条件(A2)要求，从高层顶点俯视，所有“同一层头部”的边，其尾部层次集合完全一样。这很像一张分层的流水线，同一站点的上游零件清单必须一致。再打个比方：想象一个公司组织架构，每个项目组（边）有一个项目经理（最大标号顶点），项目经理的级别决定了项目组的“层级”，而同级别的项目组，其成员构成（标号多重集）必须完全相同。

在3-图的原始定义中，Ding等人还写了一个(A3)条件：如果两条边的标号多重集有至少2个共同元素，则它们的标号多重集完全相等。论文命题1指出，最小的分层函数自动满足(A3)，所以只需(A1)(A2)就行，这个结论对一般k-图成立。这里的“最小”指的是标号值域最小，即使用的不同标号数量最少。这个命题简化了定义，使得验证分层性更加容易。

本文的定理2给出惊人结论：非分层k-图的共度Turán密度永远不会等于0，并且直接给出一个正下界。

其中m是F的顶点数，q_{k,m}=1+(k−1)+(k−1)²+...+(k−1)^m=((k−1)^(m+1)−1)/(k−2)。这个下界是正的，虽然看起来很小（基数、指数双双“叠楼”），但对证明“非分层⇒正密度”这个方向已经足够。值得注意的是，这个下界只依赖于F的顶点数m和一致性k，与F的具体结构无关，这体现了定理的普适性。

把k=3代入，立刻得到：如果3-图F有π_co(F)=0，那么F是分层的。定理1又给出了反方向，于是Conjecture 1和2全部得到证实。这个结果的风格非常“极值组合”——不需要复杂的解析工具，靠的是精巧的组合构造。它再次印证了组合数学中一个常见的现象：看似复杂的结构性质，往往可以用简洁的组合条件来刻画。

核心工具：商有向图与标号树

证明定理2的关键，是把分层条件翻译成一种更方便验证的组合结构——商有向图。

先给k-图G做d-to-1定向：d=k−1，每条边选择一个顶点作为“头”（head），其余k−1个顶点作为“尾”。把头是z、尾是x₁,...,x_d的定向边记为x₁···x_d→z。这种定向方式与普通有向图不同，它允许一个顶点同时作为多条边的头，也允许一个顶点在一条边中是头、在另一条边中是尾。

再取V(G)的一个划分Q，把顶点按划分归入对应部类。商有向图D(G→,Q)的顶点集就是Q；对于每个定向边x₁···x_d→z，如果Q(z)=Z，且某个Q(x_i)=X，就加一条弧X→Z。注意这里每条定向边可能产生多条弧（如果尾部顶点分布在不同的部类中），但每条弧都对应至少一条定向边。

引理1给出了一个漂亮的双向刻画：k-图G是分层的，当且仅当存在一个d-to-1定向和一个划分Q，使得下面两个条件同时成立：

条件(1)头部同类的两条定向边，其尾部类多重集也相同。

条件(2)Q(z)不在任何尾部类中，且商有向图是无环的。

这个引理把“分层”这种带标号的全局性质，变成了一个纯粹关于划分和定向的局部一致性条件，加上一个有向图的无环性条件。无环性意味着可以给每个类赋予一个“高度”（拓扑序），这正好对应分层函数里的标号。具体来说，如果商有向图无环，那么我们可以对每个部类赋予一个拓扑序编号，这个编号就可以作为分层函数的值。条件(1)保证了(A2)成立，条件(2)中的“Q(z)不在任何尾部类中”保证了(A1)中最大标号的唯一性。

接下来是第二个工具：完全d叉树上的可容许标号。记d=k−1，q_{k,m}是前面那个等比级数。令T_m为深度m的完全d叉树，顶点集是所有长度不超过m的d元串（空串是根）。一个可容许标号A: T_m→[q_{k,m}]满足：任何一条从根往下的路径上，标号不能重复。换句话说，同一个标号不能在同一祖先链上出现两次。这个条件保证了标号在树结构上的“层次性”——沿着树向下走，标号必须不断变化。

对一棵标号树C，它的d个主分支C¹,...,C^d是根的各子树标号。定义如下关键关系：

这个关系的直观含义是：C把这d棵树的深度r−1截断信息，恰好“记在”自己的d个主分支里。引理2给出了这个关系的三条性质：

性质(1)如果在深度r成立，截断到r−1仍然成立——这个“向下闭合”性质保证了归纳构造的可行性。

性质(2)关系不可能自指——C不会等于A₁,...,A_d中任何一个。这一条保证了构造图时头部类不与尾部类的任何顶点重合。

性质(3)正向完备性：给定任意d棵树A₁,...,A_d，总存在一棵树C使得该关系成立。这条很像“补上一条边”的操作，是后面构造图时保证每个(k−1)-顶点组都能找到共同邻居的关键。

性质(3)的证明是构造性的：给定A₁,...,A_d，我们可以显式地构造出一棵满足关系的树C。构造的核心思想是：将A₁,...,A_d的深度r−1截断信息“编码”到C的根标号中，然后递归地构造C的各个分支。这种构造保证了C的存在性，而不只是理论上的存在。

定理2的证明思路：构造F-free图H_n

准备工作做足，现在来看定理2的证明框架。

设F是m个顶点的非分层k-图。先定义颜色族P_{k,m}：它收集所有k元标号树多重集{A₁,...,A_k}，使得其中至少一个“轮转定向”满足→_m关系。一个P_{k,m}-着色就是把顶点映射到C_m（所有可容许标号树的集合），使每条边的树多重集落在P_{k,m}中。这里的“轮转定向”是指：对于多重集{A₁,...,A_k}，我们依次尝试每个A_i作为“头”，其余作为“尾”，检查是否存在某个i使得关系A₁···A_{i-1}A_{i+1}···A_k →_m A_i成立。

引理4说得很直接：任何顶点数≤m且存在P_{k,m}-着色的k-图，一定是分层的。证明不难：把每条边按满足关系的方向定向，然后调用引理3把顶点划分成满足引理1条件的部类。引理3在这里起到了桥梁作用，它将着色（树标号）转化为划分（部类），从而将分层性的验证归结为商有向图的无环性检查。

现在用反证法构造H_n。把n个顶点尽量均匀地分成很多个大类，每个大类用一棵C_m中的标号树来命名。任意k个顶点，当且仅当它们所在类名字的多重集落在P_{k,m}中时，构成一条边。这里“尽量均匀”意味着每个类的大小要么是⌊n/|C_m|⌋，要么是⌈n/|C_m|⌉，这样保证了每个类都有线性大小的顶点数。

这个H_n有两个关键性质。

第一，它的最小共度至少是⌊n/|C_m|⌋。任给一个(k−1)-顶点组，设其所在类为A₁,...,A_d，由引理2性质(3)，存在C∈C_m使得A₁···A_d→_mC。又由引理2性质(2)，C不会与A_i相同。因此C类中的每个顶点都不是这组顶点的一员，而且它们都可以与这组顶点连边。C类有约n/|C_m|个顶点，所以每个(k−1)-子集都有这么多公共邻居。这正是共度密度的线性下界。注意这里的论证依赖于性质(2)和(3)的配合：性质(3)保证存在性，性质(2)保证头部类不与尾部类重合，从而C类中的顶点确实可以作为公共邻居。

第二，H_n是F-free的。假设H_n包含F的一个拷贝，把每个顶点映射到它所在类的树标号，就得到了F的一个P_{k,m}-着色，这与F非分层矛盾（引理4）。这个论证非常简洁：如果F能嵌入H_n，那么F就继承了H_n的着色结构，从而F必须是分层的，矛盾。

于是：

C_m是所有T_m可容许标号的总数，显然不超过q_{k,m}^(q_{k,m})（每个顶点最多有q_{k,m}种标号选择），所以：

证明完成。整个构造非常干净：用树标号定义颜色，用颜色关系定义边，用边的存在性反推分层性。这种“用颜色关系编码结构”的套路，在极值组合里屡试不爽，每次都让人觉得赏心悦目。它类似于图论中的“图嵌入”思想：通过构造一个巨大的“模板图”，使得任何试图嵌入F的尝试都会在颜色层面产生矛盾。

猜想证实与未来展望

把k=3代入定理2，立即得到推论1的前半：3-图F有π_co(F)=0当且仅当F是分层的且π_t(F)=0。再结合Reiher、Rödl和Schacht对线性3-图均匀Turán密度的刻画（线性3-图一定有π_t(F)=0），就得到推论1的后半：线性3-图F有π_co(F)=0当且仅当F是分层的。Ding等人的两个猜想就此彻底解决。这里的“线性3-图”是指任意两条边至多共享一个顶点的3-图，Reiher等人的结果保证了这类图的均匀Turán密度为零，从而与分层性等价。

更一般地，因为π_ℓ(F)≥π_co(F)，所以推论2说：对任意1≤ℓ≤k−1，如果π_ℓ(F)=0，那么F是分层k-图。这个结论从3-图一路推到了任意一致性的超图，覆盖面相当广。值得注意的是，这里的ℓ可以是任意中间值，不仅仅是极端情况ℓ=1或ℓ=k−1，这大大增强了定理的适用范围。

论文还证明了命题1：分层函数的最小表示必定满足(A3)，这为后续研究“最小分层”提供了一个有用的正则性工具。这个命题的意义在于，它保证了我们在研究分层k-图时，可以专注于满足(A3)的“标准形式”，而不必担心不同分层表示之间的差异。

未来还有哪些开放问题？最大的悬念是：定理2给出的下界到底离真实的π_co(F)有多远？对于具体的非分层3-图，已有一些精确值（比如Fano平面π_co=1/2），但对一般的k-图，这个下界显然还非常粗糙。例如，对于k=3、m=7的Fano平面，定理2给出的下界大约是(1+2+4+...+2^7)^(-(1+2+...+2^7))，这是一个极其微小的数，而真实值是1/2，差距巨大。另外，“分层”给出了必要条件的刻画，但π_co(F)=0的另一半——均匀Turán密度π_t(F)=0的判别——本身依然是很难的问题。均匀Turán密度要求图在某种意义下“均匀分布”，其判定比经典Turán密度更加复杂。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底在解决什么问题？南京大学数学系最新证明：任何非分层k-图的共度图兰密度都严格大于零，从而推出零度图兰密度的k-图必为分层结构，并完全证实了Ding等人提出的3-图猜想。

这篇工作最值得看的点是什么？通过构造具有线性最小余度的F-free k-图H_n，证明任何非分层k-图F的余度Turán密度有正下界，从而推出零ℓ-度Turán密度的k-图必为分层图。

这篇工作的边界或风险在哪里？优点：理论证明严谨，构造方法精巧，将分层条件转化为商有向图性质，并利用树标号构造了具有线性余度的F-free图，解决了公开猜想。缺点：下界q_{k,m}^{-q_{k,m}}极小，仅为理论存在性证明，未讨论最优性；方法为纯理论，无实验验证。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆

通过构造具有线性最小余度的F-free k-图H_n，证明任何非分层k-图F的余度Turán密度有正下界，从而推出零ℓ-度Turán密度的k-图必为分层图。

实验合理度：★★★☆☆

现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。

学术研究价值：★★★★☆

通过构造具有线性最小余度的F-free k-图H_n，证明任何非分层k-图F的余度Turán密度有正下界，从而推出零ℓ-度Turán密度的k-图必为分层图；更关键的是问题定义是否可复用到同类任务。

稳定性：★★★☆☆

现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。

适应性以及泛化能力：★★★☆☆

现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。

硬件需求及成本：★★★☆☆

现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。

复现难度：★★★☆☆

现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。

产品化成熟度：★★★☆☆

论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。

可能的问题：下界q_{k,m}^{-q_{k,m}}极小，仅为理论存在性证明，未讨论最优性；方法为纯理论，无实验验证。

主要参考文献

[1] Ding L, Lamaison A, Liu H, Wang S, Yang H. On 3-graphs with vanishing codegree Turán density. JLMS, 2025.

[2] Mubayi D, Zhao Y. Codegree Turán density of an r-graph. Combinatorica, 2007.

[3] Katona G, Nemetz T, Simonovits M. On a problem of Turán in the theory of graphs. Mat. Lapok, 1964.

[4] Reiher C, Rödl V, Schacht M. On a Turán-type problem of Brown, Erdős and T. Sós. Proc. LMS, 2018.

[5] Yang J, Fang X, Chen Y. Any k-graph with zero ℓ-degree Turán density is layered. arXiv:2608.18542, 2026.

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

图论极限寻真章，分层结构见乾坤。欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如数学+南京+南大+龙哥），根据格式备注，可更快被通过且邀请进群。
wechat_helper