Jonathan Tidor, Princeton University

Abstract

A graph G is called H-Ramsey if every 2-coloring of the edges of G contains a monochromatic copy of H. In general, Ramsey theory studies minimal H-Ramsey graphs: the classical Ramsey number, r(H), can be defined to be the minimum number of vertices in an H-Ramsey graph. The size Ramsey number, introduced by Erdős, Faudree, Rousseau, and Schelp, is defined to be the minimum number of edges in an H-Ramsey graph. We study a generalization of these two notions, the triangle-Ramsey number, defined to be the minimum number of triangles in an H-Ramsey graph. Answering a question of Spiro, we prove that for t sufficiently large, the triangle-Ramsey number of K_t is equal to its Ramsey number choose 3. This generalizes a classical result of Chvátal on the size-Ramsey number of K_t. Our proof uses a number of techniques from probabilistic coloring of graphs.

Based on joint work with Jacob Fox and Shengtong Zhang.