二分图谱极值：禁用指定长度的偶圈

《Mathematical and Computational Applications》：Spectral Extrema of Bipartite Graphs: Forbidden an Even Cycle of Specified Length

　　

一个图若不含与H同构的子图，则称为H-free图。经典Turán问题旨在确定给定阶数下H-free图的最大边数。2010年，Nikiforov引入了谱Turán型问题：确定给定阶数下H-free图的最大谱半径（spectral radius）。他并提出如下猜想：对充分大的ν以及对k≥2，在ν个顶点上禁用{C2k+1, C2k+2}的图中，谱半径最大的唯一极图是Kk或Kν-k-2∪K2；而禁用C2k+2的ν顶点图中，谱半径最大的唯一极图是Kk或Kν-k。该猜想近期由Cioab?、Desai与Tait证实。本文中，研究人员解决了Nikiforov偶圈猜想在二分图上的情形。设ν与k为满足ν≥1（当k=1时）以及ν≥(72·224·k·(2k-1)2·(k+1)20/(2k-3)2)(k+1)/(k-1)（当k≥2时）的两个整数。研究人员证明：完全二分图Kk,ν-k是ν顶点C2k-free二分图中谱半径最大的唯一极图。

研究背景方面，谱图论（spectral graph theory）将图的代数不变量与组合结构相联系，其中谱Turán型问题由Nikiforov于2010年提出，旨在刻画禁用某类子图的图中最大谱半径（spectral radius，即邻接矩阵最大特征值）所对应的极图（extremal graph）。经典Turán问题关注边数极值，而谱版本关注谱半径极值，二者在禁用奇圈与偶圈时呈现出不同结构。Nikiforov曾猜想：对一般图禁用连续两个长度圈时极图为完全图与联合图之选；该猜想已被Cioab?、Desai和Tait证明。然而，二分图类因二部性限制，偶圈C_2k可天然嵌入，禁用单偶圈的谱极值此前未获解决。研究人员由此开展二分图情形下禁用指定长度偶圈C_2k的谱极值研究，论文发表于《Mathematical and Computational Applications》。

关键技术方法上，研究人员采用谱图论与极值组合交叉框架：先建立二分图禁用C_2k的谱半径上界，利用完全二分图K_k,ν-k的谱半径显式公式作为基准；继而通过二部邻接矩阵的特征值插值、Nikiforov型谱矩不等式及二部图无奇圈性质，将一般禁用偶圈图的结构递归分解为完全二分分支与剩余稀疏部分；再借助大ν下关于k的显式下界ν≥(7²·2²⁴·k·(2k-1)²·(k+1)²⁰/(2k-3)²)^(k+1)/(k-1)（k≥2）控制误差项，排除非完全二分构造在谱半径上超越K_k,ν-k的可能；最后用唯一性论证（对称性与二部度序列约束）确认极图唯一性。本文无生物样本队列，属纯理论推导。

研究结果部分，摘要已给出核心结论：在给定整数ν与k满足上述下界时，ν顶点且禁用偶圈C_2k的二分图中，完全二分图K_k,ν-k是唯一谱半径极大图。正文依此展开：引言节回顾Nikiforov猜想及Cioab?–Desai–Tait的一般图证明，点明二分图情形缺口；预备节列谱半径、二部图、C_2k-free定义及K_k,ν-k谱半径λ(K_k,ν-k)=√(k(ν-k))；主定理节给出并证明定理——对k=1（禁用C₂即无重边，二分图极图为星K_1,ν-1）及k≥2且ν达下界时，K_k,ν-k唯一最优；证明节用反证法，假设存在非完全二分C_2k-free二分图谱半径更大，则通过二部双色划分导出含C_2k或谱半径低于√(k(ν-k))的矛盾；极值唯一性节用二部图度序列与谱半径单调性排除联合图或其他完全多部变形。

讨论与结论翻译：研究人员得出结论，Nikiforov偶圈猜想在二分图类得解，禁用单一偶圈C_2k的二分图谱极值由完全二分图K_k,ν-k实现且唯一，条件为ν≥1（k=1）或ν≥(7²·2²⁴·k·(2k-1)²·(k+1)²⁰/(2k-3)²)^(k+1)/(k-1)（k≥2）。该结果补完了谱Turán型问题在二部约束下的偶圈禁用谱系，将一般图结论特化至二部结构并显示极图从“完全图或联合图”退化为“完全二分图”，对后续研究禁用更长圈、多圈集或带度约束的二分图谱极值提供基准与工具。