论文标题
稀疏随机图上贪婪独立集算法的大偏差
Large deviations of the greedy independent set algorithm on sparse random graphs
论文作者
论文摘要
我们在稀疏的Erdős-rényi随机图上研究贪婪的独立集算法$ {\ MATHCAL G}（N，C/N）$。 $ p $的范围由于$ c = e $的阈值而引起了人们的关注，除此之外，贪婪的算法受到独立套装景观的突然变化的影响。 Bermolen等人最近建立了一个较大的偏差原理。 （2020）但是，证明和费率函数有些涉及。速率函数的上限是由Pittel（1982）较早获得的。通过离散的演算，我们确定实现给定较大偏差的最佳轨迹，并以简单的封闭形式获得速率函数。特别是，我们表明皮特尔的界限很清晰。证明是简短而基本的。我们认为，此处介绍的方法将有助于分析其他随机增长和勘探过程的尾巴行为。
We study the greedy independent set algorithm on sparse Erdős-Rényi random graphs ${\mathcal G}(n,c/n)$. This range of $p$ is of interest due to the threshold at $c=e$, beyond which it appears that greedy algorithms are affected by a sudden change in the independent set landscape. A large deviation principle was recently established by Bermolen et al. (2020), however, the proof and rate function are somewhat involved. Upper bounds for the rate function were obtained earlier by Pittel (1982). By discrete calculus, we identify the optimal trajectory realizing a given large deviation and obtain the rate function in a simple closed form. In particular, we show that Pittel's bounds are sharp. The proof is brief and elementary. We think the methods presented here will be useful in analyzing the tail behavior of other random growth and exploration processes.
