Dear all,
This week's speaker is Jan Volec (ČVUT). Please find the talk details below.
Best regards, Misha Tyomkyn.
-----------------------------------------------------------------------------------------------
Existence of common graphs with large chromatic number Jan Volec Czech Technical University in Prague April 21, 2022, 12:20 in S6
Abstract Ramsey's Theorem states that for every graph H, there is an integer R(H) such that every 2-edge-coloring of R(H)-vertex complete graph contains a monochromatic copy of H. In this talk, we focus on a natural quantitative extension: how many monochromatic copies of H can we find in every 2-edge-coloring of K_N, and, what graphs H are so-called common, i.e., the number of monochromatic copies of H is asymptotically minimized by a random 2-edge-coloring.
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 the 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 and F. Wei
------------------------------------------------------------------------------------------------ _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz