Rainbow saturation and graph capacities

Abstract

The $t$-colored rainbow saturation number $rsa{t}_t(n,F)$ is the minimum size of a $t$-edge-colored graph on $n$ vertices that contains no rainbow copy of $F$, but the addition of any missing edge in any color creates such a rainbow copy. Barrus, Ferrara, Vandenbussche and Wenger conjectured that $rsa{t}_t(n,K_s)=\Theta (n\log n)$ for every $s\ge 3$ and $t\ge \left(\genfrac{}{}{0ex}{}{s}{2}\right)$. In this short note we prove the conjecture in a strong sense, asymptotically determining the rainbow saturation number for triangles. Our lower bound is probabilistic in spirit, the upper bound is based on the Shannon capacity of a certain family of cliques.

arXiv comment5 pages, minor changes