Universality for bounded degree spanning trees in randomly perturbed graphs

被引：29

作者：

Boettcher, Julia ^{[1
]}

Han, Jie ^{[2
]}

Kohayakawa, Yoshiharu ^{[3
]}

Montgomery, Richard ^{[4
]}

Parczyk, Olaf ^{[5
]}

Person, Yury ^{[5
]}

机构：

[1] London Sch Econ, Dept Math, Houghton St, London WC2A 2AE, England

[2] Univ Rhode Isl, Dept Math, Kingston, RI 02881 USA

[3] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo, Brazil

[4] Univ Birmingham, Sch Math, Birmingham, W Midlands, England

[5] Tech Univ Ilmenau, Inst Math, Ilmenau, Germany

来源：

RANDOM STRUCTURES & ALGORITHMS | 2019年 / 55卷 / 04期

基金：

英国工程与自然科学研究理事会;

关键词：

perturbed graphs; random graphs; spanning trees; universality;

D O I：

10.1002/rsa.20850

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 graph G(alpha) on n vertices with delta(G(alpha)) >= alpha n for alpha > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph G(alpha)?G(n,C/n) contains copies of all spanning trees with maximum degree at most Delta simultaneously, where C depends only on alpha and Delta.

引用

页码：854 / 864

页数：11

共 24 条

[1]

Allen P., 2016, ARXIV161200622

[2] Embedding nearly-spanning bounded degree trees [J].

Alon, Noga ;

Krivelevich, Michael ;

Sudakov, Benny .

COMBINATORICA, 2007, 27 (06) :629-644

[3] Tilings in Randomly Perturbed Dense Graphs [J].

Balogh, Jozsef ;

Treglown, Andrew ;

Wagner, Adam Zsolt .

COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (02) :159-176

[4]

Balogh J, 2010, ELECTRON J COMB, V17

[5] Powers of tight Hamilton cycles in randomly perturbed hypergraphs [J].

Bedenknecht, Wiebke ;

Han, Jie ;

Kohayakawa, Yoshiharu ;

Mota, Guilherme O. .

RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) :795-807

[6]

Bennett P., 2017, ARXIV171002716

[7] How many random edges make a dense graph hamiltonian? [J].

Bohman, T ;

Frieze, A ;

Martin, R .

RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (01) :33-42

[8] THRESHOLD FUNCTIONS [J].

BOLLOBAS, B ;

THOMASON, A .

COMBINATORICA, 1987, 7 (01) :35-38

[9]

Bottcher J., 2018, ARXIV180204603

[10]

Dirac G. A., 1952, Proc. London Math. Soc, V3, P69, DOI DOI 10.1112/PLMS/S3-2.1.69

← 1 2 3 →