Universality for bounded degree spanning trees in randomly perturbed graphs
Universality for bounded degree spanning trees in randomly perturbed graphs
复制标题
随机扰动图中有界度跨越树的普遍性
DOI：
10.1002/rsa.20850
复制
发表时间：
2019
影响因子：
1
通讯作者：
Böttcher J
中科院分区：
文献类型：
--
作者：
Böttcher J
我们解决了Krivelevich，Kwan和Sudakov关于随机扰动稠密图模型中所有有界度生成树的包含阈值的问题。更确切地说，我们证明了，如果我们从一个稠密的图Gαδ(Gα) ≥αNα>； 0)开始，再加上二项随机图G(n，C/n)，则图Gα∪G(n，C/n)同时包含最大度为Δ的所有生成树的副本的概率很高，其中C仅依赖于α和Δ。
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graphGαonnvertices withδ(Gα) ≥αnforα> 0 and we add to it the binomial random graphG(n,C/n), then with high probability the graphGα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, whereCdepends only onαand Δ.
登录
查看更多内容
更多集合、图表和数字
DOI：
10.1007/978-3-540-32439-3
发表时间：
2006
期刊：
ArXiv
影响因子：
--
作者：
E. Győri;G. Katona;L. Lovász;T. Fleiner
通讯作者：
T. Fleiner
随机扰动超图中的哈密顿性
DOI：
10.1016/j.jctb.2019.12.005
发表时间：
2020
期刊：
Series B
影响因子：
--
作者：
Han, Jie;Zhao, Yi
通讯作者：
Zhao, Yi
DOI：
10.1137/15m1032910
发表时间：
2015
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Michael Krivelevich;Matthew Kwan;B. Sudakov
通讯作者：
B. Sudakov
稀疏图的爆炸引理
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Peter Allen;Julia Bottcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
通讯作者：
Y. Person
添加随机边以创建汉密尔顿循环的平方
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Patrick Bennett;A. Dudek;A. Frieze
通讯作者：
A. Frieze