2018. 04. 05. 12:15 - 2018. 04. 05. 13:45
MTA Rényi Intézet, nagyterem
-
-
-
-
Event type:
seminar
Intézeti:
Intézeti
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.