A rainbow connectivity threshold for random graph families

Abstract

Given a family $\mathcal{G}$ of graphs on a common vertex set $X$, we say that $\mathcal{G}$ is rainbow connected if for every vertex pair $u,v\in X$, there exists a path from $u$ to $v$ that uses at most one edge from each graph in $\mathcal{G}$. We consider the case that $\mathcal{G}$ contains $s$ graphs, each sampled randomly from $G(n,p)$, with $n=|X|$ and $p=\frac{c\log n}{sn}$, where $c>1$ is a constant. We show that when $s$ is sufficiently large, $\mathcal{G}$ is a.a.s. rainbow connected, and when $s$ is sufficiently small, $\mathcal{G}$ is a.a.s. not rainbow connected. We also calculate a threshold of $s$ for the rainbow connectivity of $\mathcal{G}$, and we show that this threshold is concentrated on at most three values, which are larger than the diameter of the union of $\mathcal{G}$ by about $\frac{\log n}{(\log \log n{)}^2}$. The same results also hold in a more traditional random rainbow setting, where we take a random graph $G\in G(n,p)$ with $p=\frac{c\log n}{n}$ ($c>1$) and color each edge of $G$ with a color chosen uniformly at random from the set $[s]$ of $s$ colors.

15 pages