Packing arborescences in random digraphs

Abstract

We study the problem of packing arborescences in the random digraph $\mathcal{D}(n,p)$, where each possible arc is included uniformly at random with probability $p=p(n)$. Let $\lambda (\mathcal{D}(n,p))$ denote the largest integer $\lambda \ge 0$ such that, for all $0\le \ell \le \lambda$, we have ${\sum }_{i=0}^{\ell -1}(\ell -i)|\{v:d^{in}(v)=i\}|\le \ell$. We show that the maximum number of arc-disjoint arborescences in $\mathcal{D}(n,p)$ is $\lambda (\mathcal{D}(n,p))$ a.a.s. We also give tight estimates for $\lambda (\mathcal{D}(n,p))$ depending on the range of $p$.

17 pages