Multitrees in Random Graphs

Let N = ((n)(2)) and s >= 2. Let e(i),(j),(i) = 1, 2,..., N, j = 1, 2,..., s be s independent permutations of the edges E(K-n) of the complete graph K-n. A MultiTree is a set I subset of [N] such that the edge sets E-I,E-j induce spanning trees for j = 1, 2,..., s. In this paper we study the following question: what is the smallest m = m(n) such that w.h.p. [m] contains a MultiTree. We prove a hitting time result for s = 2 and an O(n log n) bound for s >= 3.