Spanning Trees in Random Graphs

21 October 2014
Richard Montgomery
Given a tree $T$ with $n$ vertices, how large does $p$ need to be for it to be likely that a copy of $T$ appears in the binomial random graph $G(n,p)$? I will discuss this question, including recent work confirming a conjecture which gives a good answer to this question for trees with bounded maximum degree.
  • Combinatorial Theory Seminar