Rainbow Stackings of Random Edge-Colorings

Abstract

A rainbow stacking of $r$-edge-colorings $\ddot{I}{‡}_1,\dots ,\ddot{I}{‡}_m$ of the complete graph on $n$ vertices is a way of superimposing $\ddot{I}{‡}_1,\dots ,\ddot{I}{‡}_m$ so that no edges of the same color are superimposed on each other. We determine a sharp threshold for $r$ (as a function of $m$ and $n$) governing the existence and nonexistence of rainbow stackings of random $r$-edge-colorings $\ddot{I}{‡}_1,\dots ,\ddot{I}{‡}_m$.

12 pages, 2 figures