Bounds for Rainbow-uncommon Graphs

Abstract

We say a graph $H$ is $r$-rainbow-uncommon if the maximum number of rainbow copies of $H$ under an $r$-coloring of $E(K_n)$ is asymptotically (as $n\to \infty$) greater than what is expected from uniformly random $r$-colorings. Via explicit constructions, we show that for $H\in \{K_3,K_4,K_5\}$, $H$ is $r$-rainbow-uncommon for all $r\ge \left(\genfrac{}{}{0ex}{}{|V(H)|}{2}\right)$. We also construct colorings to show that for $t\ge 6$, $K_t$ is $r$-rainbow-uncommon for sufficiently large $r$.

9 pages, 2 figures