禁止诱导子图与特征值下界：图与符号图的有限禁刻画分类

《Forum of Mathematics, Sigma》：Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below

语 Bussemaker和Neumaier提出的公开问题——图与符号图在特征值下界约束下是否具有有限禁刻画——被本研究彻底解决。通过引入塑性常数ρ（x3=x+1的唯一实根）及其衍生的临界值λ*=ρ1/2+ρ-1/2≈2.01980，作者证明了图族??(λ)和符号图族??±(λ)存在有限禁刻画当且仅当λ*。该结果不仅完善了Hoffman关于图最小特征值极限点的理论，还应用于高维球面二距离集最大规模问题的解决，建立了图谱理论与几何编码的深刻联系。

　　

在谱图理论中，图或符号图（每条边标有正负号的图）的特征值边界问题一直是核心课题之一。特别地，研究特征值有下界的图族是否可由有限个“禁止子图”完全刻画，是Bussemaker和Neumaier于1992年提出的著名难题。此类刻画若能实现，将极大简化对复杂图族的分类与识别。然而，此问题长期悬而未决，尤其在最小特征值λ₁≥-λ的图族??(λ)和符号图族??^±(λ)中，临界值λ的确定尤为困难。

早期研究集中于λ=2的情形。Smith（1970）完全分类了谱半径不超过2的连通图，即??'(2)，它们均为图1中扩展Dynkin图的子图。而最小特征值不小于-2的图族??(2)更为复杂，除??'(2)外还包含所有线图（line graph）。Cameron等人通过根系统（root system）理论给出了??(2)的完整分类。进一步地，Rao等人证明??(2)的极小禁止子图最大顶点数不超过10，Bussemaker和Neumaier通过计算机搜索确证其共有1812个。对于谱半径有上界的图族??'(λ)，Jiang与Polyanskii在前期工作中已解决其有限刻画的临界条件。然而，??(λ)的对应问题直至本文才被彻底攻克。

本文的核心发现是：图族??(λ)和符号图族??^±(λ)存在有限禁止子图刻画当且仅当λ小于临界值λ^*=ρ^1/2+ρ^-1/2≈2.01980，其中ρ为x³=x+1的唯一实根（称为塑性常数）。这一结果揭示了清晰的阈值现象：当λ< />^*时，可通过有限个极小禁止子图精确描述??(λ)；当λ≥λ^*时，此类刻画不存在。作为推论，作者补全了Hoffman关于图最小特征值极限点的描述，证明-λ（λ>2）是极限点当且仅当λ≥λ^*。

研究动机部分源于高维几何中的球面二距离集问题：给定-1≤β<0≤α<1，求R^d中单位向量集的最大规模N_α,β(d)，要求向量间内积仅取α和β两值。Jiang等人近期提出猜想：当d→∞时，N_α,β(d)/d的极限可由符号图的最大特征值λ及其重数（multiplicity）定义的量k_p(λ)表示（其中p=?-α/β?+1）。本文通过符号图禁止刻画理论，在(1-α)/(α-β)< />^*时证实该猜想，并将误差项改进为仅依赖α,β的常数。

关键技术方法

研究通过构造路径扩展（path extension）、团扩展（clique extension）等图操作，结合Hoffman关于特征值极限的经典结果，分析图族??(λ)的局部结构。针对λ<2的情形，利用线图与广义线图（generalized line graph）的分类定理（Cameron等），并通过Dickson引理控制极小禁止子图规模。对于λ∈[2,λ^*)，证明??(λ)\??(2)中连通图数量有限，依赖计算机辅助验证31个广义线图禁止子图的扩展性质。当λ≥λ^*时，通过构造划艇图（rowing graph）序列证明特征值在(λ^*,∞)稠密，否定有限刻画可能性。符号图部分引入切换等价（switching equivalence）和符号线图（signed line graph）理论，将问题化归为无符号图情形。

研究结果

1. λ<2情形的有限刻画

通过引理2.3和2.5，选取适当参数?,m，使得 claw图（C）和diamond图（D）的扩展族??(C,?,m)和??(D,?,m)与??(λ)不交。引理2.6表明，足够大的连通图若避免星图S_k和上述扩展族，则必避免C和D，从而由van Rooij-Wilf定理（定理2.7）知其为线图。进一步，引理2.8通过限制线图原图（树）的局部结构，结合Dickson引理（引理2.9）证明极小禁止子图集的有限性。

2. λ∈[2,λ^*)情形的连通图有限性

定理2.10是核心突破：当λ∈[2,λ^*)时，??(λ)\??(2)中连通图数量有限。证明依赖广义线图的31个极小禁止子图（图5）。通过计算机辅助（附录A）验证这些图的路径扩展和团扩展均使最小特征值低于-λ^*（引理2.14），再结合引理2.15控制路径-团扩展，最终通过引理2.6导出连通图规模上限。

3. λ≥λ^*情形的无限性

定理2.19通过构造划艇图序列（定义2.21）证明(λ^*,∞)中任意λ均为图最小特征值的极限点。引理2.22详细分析划艇图特征值性质，结合Shearer关于谱半径稠密性结果（定理2.20），补全λ^*与λ′≈2.05817间的空白。

4. 符号图的平行结果

第3节将上述结果推广至符号图。通过定义符号路径扩展、团扩展（定义3.1）并建立符号线图与有向图（bidirected graph）的对应（引理3.7），证明定理1.5：??^±(λ)的有限刻画存在性同样由λ< />^*决定。推论1.6通过符号反转得到最大特征值≤λ的符号图族??^?(λ)的对应结论。

5. 球面二距离集的应用

第4节应用禁止刻画理论至球面二距离集问题。定理4.2证明当λ< />^*时，关键参数k_p(λ)（定义1.7）可通过有限图计算得到。结合Jiang等人的框架（定理4.5），推论4.6严格证实猜想1.8在(1-α)/(α-β)< />^*时成立，且误差项为O(1)。针对λ=2的特例，引理4.12通过有向图的边着色分析，证明k_p(2)≥(p/(p-1))²，且当图切换等价于K_p,p的线图时取等。

结论与意义

本研究彻底解决了谱图理论中关于特征值下界图族有限刻画的长期难题，揭示了以塑性常数ρ衍生的λ^*为关键阈值的普适规律。理论层面，不仅完整回答了Bussemaker-Neumaier问题，还补全了Hoffman特征值极限点分类，推进了对图谱结构的内在理解。应用层面，该成果为高维球面二距离集最大规模问题提供了严格理论支撑，建立了图论与几何编码的深刻联系。所发展的符号图禁止刻画方法及计算机辅助验证策略，为后续研究提供了新范式。论文发表于《Forum of Mathematics, Sigma》，彰显了其在基础数学领域的重量级贡献。