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