Embedding bounded degree spanning trees in random graphs

By Richard Montgomery. 2014

49 citations recorded by the source corpus.

We prove that if a tree $T$ has $n$ vertices and maximum degree at most $\Delta$, then a copy of $T$ can almost surely be found in the random graph $\mathcal{G}(n,\Delta\log^5 n/n)$.

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

View Paper: https://www.semanticscholar.org/paper/7cefa113fe9ed41495c30c0b34a33e49e05f546f