Existence of common graphs with large chromatic number

Ramsey’s Theorem states that for every graph $H$, there exists a number $R(H)$ such that if $N>R(H)$ then every 2-edge-coloring of $K_N$ contains a monochromatic copy of $H$. This talk focuses on the natural quantitative extension of this result: how many monochromatic copies of $H$ can we always find, and, what are the graphs $H$ for which the edge-coloring of $K_N$ asymptotically minimizing the number of monochromatic copies of $H$ is random-like? Such graphs $H$ are called common.

A classical result of Goodman from 1959 states that triangle is a common graph. On the other hand, Thomason proved in 1989 that no clique of order at least four is common, and existence of a common graph with chromatic number larger than three was open until about 10 years ago, when Hatami, Hladky, Kral, Norin and Razborov proved that the 5-wheel is common. In this talk, we show that for every $k>4$, there exists a common graph with chromatic number $k$.

This is a joint work with D. Kral, J. Noel, S. Norin, and F. Wei

Recording