Spanning trees in random graphs

By Richard Montgomery. Advances in Mathematics, 2018

126 citations recorded by the source corpus.

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

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/9666b621bbe294e43a06aac842e072e2aa56fdfc