Let $N=\binom{n}{2}$ and $s\geq 2$. Let $e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A MultiTree is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,\ldots,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\geq 3$.
@article{10_37236_10804,
author = {Alan Frieze and Wesley Pegden},
title = {Multitrees in random graphs},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {1},
doi = {10.37236/10804},
zbl = {1508.05145},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10804/}
}
TY - JOUR
AU - Alan Frieze
AU - Wesley Pegden
TI - Multitrees in random graphs
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10804/
DO - 10.37236/10804
ID - 10_37236_10804
ER -
%0 Journal Article
%A Alan Frieze
%A Wesley Pegden
%T Multitrees in random graphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10804/
%R 10.37236/10804
%F 10_37236_10804
Alan Frieze; Wesley Pegden. Multitrees in random graphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10804
