Nearly optimal packings of equally sized rainbow forests

Source abstract

A forest in an edge-colored graph is rainbow if its edges have pairwise distinct colors. We prove that, for every fixed $0<δ<1$, every properly edge-colored simple graph with $km$ edges and color classes of size at most $m$ contains at least $(1-o(1))m$ pairwise edge-disjoint rainbow forests, each with exactly $k$ edges, uniformly for $1\leq k\leq(2-δ)m$ as $m\to\infty$. This establishes the packing conclusion in the $k$-edge formulation of a conjecture of Montgomery, Pokrovskiy, and Sudakov throughout this range, with the original global color bound. The number of forests is asymptotically optimal, and the leading constant $2$ in the range of $k$ is best possible. The proof combines random star forests with a matching theorem for bipartite hypergraphs.