论文标题
动态ERDőS-Rényi随机图的样品路径大偏差原理
A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
论文作者
论文摘要
我们考虑在$ n $顶点上的动态Erdős-rényi随机图（errg），其中每个边缘以$λ$打开，并以速率$μ$关闭，而与其他边缘无关。重点是对相关经验图形在$ n \ to \ infty $中的演变分析。我们的主要结果是观察到的经验图形样品路径的大偏差原理（LDP），直到固定时间范围为止。速率为$ \ binom {n} {2} $，速率函数是Graphon轨迹空间上的特定动作积分。我们应用LDP来识别（i）从常数Graphon开始的最有可能的路径，它会创建具有非典型密度为$ d $ regregular子图的图形，以及（ii）两个给定的图形之间的主要路径。事实证明，分叉可能发生在相关的变异问题的解决方案中。
We consider a dynamic Erdős-Rényi random graph (ERRG) on $n$ vertices in which each edge switches on at rate $λ$ and switches off at rate $μ$, independently of other edges. The focus is on the analysis of the evolution of the associated empirical graphon in the limit as $n\to\infty$. Our main result is a large deviation principle (LDP) for the sample path of the empirical graphon observed until a fixed time horizon. The rate is $\binom{n}{2}$, the rate function is a specific action integral on the space of graphon trajectories. We apply the LDP to identify (i) the most likely path that starting from a constant graphon creates a graphon with an atypically large density of $d$-regular subgraphs, and (ii) the mostly likely path between two given graphons. It turns out that bifurcations may occur in the solutions of associated variational problems.
