Daniel Kráľ, 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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.