Random trees in random graphs

Abstract:

We show that a random labeled $n$-vertex graph almost surely contains isomorphic copies of almost all labeled $n$-vertex trees, in two senses. In the first sense, the probability of each edge occurring in the graph diminishes as $n$ increases, and the set of trees referred to as "almost all" depends on the random graph. In the other sense, the probability of an edge occurring is fixed, and the relevant set of trees is predetermined. The same method applies to show that almost all labeled $n$-tournaments contain isomorphic copies of almost all labeled oriented $n$-trees.