-
MTA Rényi Intézet, nagyterem
-
-
-
-
-
-

Description

The $t$-colored rainbow saturation number $\rsat_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 $\rsat_t(n,K_s) = \Theta(n\log n)$ for
every $s\ge 3$ and $t\ge \binom{s}{2}$.
In this talk I will explain how this problem is related to the Shannon capacity of a certain family of cliques,
and use this connection to prove the conjecture in a strong sense, asymptotically determining the rainbow
saturation number for triangles.