The Bohman‐Frieze process near criticality
The Bohman‐Frieze process near criticality
复制标题
BohmanâFrieze 工艺接近临界点
DOI：
10.1002/rsa.20437
复制
发表时间：
--
影响因子：
1
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
M. Kang;W . Perkins;J. Spencer
Erdens-Rényi过程从一个有n个顶点的空图开始，边随机添加到图中。埃尔德什和雷尼的一个经典结果表明，埃尔德什-雷尼过程经历相变，当边数达到n/2时（我们说在时间1时），出现巨分支。自从Erdés和Rényi的这项开创性工作以来，各种随机图模型已经被引入和研究。本文研究了Bohman-Frieze过程，它是Erdens-Rényi过程的一个简单变形，也是从n个顶点的空图开始的.在每一步中给出两条随机边，如果第一条边将连接两个孤立的顶点，则将其添加到图中;否则添加第二条边。我们提出了几个新的结果的Bohman-Frieze过程的相变。我们发现，它有一个定性相似的相变的Erdens-Rényi过程的大小和结构的组件附近的临界点。我们证明了所有的分支都是树或单圈分支，并且最大的分支的大小为Ω（tc-logn）。此外，attc+，除了巨分支之外的所有分支都是树或单循环的，第二大分支的大小是Θ（-2logn）。这些结果中的每一个都对应于Erdens-Rényi过程的类似的众所周知的结果。我们的证明技术包括组合参数，随机过程的微分方程方法，以及满足准线性偏微分方程的磁化率矩母函数的奇异性分析。© 2012 Wiley Periodicals，Inc.随机结构算法，2013
The Erdős‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erdős and Rényi states that the Erdős‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erdős‐Rényi process.The Bohman‐Frieze process also begins with an empty graph onnvertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erdős‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at timetc− ϵ (that is, when the number of edges are (tc− ϵ)n/2) are trees or unicyclic components and that the largest component is of size Ω(ϵ‐2logn). Further, attc+ ϵ, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(ϵ‐2logn). Each of these results corresponds to an analogous well‐known result for the Erdős‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Mihyun Kang;T. Luczak
通讯作者：
T. Luczak
影响因子：
1
作者：
Tomasz Łuczak
通讯作者：
Tomasz Łuczak
Achlioptas 过程中的哈密顿度阈值
影响因子：
1
作者：
Michael Krivelevich;E. Lubetzky;B. Sudakov
通讯作者：
B. Sudakov
随机 2-复合体的同源连通性
DOI：
--
发表时间：
2006
期刊：
Comb.
影响因子：
--
作者：
N. Linial;R. Meshulam
通讯作者：
R. Meshulam
DOI：
--
发表时间：
2008
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
Mihyun Kang;T. G. Seierstad
通讯作者：
T. G. Seierstad