Spanning trees in random graphs

Richard Montgomery

doi:10.1016/j.aim.2019.106793

Spanning trees in random graphs

Richard Montgomery

Mathematics

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

100 Downloads (Pure)

Abstract

For each Δ>0, we prove that there exists some C=C(Δ) for which the binomial random graph G(n,Clog⁡n/n) almost surely contains a copy of every tree with n vertices and maximum degree at most Δ. In doing so, we confirm a conjecture by Kahn.

Original language	English
Article number	106793
Journal	Advances in Mathematics
Volume	356
DOIs	https://doi.org/10.1016/j.aim.2019.106793
Publication status	Published - 2 Sept 2019

Bibliographical note

Arxiv updated within a week of acceptence.

Keywords

Random graphs
Spanning trees
Thresholds
Universality

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1016/j.aim.2019.106793Licence: None: All rights reserved

Montgomery_Spanning_trees_in_random_graphs_Advances_in_Mathematics_2019Accepted author manuscript, 1.06 MBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://www.sciencedirect.com/science/article/pii/S0001870819304116Licence: None: All rights reserved

Cite this

@article{ba4b1a8409fe4c33bd14466c2b87a371,

title = "Spanning trees in random graphs",

abstract = "For each Δ>0, we prove that there exists some C=C(Δ) for which the binomial random graph G(n,Clog⁡n/n) almost surely contains a copy of every tree with n vertices and maximum degree at most Δ. In doing so, we confirm a conjecture by Kahn.",

keywords = "Random graphs, Spanning trees, Thresholds, Universality",

author = "Richard Montgomery",

note = "Arxiv updated within a week of acceptence.",

year = "2019",

month = sep,

day = "2",

doi = "10.1016/j.aim.2019.106793",

language = "English",

volume = "356",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Elsevier",

}

TY - JOUR

T1 - Spanning trees in random graphs

AU - Montgomery, Richard

N1 - Arxiv updated within a week of acceptence.

PY - 2019/9/2

Y1 - 2019/9/2

N2 - For each Δ>0, we prove that there exists some C=C(Δ) for which the binomial random graph G(n,Clog⁡n/n) almost surely contains a copy of every tree with n vertices and maximum degree at most Δ. In doing so, we confirm a conjecture by Kahn.

AB - For each Δ>0, we prove that there exists some C=C(Δ) for which the binomial random graph G(n,Clog⁡n/n) almost surely contains a copy of every tree with n vertices and maximum degree at most Δ. In doing so, we confirm a conjecture by Kahn.

KW - Random graphs

KW - Spanning trees

KW - Thresholds

KW - Universality

UR - https://arxiv.org/abs/1810.03299

U2 - 10.1016/j.aim.2019.106793

DO - 10.1016/j.aim.2019.106793

M3 - Article

SN - 0001-8708

VL - 356

JO - Advances in Mathematics

JF - Advances in Mathematics

M1 - 106793

ER -

Spanning trees in random graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this