论文标题:
Spectral extremal problems on planar and outerplanar graphs without Ck,l
发表日期:
2026年07月
发表单位:
Xinjiang University
原文链接:
https://arxiv.org/pdf/2607.13538v1.pdf
平面与外平面谱极值问题新突破，Ck,l 禁止图的谱半径完全刻画
这篇工作盯住的是图论里一个很“硬”的问题：在平面图和外平面图中，哪些结构能把谱半径顶到最大。别看名字很学术，核心其实很朴素——在不允许出现某些“坏图”时，谁最能长出“最强的连边骨架”，谁就更容易把邻接矩阵的最大特征值，也就是谱半径，推到上限。这篇论文禁掉的对象不是单个环，而是两个不同长度的环共享一个公共顶点形成的图 Ck,l，其中 l≥k≥3。作者最终给出的答案很干脆：当 n 足够大时，平面图和外平面图的极值结构都不是“随便拼出来的花活”，而是落在非常规整的“join + 路径森林”模板上。说白了，就是极值图长得很像一台被精心拧紧螺丝的机器，不是一团乱麻。图：极值图中普通顶点的特征向量坐标有明确上下界。这里的 ρ 是谱半径，xu 是对应正特征向量在顶点 u 上的分量。这个界很关键，因为后面所有“加一条边、删几条边、换一段路径”的比较，最后都要落到这个量上来算账。
方法概述
先把问题翻译成人话：给定一个禁止子图 Ck,l，在所有 n 个点的平面图或外平面图里，谁的谱半径最大？这类问题叫谱极值问题。它和普通的“边数最多”不一样，谱半径更偏向于“连接方式是否高效”，所以有时同样的边数，结构不同，结果能差一截。论文的技术路线很经典，也很硬核：先借助已有定理说明，足够大的极值平面图一定包含 K2,n-2 这种“两个核心点连着几乎所有其他点”的骨架；再用正特征向量和 Rayleigh 原理衡量“改一刀以后谱半径是涨还是跌”；最后通过一连串结构排除，把剩余图压缩成若干条路径的并，进一步锁死路径长度分布，得到唯一极值图。图：外平面图版本里，普通顶点的特征向量分量也被压在一个很窄的区间内。这个界比平面图略紧，原因不难理解：外平面图的结构约束更强，能“乱长”的空间更小，极值结构自然更容易收缩成一条主路径挂若干短路径的形状。这里有个很值得注意的点：论文不是只证明“存在某个极值图”，而是把唯一极值结构也给了出来。对图论来说，这比单纯给上界更有价值，因为它告诉读者：真正把谱半径顶到天花板的，不是某类松散结构，而是非常具体、几乎没有歧义的图形模板。
论文主体思路
这篇论文属于典型的图论谱极值研究，下面先把主干信息用一张表说清楚。
*表格超出部分左右可以滑动
项目
内容
应用场景
平面图、外平面图中的谱极值理论研究
问题建模
在禁止子图 Ck,l 的前提下，最大化 n 维图的谱半径
模型 Backbone 及选择原因
以 K2,n-2 骨架、join 结构和路径森林为核心模板；因为极值平面图在大 n 下会自然逼近这种高连接度结构
损失函数
无机器学习损失函数；用特征向量、Rayleigh 原理和结构变换比较谱半径大小
训练数据集
无；使用图论定理、引理与结构归纳
测试数据集
无；通过对所有可能结构分类排除完成证明
训练方法
证明式推导：先锁定骨架，再限制剩余部分只能是若干条路径，最后用路径变换逼出最优分布
实验效果
给出平面图与外平面图中 Ck,l-free 的唯一极值图，属于完全刻画
方法优势
结论清晰、结构唯一、可复用到类似禁止图问题
方法缺点
需要 n 足够大，且证明依赖较强的结构引理，常数门槛偏高
核心设计
证明一开始就把极值图“逼”成了一个很窄的形状。根据已有结果，足够大的极值平面图中会出现 K2,n-2。直白点说，就是有两个顶点像总指挥，其他点几乎都得听它们的。此时再看正特征向量，两个核心点的分量最大，其他点的分量则被压到 2/ρ 附近。这个“分量很小”的事实特别重要，因为它说明：后面如果把某些边从小分量区域挪到大分量区域，谱半径就可能上升。接下来，作者把剩余顶点集合记成 R，并证明 G[R] 必须是若干条路径的并。为什么？因为一旦 R 里出现环，就会和两个核心点一起拼出 K5 或 K3,3 这样的非平面结构；一旦某个点在 R 里的度数超过 2，也会直接炸出 K3,3。所以这个步骤不是“审美洁癖”，而是把所有不合法结构一刀切掉。然后是更关键的一步：证明这两个核心点之间必须相邻。如果它俩不连边，就把这条边补上，平面性仍然不坏，而且还能继续保持 Ck,l-free。可一旦补边后谱半径更大，就和“原图已经极值”矛盾。这个思路非常图论：不是直接猜答案，而是用“补一刀会不会更好”来反推原图必须长什么样。再往下，作者对路径森林 H 的长度分布做“精修”。如果最长两条路径加起来太长，就能在 K2 + H 里拼出禁掉的 Ck,l；如果路径太碎，又可以通过所谓的 (s1, s2) 变换 把两条路径合并或重分配，令谱半径变大。这个变换的本质很朴素：把“短而散”的结构整理成“长且集中”的结构，谱半径通常会更喜欢后者。这也是整篇文章最像“工程调参”的地方：先固定骨架，再调整枝叶。骨架是 K2 或 K1 加路径森林，枝叶则是各条路径的长度。作者通过一系列比较证明，最优分配会把大部分路径长度压成同一个数值，剩下的最多只差一个单位。于是最终极值图就落成了论文里给出的那几个 H𝒫 或 H𝒪𝒫 模板。
从通用猜想出发，实现定理的严谨证明
这篇论文并不是凭空起题，而是接在一条很清楚的谱极值研究脉络上。早年人们就猜测：外平面图里最“能撑谱半径”的结构，应该是 K1 + Pn-1；平面图里则更像 K2 + Pn-2。后来的工作已经把这些经典猜想解决得差不多了。本文做的事情，可以理解成把这个思路继续往前推：当禁掉的图从“一个环”变成“两个共享点的异长环”时，极值结构是否仍然保持这种“核心点 + 路径森林”的风格？答案是肯定的，而且作者把答案写得很完整。证明过程里最值得记住的不是那些长长的代数式，而是三类动作：排除非法环、补边比较谱半径、路径变换逼近最优分布。这三板斧一出，图的自由度就被压得很低。最后的结论自然也就不神秘了：平面图版本是 K2 + H𝒫(·,·) 的分段形式，外平面图版本是 K1 + H𝒪𝒫(l-2,l-2)。不同的 l 与 k 区间，对应不同的最优路径长度组合，但整体范式非常统一。如果把这件事放到更大的谱图论语境里看，它的意义在于：禁止子图越具体，极值结构越容易从“猜测”走向“完全刻画”。这类结果不一定像深度学习那样有炫目的指标涨幅，但它的价值在于“干净”。数学里最舒服的答案，往往不是“差不多”，而是“就是它”。这篇论文属于后者。
图论前沿：为谱极值理论添砖加瓦
这类工作对从业者最直接的启发，不是“拿来就能部署”，而是极值结构分析的思维方式。先找骨架，再看局部；先定不可行结构，再做最优调整；先用全局定理收缩搜索空间，再用局部变换完成精修。这个套路在很多组合优化、图算法和结构证明里都能复用。不过这篇论文也有明显边界。第一，结论依赖“n 足够大”，那些夸张的大常数门槛说明它更像渐近理论，而不是小规模图的现成工具。第二，证明链条比较长，很多地方都依赖前人关于平面谱极值的结构引理，复现时不能只看主定理，得把前置引理一起啃掉。第三，论文解决的是非常明确的禁止图问题，泛化到更复杂的 forbidden family 时，结构未必还能这么听话。但也正因为它边界清楚，这篇工作才显得扎实。它没有把问题包装成“万能框架”，而是老老实实把一个经典方向往前推进了一步：从单环到双环，从同长度到异长度，从猜结构到定唯一性。这才是数学论文最值钱的地方——不是把话说大，而是把结论说死。
可能的问题：结论依赖很大的 n 门槛，证明链条长且常数偏硬；更像“把一个经典分支做完整”，而不是打开全新赛道。
主要参考文献
Jiamin Li, Dan Li, Xilong Yin, Yuanyuan Chen. Spectral extremal problems on planar and outerplanar graphs without Ck,l. arXiv:2607.13538v1, 2026.Tait and Tobin. Spectral extremal problems for planar and outerplanar graphs. Journal of Combinatorial Theory, Series B, 2017.Yin and Li. Related results on spectral extremal problems for planar and outerplanar graphs without cycles and linear forests. 2026.
