기초과학연구원 이산수학그룹
On August 2, 2023, Daniel Kráľ from Masaryk University gave a talk on constructing common graphs with large chromatic numbers at the Discrete Math Seminar. The title of his talk was “High chromatic common graphs.”
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. As probabilistic constructions often provide good bounds on quantities in extremal combinatorics, we say that a graph H is common if the random 2-edge-coloring asymptotically minimizes the number of monochromatic copies of H. This notion goes back to the work of Erdős in the 1960s, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s, however, a classification of common graphs remains one of the most intriguing problems in extremal combinatorics.
Sidorenko’s Conjecture (if true) would imply that every bipartite graph is common, and in fact, no bipartite common graph unsettled for Sidorenko’s Conjecture is known. Until Hatami et al. showed that a 5-wheel is common about a decade ago, all graphs known to be common had chromatic number at most three. The existence of a common graph with chromatic number five or more has remained open for three decades.
We will present a construction of (connected) common graphs with arbitrarily large chromatic number. At the end of the talk, we will also briefly discuss the extension of the notion to more colors and particularly its relation to Sidorenko’s Conjecture.
The main result presented in the talk is based on joint work with Jan Volec and Fan Wei.