Spanning trees in random graphs

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
67 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 languageEnglish
Article number106793
JournalAdvances in Mathematics
Volume356
DOIs
Publication statusPublished - 2 Sep 2019

Keywords

  • Random graphs
  • Spanning trees
  • Thresholds
  • Universality

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Spanning trees in random graphs'. Together they form a unique fingerprint.

Cite this