  Given a class of graphs F, we say that a graph G is universal for F, or
F-universal, if every H in F is contained in G as a subgraph. The construction
of sparse universal graphs for various families F has received a considerable
amount of attention. One is particularly interested in tight F-universal
graphs, i.e., graphs whose number of vertices is equal to the largest number of
vertices in a graph from F. Arguably, the most studied case is that when F is
some class of trees.
  Given integers n and \Delta, we denote by T(n,\Delta) the class of all
n-vertex trees with maximum degree at most \Delta. In this work, we show that
every n-vertex graph satisfying certain natural expansion properties is
T(n,\Delta)-universal or, in other words, contains every spanning tree of
maximum degree at most \Delta. Our methods also apply to the case when \Delta
is some function of n. The result has a few very interesting implications. Most
importantly, we obtain that the random graph G(n,p) is asymptotically almost
surely (a.a.s.) universal for the class of all bounded degree spanning (i.e.,
n-vertex) trees provided that p \geq c n^{-1/3} \log^2n where c > 0 is a
constant. Moreover, a corresponding result holds for the random regular graph
of degree pn. In fact, we show that if \Delta satisfies \log n \leq \Delta \leq
n^{1/3}, then the random graph G(n,p) with p \geq c \Delta n^{-1/3} \log n and
the random r-regular n-vertex graph with r \geq c\Delta n^{2/3} \log n are
a.a.s. T(n,\Delta)-universal. Another interesting consequence is the existence
of locally sparse n-vertex T(n,\Delta)-universal graphs. For constant \Delta,
we show that one can (randomly) construct n-vertex T(n,\Delta)-universal graphs
with clique number at most five. Finally, we show robustness of random graphs
with respect to being universal for T(n,\Delta) in the context of the
Maker-Breaker tree-universality game.
