Existence of common graphs with large chromatic number

Jan Volec, 4 Oct 2021

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 KN 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 KN 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