기초과학연구원 이산수학그룹
On December 19, 2023, Shengtong Zhang (张盛桐) from Stanford University gave a talk at the Discrete Math Seminar on the minimum number of triangles in a $K_t$-Ramsey graph. The title of his talk was “Triangle Ramsey numbers of complete graphs“.
A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}3\] for all sufficiently large $t$. Our proof involves a combination of results on the chromatic number of triangle-sparse graphs.
Joint work with Jacob Fox and Jonathan Tidor.