Tree Universality in Random Graphs

Recently, Krivelevich showed that if T is a n-vertex tree with bounded maximum degree, then G a.a.s. contains T if pn is at least of order n^eps where eps is an arbitrary positive constant. However, this does not imply that G a.a.s. contains all such trees simultaneously, i.e., that G is universal for all n-vertex trees with bounded maximum degree. We study the question for which values of pn such a universality occurs.

To this end, we investigate sparse n-vertex graphs that satisfy certain natural expansion properties. We show that a graph with these properties does indeed contain every n-vertex tree with bounded maximum degree. We then see that a random graph drawn according to the G(n;p) model with pn at least of order n^(2/3) log^2 n a.a.s. has the desired expansion properties and is therefore universal for the class of n-vertex trees with bounded maximum degree.

Joint work with Michael Krivelevich and Wojciech Samotij.