Common graphs with arbitrary chromatic number

Ramsey’s theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. In 1962, Erdős conjectured that the random 2-edge-coloring minimizes the number of monochromatic copies of Kk, and the conjecture was extended by Burr and Rosta to all graphs. In the late 1980s, the conjectures were disproved by Thomason and Sidorenko, respectively. A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. If Sidorenko’s conjecture, one of the most significant open problems in extremal graph theory, is true, then every 2-chromatic graph is common and, in fact, no 2-chromatic common graph unsettled for Sidorenko’s conjecture is known. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012, and no common graph with a larger chromatic number is known.

Duke Scholars

Author Fan Wei Mathematics