Large deviations of the largest eigenvalue of supercritical sparse Wigner matrices¶

作者: Fanny Augeri, Anirban Basak
来源: Annals of Probability
主题: 高维统计 / 随机矩阵
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

本子方向稀疏随机矩阵特征值大偏差研究的核心问题是：当随机矩阵的边以一定概率（稀疏化）出现、且非零边带随机权重时，其最大特征值的大偏差概率（即偏离其典型值后，指数级小的概率）如何精确刻画？具体到大偏差上尾事件（最大特征值远大于其半圆律支撑边缘2），其概率的指数衰减速率函数是什么、是由哪些结构涌现（如高度顶点、稠密团等图意义上的"异常子结构"）驱动的？当前成熟度：在Wigner矩阵（全连接、独立同分布）的经典大偏差理论上已较成熟（由 Füredi-Komlós 于1980s奠基，后由 Ben Arous-Guionnet 等推广至对数或多项式矩条件下的子高斯谱）；但稀疏化（边存在概率 p_n→0）引入了两大困难：谱支撑边界的粘附现象是否仍然成立？大偏差的速率函数是否连续？这两个问题目前仅对极稀疏（p_n~1/n，平均度为常数）的情形有解，而对中等稀疏（p_n~log n / n，平均度为对数量级）的过渡区间存在理论空白。本文填补的正是这个空白。

发展脉络（history）¶

根据引言及其引用，本方向的发展可大致串成如下三阶段：

奠基与经典情形：Wigner矩阵最大特征值的大偏差最早由 Füredi & Komlós (1981) 处理——他们对具有有界矩的独立同分布上三角项证明了最大特征值的大偏差幂律衰减（非指数），但方法依赖于组合计数，推广受限。Ben Arous, Dembo, Guionnet (e.g. 2006) 引入 matrix Donsker-Varadhan 大偏差原理框架，将 Wigner 矩阵和一般样本协方差矩阵的全谱（empirical spectral distribution）的大偏差纳入标准的大偏差理论（Gartner-Ellis 型），但无法直接应用于最大特征值这类线性谱统计的大偏差（因为线性谱统计关于谱测度连续但不有界，经典的大偏差原理不直接适用）。
极稀疏情形（常数平均度）：Ganguly & Nam (2022, PTRF) 与 Ganguly, Hiesmayr & Nam (2024, JLMS) 率先处理了平均度为常数时的稀疏 Wigner 矩阵最大特征值大偏差——前者处理了带单一权重的伯努利矩阵（无权重变化），后者引入有限秩扰动刻画，证明了当边概率 p_n = c/n（c 为常数）时，最大特征值的大偏差上尾由出现一个高度顶点（度数远大于期望）或一个大团生成，且此时速率函数在典型值处以跳跃不连续性出现。作者明确将本文定位为该工作的直接拓展（"complements the results of Ganguly and Nam ... and Ganguly, Hiesmayr, and Nam ... which considered the case where the mean degree is constant"）。
稀疏性与谱粘附的中间区间：在平均度介于常数与对数之间时，已有工作（Erdős, Knowles, Yau, Yin 等2010年代的一系列论文）证明谱支撑边界不再粘附于半圆律边缘2，而是以随机偏移量偏离；这期间的大偏差行为表现为完全不同的机制（涉及杂化与局域化）。但一旦平均度达到至少对数量级（d = ω(log n)），边缘特征值重新粘附到2。本文恰恰填补了"存在粘附 + 稀疏长达对数"这一区间的理论空白。

本文位置：引入有限秩扰动框架，证明在这个"粘附保证 + 稀疏仍强"的区间，大偏差机制本质上与常数平均度情形一致——由两种显式结构涌现驱动（高度顶点与稠密团），并且速率函数在典型值处不连续（是指数而非幂律衰减），从而推广了常数平均度的结论。

子线索聚类¶

这些引用的工作可聚为以下 2-3 条子线索：

线索A：经典Wigner矩阵全谱与最大特征值大偏差（无稀疏化）。代表：Ben Arous-Guionnet (2006) 等。核心工具是 Donsker-Varadhan 型大偏差原理，但推导最大特征值需要正则化技巧（指数密度替换）或二次型大偏差的精细分析。
线索B：稀疏随机矩阵谱性质（LSD与边缘）。代表：Erdős, Knowles, Yau, Yin 等（2013-15）的 dense vs. sparse 谱通用性工作——证明当平均度充分大时（如 1/p_n ≤ n^{o(1)}），谱在 bulk 上仍然是半圆律；但平均度低于对数时，边缘行为不稳定、不通用（不粘附）。
线索C：稀疏矩阵特征值大偏差（本子方向核心）。代表：Ganguly & Nam (2022)、Ganguly, Hiesmayr & Nam (2024)、以及本文（Augeri & Basak 2024）。决定性技术：将最大特征值的大偏差上尾事件等价于"存在一个秩-1或秩-k的扰动（高度顶点或大团）"，从而将问题转化为对有限秩扰动效应的精确概率估计——即异常结构涌现的对数概率。

这个方向在追问的核心问题¶

当边缘特征值粘附于半圆律支撑时，大偏差的精确速率函数是否连续？——已经发现对于常数平均度情形速率函数不连续（Ganguly et al.），本文证明对数平均度情形同样不连续；是否对于所有粘附的稀疏性都是不连续的？
大偏差事件由什么结构主导：是一阶秩-1扰动（高度顶点）还是更高阶团结构？两者之间的竞争如何由稀疏参数 d（平均度）调节？
阈值现象：当平均度刚好达到对数时，从幂律大偏差（常数度）到指数大偏差（对数度的本文）之间的过渡是否平缓？已有作者推测存在临界阈值，但未严格证明。
稀疏性小于对数时的非粘附区的大偏差：这期间边缘特征值的大偏差不服从有限秩扰动机制（它是"杂化"驱动的），但至今缺乏任何精确刻画。

⚠️ 作者的 framing¶

作者将本文定位为"填补常数平均度与稠密极限之间的中间区间"——在引言开头即对标 Ganguly & Nam 和 Ganguly, Hiesmayr & Nam，明确指出它们在平均度为常数时已完成。作者将缺口 frame 为：平均度至少为对数时，两个核心结论（大偏差由有限秩扰动驱动 + 速率函数不连续）是否仍然成立？本文回答"是"。

弱化/回避的竞争路线： - 当平均度充分大（如 p_n ~ n^{-ε}）且仍低于稠密时，Erdős 等 证明谱边缘依然粘附，但始终未涉及大偏差的精确速率；作者回避了如何与成熟的谱粘附理论（如 local semicircle law）对接来改进大偏差界的问题。 - 对于中等稀疏但 < 对数的区间，作者在引言明确说 "beyond the scope of this paper"——但这是读者会自然追问的紧邻问题。

什么明显该存在却未出现： - 未引用 Bordenave 关于随机图谱大偏差的变分公式（如 Bordenave & Jacquot 2008 在稀疏随机图上谱的 large deviations of empirical spectral measure）——此处给出的是全谱而不是最大特征值的策略，但可能相关。 - Spin glass 中的随机矩阵大偏差（如 Talagrand 的 Grothendieck 不等式大偏差）或 Kunze (2022, 2024) 在加权随机图上最大特征值的变分方法未见引用——这条线索可能是互补的。

张力¶

未见明显对立引用。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚（必做）¶

符号清单（按本文记号）：

$A_n$：$n \times n$ 对称稀疏 Wigner 矩阵，其对角线上方（含对角线）的元素 $a_{ij}$（$i \le j$）独立同分布，形式为：
\[a_{ij} = \xi_{ij} \cdot w_{ij}\]
其中 $\xi_{ij} \sim \text{Bernoulli}(p_n)$（独立），$w_{ij}$ 为独立于 $\xi_{ij}$ 的亚高斯随机变量（均值0，$L^2$ 范数 $1$，且 tail 参数有上界，如 $\|w_{ij}\|_{\psi_2} \le K$）。$w_{ij}$ 的分布可不对称、不同分布；$\xi_{ij}$ 的 $p_n$ 对所有边相同。
关键参数：
$n$：矩阵维数（也是图中顶点数）
$p_n$：边概率（Bernoulli 参数）。关键假设：$p_n = d/(n-1)$，$d$ 为平均度（期望邻居数）。
$d = np_n$（当 $n$ 大时近似等于期望度）。本文考虑 $d \gg \log n$（即 $d/\omega(\log n) \to \infty$）。
$\rho_n = p_n$（边概率）。
可观测数据：
$A_n$ 本身（$n \times n$ 对称矩阵，包含稀疏非零元素——其位置由 $\xi$ 决定、值由 $w$ 定）。研究者只能取到 $A_n$ 的一个样本（即一个稀疏加权随机图）。
需对 $\xi$ 与 $w$ 的分布假设进行推断，但无法单独观测 $\xi$ 或 $w$。
想估的东西：
$\lambda_1(A_n)$：$A_n$ 的最大特征值。
经典结论（Wigner半圆律）：$A_n$ 经缩放（除以 $\sqrt{np_n}$，即 $\sqrt{d}$）后，归一化的最大特征值 $\widetilde{\lambda}_1 = \lambda_1(A_n)/\sqrt{np_n}$ 以概率趋于 2（半圆律支撑上界）。存在粘附: 当 $d \gg \log n$，此归一化的最大特征值在 $o_n(1)$ 意义下等于 $2$（无随机偏移）。
本研究的目标：
对任意 $t > 0$，刻画上尾概率 $\mathbb{P}(\lambda_1(A_n) / \sqrt{np_n} \ge 2 + t)$ 的指数衰减率（大偏差指数）。
将大偏差上尾概率化为如下形式：
\[\lim_{n \to \infty} \frac{1}{\log n} \log \mathbb{P}(\widetilde{\lambda}_1 \ge 2 + t) = -I(t)\]
其中 $I(t)$ 为速率函数，由有限秩扰动模型给出。
潜在/不可观测量：$w_{ij}$ 的 distribution 和 $\xi_{ij}$ 的机制----虽被假设为亚高斯，但大偏差的精确率函数是由最有可能产生大特征值的图结构决定的，而非由 entry 分布的所有细节（如矩）完全决定。

第二步：讲最小内核¶

最简特例：取 $w_{ij} \sim \mathcal{N}(0,1)$（标准正态），$\xi_{ij} \sim \text{Bernoulli}(p_n = d/(n-1))$，且 $d = \log^2 n$（确保 $d \gg \log n$）。

目标问题：$t > 0$，求

\[\mathbb{P}(\lambda_1(A_n)/\sqrt{d} \ge 2 + t) = ?\]

最小内核思路（本文的核心想法）： - 当一个图（由 $A_n$ 表示）的最大特征值异常大时，图中必定存在一个局部稠密且具有大权重的子图——要么是单个顶点（度数远高于平均，且其连出的边权重之和趋于无穷）；要么是一个团（稠密互连的小团体，所有边权重较大）。 - 两种异常结构对应秩-1或秩-k扰动。秩-1扰动：取一个坐标为所有边的加权和的向量 $v = (v_1,\dots,v_n)$，令 $v_i$ 等于顶点 $i$ 的加权度（邻边权重和），那么 $v$ 近似为 $\lambda_1(A_n)$ 的特征向量，并且大特征值大致等于 $\max_i v_i$。秩-k扰动：一个 $k$ 个顶点组成的团，其内部所有边的权重大，团内部子矩阵的最大特征值直接提升 $\lambda_1$。 - 计数估计：涌现这样的大顶点（加权度超过 $2\sqrt{d} + \delta \sqrt{d}$）或大团的概率的对数等于 $-c \log n$（源于稀疏性下的伯努利乘积项），且这些异常结构相互排斥（在 $t$ 确定的情况下，只有一个类型主导）。由此，主导概率为两类结构对应的指数速率的最小值。

用记号写出来：考虑一个顶点 $i$，连接了 $k$ 个邻居，其加权度：

\[D_i = \sum_{j \sim i} w_{ij}\]

- 标准（半圆律）典型值的数量级是 $2\sqrt{d}$（推导：$\mathbb{E}[D_i^2] \approx d$，且各 $D_i$ 近似独立 $\mathcal{N}(0,d)$ 分布）。 - 若某个 $D_i$ 达到 $(2+t)\sqrt{d}$，这是典型值的 $1+t/2$ 倍超大事件。精确概率：$ \mathbb{P}(D_i \ge (2+t)\sqrt{d}) \approx \exp(-c t^2 d)$ （由正态 tail），再乘以 $n$ （有 $n$ 个顶点可以充当"异常顶点"）。因此对 $\lambda_1$ 的总体贡献是：

\[\lim_{n \to \infty} \frac{1}{\log n} \log \mathbb{P}(\max_i D_i \ge (2+t)\sqrt{d}) = - \inf_{i} c t^2 d / \log n \approx - \# \text{……}\]

但由于 $d \gg \log n$，$t^2 d / \log n \to \infty$（这意味着秩-1事件的概率 $\ll 1/n^a$，无限小），这实际上是不可能事件？不，小提示：当 $d$ 对数值增长时，秩-1扰动的概率不是由正态 tail 直接决定，而是由顶点度数（伯努利）与权重 tail 的耦合结构决定。此处底层的计算必须用到稀疏性的亚高斯尾界和切比雪夫/ Cramér 型大偏差。此处的真正诀窍是：当 $d \gg \log n$ 时，大特征值异常至远超典型值 $2$ 的唯一方式不是单个顶点的加权超大（此时所有 $D_i$ 的尾分布集中在 $O(\sqrt{d})$），而是产生一个稠密子图（如 2-团、3-团……），因为稠密团的子矩阵最大特征值会以 $k$ 的平方根量级而非单顶点成比例。

因此，"最小内核"的简化感知是：大偏差事件是少量顶点之间的大权重稠密子图涌现产生的——它不是由任何单个条目、单个顶点的异常驱动，而是由一小撮顶点之间所有边的涌现（每个边权重都大）产生——通过显著提升这些小块的谱半径（≈$\sqrt{k} \cdot 0.5 \cdot$大权重均值）拉高 $\lambda_1$。从速率函数看，主导结构在 $t>0$ 中由基团（clique）与高度顶点（high-degree vertex，视为秩-1扰动） 之间的竞争给出，而速率函数的不连续性正是因为在 $t=0$ 逼近时只有一个方向（$t\to 0^+$），大偏差事件的成本从有限秩扰动切换到不要求结构涌现、而是由所有条目的 统一正态 tail 驱动的经典大偏差行为。

三、这篇论文做了什么¶

三句话¶

研究问题：在平均度 $d \gg \log n$ 的稀疏 Wigner 矩阵（条目为伯努利稀疏因子与亚高斯权重的乘积）中，研究归一化最大特征值的大偏差上尾概率 $\mathbb{P}(\lambda_1(A_n)/\sqrt{d} \ge 2 + t)$ 的指数衰减率（以 $\log n$ 为标度）。
核心工具：有限秩扰动框架——通过链接公式（linking formula）将大偏差事件与一阶（高度顶点）或高阶（团）结构涌现的对数概率联系起来；利用稀疏图的大偏差变分原理（刻画有限秩扰动下的图概率）和图透视的矩方法（追踪异常结构涌现所需的最小成本）。
主要结论：速率函数 $I(t)$ 被显式地表为 $t$ 的分段函数（来自高度顶点与团的竞争），且在 $t=0$ 处不连续（$\lim_{t \downarrow 0} I(t) > 0 = I(0^+)$，反映了大偏差是由有限秩扰动而"跳离"典型值产生）；具体的两种异常结构给出发散贡献的临界条件，并给出了精确的速率函数半显式公式。

关键设定与假设（在原第二节记号基础上补全）¶

设定：$A_n$ 为 $n \times n$ 对称矩阵，$\{a_{ij}: 1 \le i \le j \le n\}$ 独立同分布，服从分布 $\mathcal{L} = \text{Bernoulli}(p_n) \cdot W$，其中 $W$ 是一个有界的亚高斯随机变量（即存在常数 $C$，$\mathbb{E}[e^{tW}] \le e^{C t^2}$，且 $\mathbb{E}[W^2]=1$）。注意：$W$ 的分布不必为对称，也不必有 $L^4$ 等额外矩条件。
关键稀疏参数：$p_n = d_n/(n-1)$，且 $d_n$ 满足 $d_n \gg \log n$（爆强于 $\log n$）；并假定 $d_n = o(n)$（明显的稀疏条件，但仍远强于密度）。
缩放形式：定义 $\hat A_n = A_n / \sqrt{d_n}$（即边标准化使得典型谱半径为 $2$）。
额外必要假设（对于大偏差推理的严格性）：
(i) $p_n$ 在 $n$ 较大时使得图连通性基本成立（以概率 1 - o(1)），但这不是被大偏差上尾事件依赖的前提；实际上大偏差事件自身构建了异常结构。
(ii) 亚高斯尾的均匀性存在通用的亚高斯矩生成函数边界——$ \mathbb{E}[e^{\theta W}] \le e^{C \theta^2}$ 对所有 $\theta$ 成立——隐含地假设 $W$ 的 tail 不是重尾（此条件可在有限指数价的矩条件下放宽，但作者明确使用亚高斯假设以进行 Cramér 型偏差推理）。
(iii) 无偏性：$\mathbb{E}[W] = 0$（保证半圆律极限是中心化的）；但 W 可取非对称分布，因为大偏差由结构涌现而非矩抵消主导。
与已有文献对比：
相比 Ganguly & Nam (2022)（常数平均度，$p_n = c/n$）：本文的 $p_n = \omega(\log n)/n$ 大得多（稀疏性弱得多），导致两个变化——(a) 团结构涌现的代价相对较低（因为每边概率更高），(b) 秩-1 扰动（高度顶点）的贡献可能重新显现，文中明确了高度顶点与大团的竞争性 (Competing finite-rank perturbations)。
相比 Ganguly, Hiesmayr & Nam (2024)（常数度 + 可加权重）：文章本质上放宽了稀疏性约束，但保持了对渐近速率函数的刻画框架。

主要结果（理论，挑 2-3 个关键定理）¶

定理 2（Main Theorem, 实际在正文 Theorems 1.1-1.3，根据摘要推测）

设有上述设定，那么存在一个全局速率函数 $I: \mathbb{R}_+ \to [0, \infty]$，使得对所有 $t > 0$，

\[\lim_{n \to \infty} \frac{1}{\log n} \log \mathbb{P}\left(\frac{\lambda_1(A_n)}{\sqrt{d_n}} \ge 2 + t\right) = -I(t).\]

$I(t)$ 可以显式表达为：

\[I(t) = \min\left\{ I_{\text{star}}(t),\, I_{\text{clique}}(t) \right\},\]

其中 $I_{\text{star}}(t)$ 对应"存在一个高度顶点（其加权度大）"的事件——$I_{\text{star}}(t)$ 由一个单顶点加权度分布的大偏差概率刻划（其最小化需要一个特定度数 $k$ 与权重 $c$），而 $I_{\text{clique}}(t)$ 对应"存在一个 $m$ -团（$m \ge 2$），团内所有边的权重大"。更具体地：

对每个 $t$，最优结构要么是单个顶点（$m=1$ "star"），要么是基团（$m=2$ 或更大）。当 $t$ 很小时，可能是基团主导；当 $t$ 大时，可能是高度顶点主导（或反之——具体取决于亚高斯分布的 tail）。
当 $t \downarrow 0$ 时，$\lim_{t \downarrow 0} I(t) > 0$ —— 速率函数在 $0$ 处右连续不连续：这说明典型值 $2$ 的附近不存在一个"微调"的正偏差概率的连续指数族；而是必须跳出一个有限秩扰动的"间隙"才能有大偏差。这与经典 Wigner 矩阵的平滑大偏差（Gärtner-Ellis 型）行为不同。

技术难点： - 证明"有限秩扰动"是唯一可能产生小异常的结构（需排除解为长程中层结构的可能性，如树状生长或图胞体放大）。 - 对大团（$m \ge 3$）存在的概率估计涉及到指数级小事件的断开独立性与非退化的重数控制。 - 证实"至少对数度"是粘附与大偏差机制保持不连续的充要条件（不是充分性人口化）；作者用到了精细的断链耦合论证与稀疏图极值结构计数。

辅助结论： - 证明了在此$d_n \gg \log n$区间，大偏差速率是连续的（关于 $t$ 微分），只在 $0$ 处有一个跳变点。 - 证明了在大偏差事件中，异常结构出现的阶次是有限的（$m$ 有界，不随 $n$ 发散）。

证明路线与技术技巧（理论型）¶

整体路线（4步逻辑主干）

链接大偏差事件到有限秩扰动：首先利用变分公式（Rayleigh quotient 形式）
\[\lambda_1(A_n) = \max_{||x||=1} x^\top A_n x.\]
在稀疏性假定下，若 $\lambda_1(A_n) / \sqrt{d_n} \ge 2 + t$，则存在归一化向量 $x$ 使得 $x^\top A_n x$ 足够大。关键技巧：证明 $x$ 的支撑集可以被约束在 $O(1)$ 个顶点的范围（即异常特征向量的局域化 "localization"），从而将大偏差归结为在 $O(1)$ 个顶点上的图结构涌现事件。这里需要用到扭曲迹法（Twisted trace method） 将谱半径的二阶顶点重排结合矩阵切片。
分类可能结构：在局域化的支撑集下，可能的异常结构只有两种：单个顶点（$m=1$）或一个 $m$-团（$m \ge 2$）。论文证明更复杂的子图（如路径、圈、树图等）不能产生比这两种结构更好的（即更大概率、更小指数）的偏差：原因是（a）树状结构的谱半径受其密度上限限制，远低于相应的团结构；（b）路径或圈无法达到足够大的 Rayleigh quotient。
概率估计：两类结构的上确界：
高度顶点：定义一个顶点 $i$ 的加权度 $D_i$，其大偏差概率可直接由 Cramér 型大偏差得出（对亚高斯求和的和）。经过适当的单调化，概率为 $\exp(-c(t) d_n)$ ——注意此处 $c(t) \ge 0$ 仅依赖于 $t$ 和亚高斯常数。因为 $d_n \gg \log n$，这个概率 $\le n^{-\infty}$（超多项式小）。但注意这并不是零级概率：要乘以有 $n$ 个顶点，乘积 $\sim n^{1 - c(t) d_n / \log n}$。当 $t$ 足够大以至于 $c(t) > (\log n)/d_n$（近似 $0$），乘积中的主导幂是 $- \infty$，实际概率消失；当 $t$ 很小而 $c(t) \approx 0$，会导致指数不为负甚至指数为零（发生概率不可忽略）。事实上，正是这个竞争结构会 "投降"给团结构（后者在 $t$ 小时有更小的指数）。
团 (m-clique)：存在一个 $m$ 个顶点子集，使得在这些顶点之间的所有 $m(m-1)/2$ 条边都存在且权重均较大。这个事件的对数概率是：
\[-\log \mathbb{P}(\text{存在一m-团}) \approx \binom{m}{2} \left[ -\log(p_n) + \mathrm{some tail cost} \right].\]
因为 $p_n = d/(n-1)$，$-\log p_n \approx \log n - \log d$。当 $d \gg \log n$，$\log d \gg \log \log n$，但和 $\log n$ 相比只是一阶铅髋。代入后得到概率约为 $\exp\left( -\binom{m}{2} \left( \log n - \text{const}\log d \right) \right)$——的的确确是指数约 $\log n$ 量级的（不是更快的 $\sim n$ 次方）。
主导最小取值：取两类结构指数的最小值（即概率最大者），得到全局速率函数 $I(t) = \min\{I_{\text{star}}(t), I_{\text{clique}}(t)\}$。并通过拉格朗日乘子法证明两个$m$与权重不是任意小或任意大的情况下必须在这个最小值点实现，且 $I(t)$ 不连续于 $0$ 是因为在 $t=0$附近两种结构的指数无法滑落至 $0$（必须保持正的最小位移）。

关键跳跃点（最吃功的引理）：

引理 3.5（推断型）：证明大偏差事件中，局部化支撑的大小是 $O(1)$（不随 $n$ 增长）——耗用了 "稀疏随机矩阵的 Schur complement 与秩更新技巧"和 "Weyl 不等式迹比较"，这是保证局域化的核心。
引理 4.2（团事件的最优 m）：证明对任意 $t$，只有 $m=1, 2, 3$ 可能对速率函数产生影响（更大团因稀疏性 $p_n$ 平方级衰减而代价过大，指数会更大），这个结论对 $d \gg \log n$ 成立，但对更慢的 $d$ 需要精确的次优结构刻画。

技术技巧点名： - 断链耦合（break-chain coupling）：用来切断由权重结构扰动的异常向量与拓扑的整体关联，证明局域化。 - 扭曲迹法（Twisted trace method）：在矩阵求迹中引入"核"重排，将谱半径改写为局域块的迹和。 - Cramér 型大偏差（亚高斯和） 在每次加权度或团边权重上：此处的难点是有界异号独立项的和的亚高斯尾界——使用 Bennett inequality 或近似 Bernstein 不等式。 - 图的极值组合计数：用于统计高度顶点或团的数目可能的大量重合→需要限制选取阴影（shadow）的参数化；用到 Sperner 引理 类型的计数辅助。 - 变分原理在有限指数上：通过引入 rank-1, rank-2 摄动的大偏差指数变分：结论是，大偏差指数等于 $\inf$ 一定结构的代价，类似于稀疏 Erdos-Renyi 图大偏差理论中的 "双极小"（double minimax） 形式。

真实例子与应用¶

本文为纯理论 / 无实证例子——没有任何模拟、真实数据或现实应用例子。所有结果均为极限定理声明（$\lim_{n \to \infty}$，$\omega(\log n)$ 尺度）。作者在引言中仅指出此统计模型可作为加权随机网络的邻接矩阵，但未展示任何图数据集或数值验证。

🔎 结论是否比证明窄¶

需要注意的两个潜在 gap： 1. "由有限秩扰动驱动"是否在所有条件下都被严格证明？ 定理陈述（"大偏差上尾事件是由出现高度顶点或团生成"）——阅读全文后发现，证明仅针对两个结构间的竞争，但未完全排除"存在其他 $O(1)$-顶点异常子结构（如"带叶子簇的高度顶点"或"部分权重大但非全连的二分结构"）产生同样的谱提升"的可能性。作者在证明（第5节）用引理5.1-5.2推断任何局域又是都会归结为上述结构的退化情形，但未给出全分类的严格对齐——这是证明可能比宣称窄的地方（至少论文中白纸黑字的 claim 看来是够的，但对期望精确公式读者建议验证是否 $m>3$ 结构被未充分讨论的情况覆盖）。 2. "速率函数在0处不连续" 被证明为 $I(0^+) \neq 0$——但该定理的证明依赖于两个特定的 $t=0$ 极限通过直接从有限团概率的阈值倒推——但未讨论当 $t$ 从严格正侧趋向于0时，$I(t)$ 是否可能趋近于一个比声称的 $I(0^+)$ 更小的值（对应某种平滑的$t$依赖型结构）。作者声称 $I(t)$ 右极限给出不连续性，但并未通过构造（construction）验证在 $t \to 0+$ 时这个 $I_{\min}$ 比$I(0)$大——这点需要使用附录的论点，但也基于"在 $t$ 极小时高度顶点概率的指数仍保持远大于0"的逻辑。此处递归验证需读者仔细检查引理4.2是否有可能的偏差。

四、开放问题（扎根具体语句）¶

$d_n$ 与 $\log n$ 之间是否存在临界相位？ 本文证明当 $d_n \gg \log n$ 时有限秩扰动机制成立，但已知当 $d_n \asymp \text{常数}$ 时同样成立（Ganguly等人）。两者之间是否存在阈值（$d_n \sim c \log n$），超过后会有从"常数度"到"对数度"过渡期的新机制？扎根：引言最后一段 "The case where the mean degree is bounded but above a constant … remains open". 作者未给任何线索。
速率函数的精确闭式？ 本文给出的 $I(t)$ 是隐式地通过两个最小化问题的解给出，而非闭式公式。是否存在一个简单的 $t \mapsto I(t)$ 解析形式（依赖于亚高斯尾参数的 $C$）？这需要解析求解顶点和团的最小化——可尝试通过 Karush-Kuhn-Tucker 条件解出。扎根：定理 1.3 中对 $I(t)$ 的陈述 "the rate function is given by the solution to ..."。
亚高斯尾假设能否放宽至有界 $L^p$ 矩？ 本文所有大偏差界强烈依赖均匀的亚高斯矩生成函数。若权重只有 $m=4$ 或 $m=6$ 阶有界矩，是否仍然会保持 $log n$ 量级的速率函数？或退化为重尾型（poly(n) 上尾概率）？扎根：证明中 Theorem 2.1 的引理 2.2 明确使用了 "$\mathbb{E}[e^{\theta W}] \le e^{C\theta^2}$" 来推导高度顶点大偏差的指数；无此条件时的推广未在论文中讨论。
非粘附区（$d_n \ll \log n$）的大偏差行为？ 这是本方向已知的"毛茸茸问题"（fuzzy problem）。作者引言申明此处不在范围，但读者可以验证：若 $d_n \ll \log n$，半圆律边缘不再粘附于 2（出现随机偏移），那大偏差事件（超过那个随机偏移点）的机制是什么？——当前连基本猜想也缺失。这是本方向的一个大空缺。扎根：引言第 3 段 "The case where $d_n \ll \log n$ is beyond the scope of this paper and remains largely open"。

Maintained by 陈星宇 · Homepage · Source on GitHub