Large deviations for subcritical bootstrap percolation on the random graph
Large deviations for subcritical bootstrap percolation on the random graph
复制标题
随机图上亚临界自举渗透的较大偏差
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Brett Kolesnik
中科院分区：
文献类型：
--
作者：
Omer Angel;Brett Kolesnik
在Bootstrap渗流中，图中的一些顶点最初是活动的，而其他顶点如果最终有$r$活动的邻居，则会变为活动的。对于ErdőS-Renyi图中一小部分最初活跃的顶点最终激活多个非典型顶点的事件，我们给出了大偏差率函数。为此，我们通过古西诺夫的离散变分法比较了动力学的轨迹。这补充了Janson、Łuczak、Turova和Vallier研究该模型的典型行为的基础工作，以及Torrisi、Garetto和Leonardi最近在超临界大偏差方面的工作。作为应用，我们得到了激活整个图的最小集大小的下界，改进了Feige，Krivelevich和Reichman最近得到的下界。
In bootstrap percolation, some vertices in a graph are initially active and others become active if eventually they have $r$ active neighbours. We identify the large deviations rate function for the event that a small set of initially active vertices eventually activates atypically many vertices in the Erdős-Renyi graph. To this end, we compare trajectories of the dynamics, via Guseinov's discrete calculus of variations. This complements the fundamental work of Janson, Łuczak, Turova and Vallier, which studies the typical behaviour of the model, and the recent work of Torrisi, Garetto and Leonardi on supercritical large deviations. As an application, we obtain lower bounds for the size of the smallest sets that activate the entire graph, improving those recently obtained by Feige, Krivelevich and Reichman.