Multitrees in random graphs

Abstract

Let $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $s\ge 2$. Let $e_{i,j},i=1,2,\dots ,N,j=1,2,\dots ,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A {\em MultiTree} is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,\dots ,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\ge 3$.