The order of the largest complete minor in a random graph
The order of the largest complete minor in a random graph
复制标题
随机图中最大完全次要的阶数
DOI：
10.1002/rsa.20215
复制
发表时间：
2008
影响因子：
1
通讯作者：
Fountoulakis N
中科院分区：
文献类型：
--
作者：
Fountoulakis N
设ccl（G）表示图G中最大完全子图的阶数（也称为收缩团数），Gn，p表示n个顶点上边概率为p的随机图.当p为常数时，Bollobás，Catlin，and Erdés（Eur J Combin 1（1980），195-199）渐近确定ccl（Gn，p）. Pittel和Wierman（Trans Am Math Soc 341（1994）721-748）给出了当p非常接近1/n（即在相变内部）时ccl（Gn，p）的界。我们证明了对每一个ε> 0，存在一个常数C使得当C/n< p< 1-ε时，渐近几乎必然ccl（Gn，p）=（1±ε）n/log_B（np），其中B：= 1/（1-p）.如果对于常数C> 1，p= C/n，则ccl（Gn，p）= Θ（n）。这扩展了（Bollobás，Catlin，and P. Erdás，Eur J Combin 1（1980），195-199）中的结果，并回答了Krivelevich和Sudakov（预印本，2006）的一个问题。随机结构算法，2008
Let ccl (G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let Gn, p denote a random graph on n vertices with edge probability p. Bollobás, Catlin, and Erdős (Eur J Combin 1 (1980), 195–199) asymptotically determined ccl (Gn, p) when p is a constant. Łuczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721–748) gave bounds on ccl (Gn, p) when p is very close to 1/n, ie inside the phase transition. We show that for every ε> 0 there exists a constant C such that whenever C/n< p< 1‐ε then asymptotically almost surely ccl (Gn, p)=(1±ε) n/log_b(np), where b:= 1/(1‐p). If p= C/n for a constant C> 1, then ccl (Gn, p)= Θ (n). This extends the results in (Bollobás, Catlin, and P. Erdős, Eur J Combin 1 (1980), 195–199) and answers a question of Krivelevich and Sudakov (preprint, 2006).© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008
登录
查看更多内容
随机图的拓扑派系
DOI：
--
发表时间：
1981
期刊：
J. Comb. Theory B
影响因子：
--
作者：
B. Bollobás;P. A. Catlin
通讯作者：
P. A. Catlin
浅层排除未成年人并改进图分解
DOI：
--
发表时间：
1994
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Serge A. Plotkin;Satish Rao;Warren D. Smith
通讯作者：
Warren D. Smith
扩展图中的未成年人
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Michael Krivelevich;B. Sudakov
通讯作者：
B. Sudakov
完全未成年人的极值函数
DOI：
10.1006/jctb.2000.2013
发表时间：
2001
期刊：
J. Comb. Theory B
影响因子：
--
作者：
A. Thomason
通讯作者：
A. Thomason
DOI：
10.1017/s0305004100061521
发表时间：
1984
影响因子：
0.8
作者：
A. Thomason
通讯作者：
A. Thomason