Ehud Friedgut
(Hebrew University)
What Makes a Graph Ramsey?
(plus a detour to hypergraph regularity)
Abstract: Let us call a graph "Ramsey" if every red/blue coloring of its edges induces a monochromatic triangle. Which graphs have this property? We will show that in a well defined sense for most graphs the answer to this question depends only on the ratio between the number of triangles in the graph and the number of edges. A key ingredient in the proof is a generalization of the celebrated Szemeredi Regularity Lemma to the setting of hypergraphs. No prior knowledge of these themes will be assumed.