Multitrees in random graphs (Q2684902)

Let \(N=\binom{n}{2}\) and \(s\geq 2\) be a positive integer. Let \(e_{i,j}\) for \(1\leq i\leq N\) and \(1\leq j\leq s\) be \(s\) independent random permutations of the \(N\) edges of a complete graph on \(n\) vertices. We say that \(I\subseteq [N]=\{1,2,\ldots ,N\}\) is a multitree if for each \(1\leq j\leq s\) the edges \(E_{I,j}=\{e_{i,j}: i\in I\}\) induce spanning trees of \(K_{n}\). Our interest is in the smallest \(m=m(n)\) for which there is a multitree with high probability (w.h.p., i.e. with probability tending to 1 with \(n\)). Let \(m^\ast\) denote the hitting time for having a multitree. The main result of the paper under review is that \(m^\ast=O(n\log(n))\) where the implied constant depends on \(s\). The second main result is for the case \(s=2\) when a matroid result of \textit{J. Edmonds} [in: Combinatorial structures and their applications. Proceedings of the Calgary international conference on combinatorial structures and their applications held at the University of Calgary, Calgary, Alberta, Canada, June, 1969. New York-London-Paris: Gordon and Breach, Science Publishers. 69--87 (1970; Zbl 0268.05019)] allows a more precise result that the first theorem mentioned above. The authors also discuss some variants, for example showing that if \(m\geq Kn\log(n)\) for some absolute constant \(K\), then \([m]\) w.h.p. contains a MultiPerfectMatching, that is \(I\subseteq [m]\) with \(\vert I\vert=\lfloor n/2 \rfloor\) and each set \(E_{I,j}\) inducing a matching of the maximum possible size \(\lfloor n/2 \rfloor\). The authors also conjecture that there should be a constant \(K\) such that for \(m\geq Kn\log(n)\) there should be a multi-Hamilton cycle.