论文标题
程度限制的随机过程远非统一
The degree-restricted random process is far from uniform
论文作者
论文摘要
程度限制的随机过程是一种天然算法模型，用于生成具有度序列d_n =（d_1，\ ldots，d_n）的图形：从空的n-vertex图开始，它顺序添加了新的随机边缘，以使每个顶点v_i的度数最多保留在D_I中。 1999年，蠕虫的猜想是，对于d等级序列d_n，该过程的最终图类似于均匀的随机d和图形。 在本文中，我们表明，对于不规律的程度序列D_N，限制性随机过程的最终图与具有度序列d_n的均匀随机图大不相同。组合证明技术是我们的主要概念贡献：我们将切换方法适应度限制过程，表明该枚举技术也可以用于分析随机过程（而不是像以前一样仅仅是统一的随机模型）。
The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1, \ldots, d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform random d-regular graph. In this paper we show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. The combinatorial proof technique is our main conceptual contribution: we adapt the switching method to the degree-restricted process, demonstrating that this enumeration technique can also be used to analyze stochastic processes (rather than just uniform random models, as before).
