论文标题
稀疏随机图中的光谱边缘：上和下尾大偏差
Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large Deviations
论文作者
论文摘要
在本文中，我们考虑了估计Erdős-rényi随机图的边缘特征值$ \ MATHCAL {g} _ {n，p} $在$ p $的政权中，频谱的边缘不再由全球范围的ver量进行验证，而是由等级的数字进行统计，而是在$ p $的情况下进行$ p $的政权，而是在$ p $的情况下，而是由等级的数量来管理，而是在其中，估算了Erdős-rényi随机图$ \ Mathcal {g} _ {g} _ {n，p} $的问题的问题。本文超出了相关问题的均值近似值的最新发展，对整个制度的光谱边缘的巨大偏差提供了全面的处理，这特别包括研究良好的平均水平的经过良好研究的情况。特别是，对于$ r \ geq 1 $固定，我们确定了上面提到的制度中最大/小于$ 1 $的最高$ r $ eigenvalues共同$ r $ eigenvalues的渐近概率。 The proof for the upper tail relies on a novel structure theorem, obtained by building on estimates of Krivelevich and Sudakov (2003), followed by an iterative cycle removal process, which shows, conditional on the upper tail large deviation event, with high probability the graph admits a decomposition in to a disjoint union of stars and a spectrally negligible part. On the other hand, the key ingredient in the proof of the lower tail is a Ramsey-type result which shows that if the $K$-th largest degree of a graph is not atypically small (for some large $K$ depending on $r$), then either the top eigenvalue or the $r$-th largest eigenvalue is larger than that allowed by the lower tail event on the top $r$ eigenvalues, thus forcing a矛盾。以上论点将问题降低了可能具有独立利益的极大程度的大偏差理论。
In this paper we consider the problem of estimating the joint upper and lower tail large deviations of the edge eigenvalues of an Erdős-Rényi random graph $\mathcal{G}_{n,p}$, in the regime of $p$ where the edge of the spectrum is no longer governed by global observables, such as the number of edges, but rather by localized statistics, such as high degree vertices. Going beyond the recent developments in mean-field approximations of related problems, this paper provides a comprehensive treatment of the large deviations of the spectral edge in this entire regime, which notably includes the well studied case of constant average degree. In particular, for $r \geq 1$ fixed, we pin down the asymptotic probability that the top $r$ eigenvalues are jointly greater/less than their typical values by multiplicative factors bigger/smaller than $1$, in the regime mentioned above. The proof for the upper tail relies on a novel structure theorem, obtained by building on estimates of Krivelevich and Sudakov (2003), followed by an iterative cycle removal process, which shows, conditional on the upper tail large deviation event, with high probability the graph admits a decomposition in to a disjoint union of stars and a spectrally negligible part. On the other hand, the key ingredient in the proof of the lower tail is a Ramsey-type result which shows that if the $K$-th largest degree of a graph is not atypically small (for some large $K$ depending on $r$), then either the top eigenvalue or the $r$-th largest eigenvalue is larger than that allowed by the lower tail event on the top $r$ eigenvalues, thus forcing a contradiction. The above arguments reduce the problems to developing a large deviation theory for the extremal degrees which could be of independent interest.
