Non-bipartite k-common graphs

Abstract: How many monochromatic copies of H must appear in a k-edge colouring of a large complete graph? The graph H is said to be "k-common" if the number of monochromatic H is asymptotically minimized by a random colouring. Recent progress on Sidorenko's Conjecture has provided many new examples of bipartite k-common graphs; however, it is not known if such graphs can have high chromatic number. We construct the first examples of non-bipartite k-common graphs for $k \ge 3$, addressing a problem raised by Jagger, Šťovíček and Thomason in 1996. This talk is based on joint work with Daniel Kráľ, Sergey Norin, Jan Volec and Fan Wei.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).