← 返回 PaperDaily 大模型与智能体

反直觉！线图居然是Schur-负的，龙哥带你看懂这个反例

一个漂亮到令人拍案的反例，仅用12个顶点和22条边，就终结了一个困扰组合数学界20多年的猜想。论文不仅有严密的数学证明，还通过计算机穷举所有不超过12个顶点的无爪图，验证了最小性。这篇文章值得每个喜欢“反直觉”故事的人读一读。

龙哥读论文 阅读 3 查看原文
#AI科研
原论文信息如下：
论文标题:
A counterexample to the claw-free Schur-positivity conjecture
发表日期: 2026年07月 发表单位: IIT Madras（印度理工学院马德拉斯分校） 原文链接: https://arxiv.org/pdf/2607.26364v1.pdf 开源代码链接: https://github.com/infinityscroll/claw-free-schur-counterexample
先来一个龙哥经典开场：你见过猜了20多年、所有小图都乖乖听话、结果被一个只有12个顶点的“小妖精”当场掀翻的数学猜想吗？今天这篇2026年的论文，就是这么一个“反杀”名场面。龙哥读的时候，一边拍大腿一边感叹：数学的直觉有时候真不靠谱，但反例的力量永远让人上头。
sneaky smile
好了，收。今天的主角是一篇来自印度理工学院马德拉斯分校（IIT Madras）的独立作者Jitendra Prajapati的论文，标题很干脆——《A counterexample to the claw-free Schur-positivity conjecture》。这篇论文要解决的是组合数学里一个悬了二十多年的开放问题：无爪图（claw-free graph）的色对称函数（chromatic symmetric function）是否一定是Schur-正（Schur-positive）的？结果，作者用一个12个顶点的图给出了否定答案——不仅证明了猜想错误，还通过计算机穷举找到了所有最小反例。这是个干净利落的“一锤子买卖”，让人不得不服。

一个困扰组合数学界20年的猜想被推翻

“Schur-正性”（Schur-positivity）是代数组合中的一个重要概念。给定一个图G，我们可以定义它的色对称函数 \(X_G\)（Stanley, 1995），它是关于无限多个变量x₁, x₂, …的形式幂级数，通过图的所有正常着色（proper coloring）求和得到。如果这个对称函数可以写成Schur函数（s_λ）的线性组合且所有系数非负，就称它是Schur-正的。Schur函数是对称函数理论中的一组特殊基，在代数几何、表示论中都有重要地位。
1995年，Gasharov证明了(3+1)-free偏序集的不 comparability图（incomparability graph）是Schur-正的。随后，Stanley在1998年把这一结果归功于Gasharov，并进一步猜想：所有无爪图（即不包含诱导子图K₁,₃的图）的色对称函数都是Schur-正的。这个猜想被称为“无爪Schur-正性猜想”（claw-free Schur-positivity conjecture）。此后近20年，大量数学家尝试证明或证伪，但只得到了部分特殊类（如generalized nets等）的肯定结果，始终没有突破。直到2026年7月，这篇论文把它彻底推翻了。
龙哥想说：数学猜想被推翻是常事，但能给出一个如此简洁、可验证的反例，并且证明它就是最小的，这本身就是一件艺术品。下面我们就来仔细端详一下这个新晋“反例之王”。

12个顶点和一个负的Schur系数

反例图的图6编码（graph6 code）是K?`CRAWWUXIM，听起来像外星密码，但实际它就是一个有12个顶点、22条边的连通无爪图。该图的色对称函数X_G在Schur基下的展开中，系数等于-64，这是唯一一个负系数。换句话说，这个图不仅不是Schur-正的，还贡献了一个负数：-64。你可能会问：为什么这个数字这么具体且巨大？因为它来自组合计数，我们后面会看到。
作者还给出了另一个同为12顶点的反例，图6编码为K?`CR@`bAbRB，其系数 = -40。这两个图是仅有的两个12个顶点的非Schur-正的无爪图（同构类意义上）。而且穷举结果告诉我们：所有≤11个顶点的连通无爪图（总共18万多）全部是Schur-正的，所以12就是最小反例的顶点数。

如何构造反例——线图与4-cycle

构造并不复杂，甚至可以用纸笔画出来。核心想法是从一个4-cycle（四边形）出发，在它四个顶点上附加一些结构，然后取它的线图（line graph）。线图L(G)的顶点对应于原图G的边，两个顶点在线图中相邻当且仅当它们在原图中共享一个端点。线图的一个重要性质：线图一定是无爪图。因此只要构造一个线图，就可以确保它是无爪图。
具体构造如下：取一个4-cycle，顶点标记为a、b、c、d，依次连接。现在做四步手术：

•在顶点a处增加一个三角形：添加新顶点u、v，并连接a-u、a-v、u-v。

•在顶点c处增加一个三角形：添加新顶点x、y，并连接c-x、c-y、x-y。

•在顶点b处增加一条悬挂边：添加新顶点ℓ，连接b-ℓ。

•在顶点d处增加一条悬挂边：添加新顶点m，连接d-m。

这样就得到图H，它有4个顶点（a,b,c,d）+ 两个三角形（u,v和x,y）+ 两个叶顶点（ℓ,m）= 10个顶点、11条边（4-cycle的4条边+两个三角形的3+3条边+两条悬挂边=4+6+2=12？等一下：4-cycle有4条边，每个三角形增加3条边（两条从a到新顶点，一条三角形底边），两个三角形共6条边，加上两条悬挂边，所以总边数=4+6+2=12？但原论文说是10条边？我们需要重新计算：H有顶点：a,b,c,d,u,v,x,y,ℓ,m，共10个顶点。边：ab, bc, cd, da（4条），au, av, uv（3条），cx, cy, xy（3条），bℓ, dm（2条），总共4+3+3+2=12条边。的确，H有12条边。然后取线图G = L(H)，G的顶点数等于H的边数，即12个顶点。G的边数：线图的边数由H中相邻边的对数决定，计算可得22条边，与论文一致。
既然G是线图，它天然是无爪图，所以直接成为了反例的候选。接下来就是计算它的色对称函数的Schur展开，发现负系数。这种构造并不神秘，但能命中负系数，说明它巧妙地打破了某种平衡。龙哥只能说：作者很可能先通过计算机搜索发现了这个图，然后才给出简洁的人工证明。

计算机穷举验证：最小反例

为了证明这个12顶点的反例是最小的，作者利用计算机对≤12个顶点的所有连通图进行了穷举。使用nauty的geng工具生成所有连通图，然后筛选出无爪图，再对每个无爪图精确计算其色对称函数的Schur系数（用整数算术）。结果如下表所示（原论文表格）：
顶点数 n 连通图总数 无爪图个数 非Schur-正的无爪图个数
≤812,1131,1450
9261,0804,4940
1011,716,57126,3890
111,006,700,565184,7490
12164,059,830,4761,728,4042
总计165,078,520,8051,945,1812
表1 穷举结果（原论文Table 1）
可以看到，在所有n≤11的无爪图中，没有发现任何反例；到了12顶点，一共1,728,404个无爪图中，只有两个图不是Schur-正的（即论文中描述的两个）。因此，12是最小反例的顶点数。这一计算用了大量的CPU时间（对于n=12总共产生了超过1640亿个连通图，但无爪图只有172万个），但作者给出了确切的数值，而且所有Schur系数计算都用精确整数算术，可靠性没有问题。
龙哥认为，这个计算非常扎实，并且作者将代码、数据以及完整的计算日志都开源了（MIT协议），这让任何人都可以复现和验证。对于一个纯数学猜想，这是最佳实践。

数学验证与独立确认的意义

这篇论文除了给出构造和证明，还做了三件事，让结果更加可信：

第一，作者提供了三种独立实现的精确计算：基于标准边着色与半标准Young tableau枚举、基于幂和对称函数的包含-排除、以及基于稳定划分动态规划加上Kostka矩阵求逆。三种方法都得到了相同的结果：唯一负系数[s₍₃,₃,₃,₃₎] = -64。每种方法都包含对完全图、爪图、暴力着色计数的自测试，确保程序正确。

第二，在本文公开验证存储库于2026年7月22日发布后，Matherne和Morales于次日（7月23日）独立提交了一篇预印本，也给出了两个反例。经过交流确认，他们找到的图与本文的两个图同构。完全独立地发现，增加了结果的可信度。

第三，著名的组合数学社群MathOverflow上也有相关讨论（问题ID 513515），Darij Grinberg等人也进行了独立验证。

这三个层面的独立确认，让这个反例几乎无懈可击。龙哥觉得，这种公开透明的验证文化非常值得其他领域借鉴——特别是在人工智能、机器学习领域，如果人人都能像这样提供可复现代码和详细数据，很多争议早就烟消云散了。

龙迷三问

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

Q1: 什么是“无爪图”？为什么这个猜想重要？无爪图就是不含诱导子图K₁,₃（即一个顶点连接三个互不相邻的顶点，像乌鸦的爪子）的图。这类图在组合优化中很重要（如最大独立集可以在无爪图上多项式时间求解）。无爪Schur-正性猜想试图将这类结构优良的图的着色性质与表示论中的Schur正性联系起来，如果成立，会给代数组合带来统一工具。因此被推翻后，大家需要重新思考哪些图类真正具有Schur正性。

Q2: “Schur函数”和“色对称函数”具体是怎么定义的？普通人能理解吗？可以简单理解：色对称函数X_G是对图的所有正常着色（给顶点涂色，相邻顶点颜色不同）求和，每个着色的贡献是各个颜色变量的乘积。Schur函数是对称函数中一组具有良好对称性和表示论意义的基。说X_G是Schur-正，就是说它可以写成Schur函数的非负组合。这有点像把一个多项式分解成“漂亮”基底的线性组合，系数非负保证了一些组合/几何性质。具体计算通常要用到Kostka矩阵等工具，但看懂反例的证明不需要特别深的背景，主要靠稳定划分计数和矩阵求逆。

Q3: 为什么这个反例的系数是-64？这个数字有什么特别吗？它来自组合计数：先计算所有稳定划分（即把边划分为匹配）的个数，然后乘以Kostka矩阵的逆。具体地，对于形状(3,3,3,3)的Schur函数，它的系数由所有四个部分的稳定划分贡献，经过Kostka矩阵的逆转置运算得到-64。论文中通过枚举得到了32个(3,3,3,3)类型的无标号稳定划分，乘以4!得到768个有标号划分，再减去其他形状的贡献，最终得到-64。实际上就是一组整数线性方程的解，所以不是巧合，而是精算的结果。

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

龙哥点评

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

完全推翻了流传20多年的知名猜想，并且给出了最小反例和干净的人工证明。这种暴力美学与理论洞察兼备的工作，在组合数学里极其罕见。满分实至名归。

实验合理度：★★★★★

虽然是纯数学论文，但关于计算机验证的部分设计严谨：使用nauty枚举所有连通图，筛选无爪图，然后用三种独立实现计算Schur系数，并给出自测试；穷举范围覆盖所有≤12个顶点的图，没有遗漏。实验设计完全合理。

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

直接终结了无爪Schur-正性猜想，同时将研究方向引向更精细的图类（如线图、特定结构的图），给后来者开辟了新问题。对代数组合领域有深远影响。

稳定性：★★★★★

数学证明是确定性的，计算机计算给出精确整数结果，不需要近似或随机。稳定性高到“一旦成立永不改变”。

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

本文聚焦单一猜想，所构造的反例是针对该猜想的特定图。结论不具有直接泛化性。但方法（计算机穷举+人工证明）可以推广到类似猜想的验证。

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

穷举计算在普通服务器上可完成（论文没有报告具体耗时，但12个顶点的连通图总数约1640亿，经筛选后只有172万个无爪图需要计算，应该可行）。人工证明部分完全不需要计算资源。整体成本极低。

复现难度：★★★★★

代码和所有数据已在GitHub上以MIT协议开源，包括验证程序、日志、自测试等。按说明即可完全复现。这也是龙哥特别欣赏的地方。

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

这是一篇纯理论数学论文，不涉及任何产品化。它不适合直接工程落地，但可以作为数学课程、研究课题的绝佳素材。

可能的问题：

论文本身已经非常完善，挑剔地说，如果人工证明部分能给出更结构化的解释，比如为什么这个反例的负系数恰好是-64、而另一个是-40，会更有深度。但作为一篇推翻猜想的短文章（4页），已经足够了。此外，独立验证者Matherne和Morales的论文只相差一天，谁先谁后其实不重要，但论文对此做了妥善说明，没有争议。

参考文献

[1] V. Gasharov, Incomparability graphs of (3+1)-free posets are s-positive, Discrete Math. 157 (1996) 193–197.
[2] R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111 (1995) 166–194.
[3] R. P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Math. 193 (1998) 267–286.
[4] J. P. Matherne, A. H. Morales, Chromatic symmetric functions of claw-free graphs are not Schur positive, arXiv:2607.21508 (2026).
[5] 其他参考文献请见原论文。

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

end
🌟 感觉这个反例太精彩？想跟龙哥一起拆解更多数学难题？
欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如 图论+上海+复旦+龙哥），根据格式备注，可更快被通过且邀请进群。
龙哥读论文微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群。

wechat_helper dianzan
转发文章 微博 X LinkedIn Facebook
龙哥读论文 · PaperDaily

本文基于龙哥读论文 PaperDaily 数据库整理，结合论文原文与工程视角进行解读。