度偏差和谱半径的优化方法

《Discrete Optimization》：An optimization approach to degree deviation and spectral radius

　　

对于一个有限、简单、无向图G，具有n个顶点和平均度d，Nikiforov 引入了G的度偏差s(G)，定义为 s(G) = ∑_u∈V(G) |d_G(u) ? d|。假设G具有最大特征值（即谱半径）λ(G)，最小度至少为δ，且最大度至多为Δ，其中 0 ≤ δ < d < Δ < n，研究人员证明：s(G) ≤ 2n(Δ ? d)(d ? δ)/(Δ ? δ)，以及 λ(G) ≥ d²n/√(d²n² ? s²)，若 s ≤ dn/2，否则 λ(G) ≥ 2s/n。研究人员的结果基于一种平滑技术，该技术将度偏差和最大特征值与低维非线性优化问题相关联。

论文解读：关于度偏差与谱半径的优化方法研究

**研究背景与问题**

在图论与谱图理论中，度偏差（degree deviation）和谱半径（spectral radius）是刻画图结构的重要参数。度偏差s(G)定义为图中所有顶点度与平均度之差的绝对值之和，反映了图的度分布不均匀程度；谱半径λ(G)是图邻接矩阵的最大特征值，与图的连通性、扩张性等性质密切相关。Nikiforov 提出了度偏差的概念，并给出了s(G)与λ(G) ? d（d为平均度）之间的一个不等式关系，但该不等式在常系数上存在优化空间。Haviland 等人给出了度偏差的一般上界，Ali 等人则在最小度δ和最大度Δ约束下得到另一个上界，但该界仅在特定参数下最优，且极值图判定存在疏漏。此外，Nikiforov 猜想对于足够大的n和m，度偏差与谱半径的差距可进一步缩小，即下界和上界均可改进。然而，已有证明仅能逼近到一定因子。因此，本研究旨在：1）在给定度约束下得到更优的度偏差上界，并明确其最优性条件；2）给出谱半径的改进下界，以支持 Nikiforov 猜想；3）重新审视 Ali 等人上界的证明，确定极值图结构。

**研究方法**

研究人员采用的主要关键技术方法为平滑技术（smoothing technique），即将原始图G转化为一个边加权完全图(K, w)，使得度偏差和总边数保持不变，且顶点度在V⁺和V?上分别成为常数。该技术将原问题转化为低维非线性优化问题（non-linear optimization problem），通过分析约束域和目标函数，利用线性规划松弛和极值分析得到最优解。具体地，研究人员将度偏差最大化问题 (PI) 松弛为连续优化问题 (P)，并利用拉格朗日乘子法、偏导数分析等工具，结合边界条件（如d⁺ = Δ或d? = δ）推导出闭式上界。对于谱半径下界，则通过构造二次型极小化问题 (QI) 并利用 Rayleigh 商和特征向量分析，结合偏导数单调性得到下界表达式。

**研究结果**

**1. 引言（Introduction）**
研究人员回顾了度偏差的定义及已有结果：Haviland 的上界（式(2)）在特定参数下达到最优，Ali 等人的上界（式(3)）声称正则或半正则二部图取等，但实际仅在d = 2δΔ/(δ+Δ)时最优。通过分析，研究人员指出式(3)的证明存在漏洞，并在第5节重新校正。

**2. 平滑技术（Smoothing）**
引入平滑图(K, w)后，Lemma 3 证明度偏差和总边数在平滑前后保持不变，且平滑后顶点度在V⁺上位于(d, Δ]内，在V?上位于[δ, d]内。Lemma 4 给出平滑邻接矩阵A?的最大特征值λ?的显式表达式，并证明λ(G) ≥ λ?(G) ≥ d。

**3. 度偏差的上界（Upper bound on s(G)）**
研究人员将度偏差最大化问题转化为连续优化问题 (P)，通过 Lemma 5 分析最优解的性质：最优解满足d⁺ = Δ或d? = δ，并推导出上界 s(G) ≤ 2n(Δ ? d)(d ? δ)/(Δ ? δ)（定理1）。该界优于 Ali 等人的式(3)，且当n足够大时可通过构造特定参数达到，说明其至多相差低阶项。此外，定理6对特殊参数范围（δ=0, 2Δ ≤ dn < Δ(Δ+1)）给出另一上界。

**4. 谱半径的下界（Lower bound on λ(G)）**
通过优化问题 (QI) 的松弛 (Q′)，利用 Lemma 7 的偏导数单调性，研究人员证明定理2：若s ≤ dn/2，则λ(G) ≥ d²n/√(d²n² ? s²)；若s > dn/2，则λ(G) ≥ 2s/n。进一步，Corollary 8 表明，当d ≤ n/2且s ≤ dn/2时，或s > dn/2时，有λ(G) ? d ≥ s²/(2n²d)，从而验证了 Nikiforov 猜想的下界部分（对于d ≤ n/2）。

**5. 式(3)的证明与极值图（Proof and extremal graphs for (3)）**
研究人员重新审视了 Ali 等人上界的推导，通过向量夹角和凸性分析，得到等式(19)和(20)，指出式(3)取等条件为：|d_G(u) ? d|/d_G(u) 为常数，且所有顶点度属于{δ, Δ}。这导致d = 2δΔ/(δ+Δ)，因此极值图不一定是二部图，从而纠正了原文的结论。

**讨论与结论**

在讨论部分，研究人员指出，定理1的上界在大多数参数下优于 Ali 等人的式(3)，且通过构造具体图（如取n₊ = (d?δ)n/(Δ?δ)等）可达到该界（至多相差低阶项），说明该界是紧的。定理2的下界在d ≤ n/2时完全证实了 Nikiforov 猜想的下界部分，而d > n/2的情形仍需进一步研究。此外，平滑技术作为核心工具，将图论问题转化为低维非线性优化，为此类问题提供了新思路。

**研究结论翻译**
论文证明了：对于具有n个顶点、平均度d、最小度至少δ、最大度至多Δ的图G，度偏差满足 s(G) ≤ 2n(Δ ? d)(d ? δ)/(Δ ? δ)；谱半径满足 λ(G) ≥ d²n/√(d²n² ? s²)（若s ≤ dn/2）或 λ(G) ≥ 2s/n（若s > dn/2）。这些结果基于一种将度偏差和最大特征值与低维非线性优化问题相关联的平滑技术。论文发表在《Discrete Optimization》。