Reminder: this is today.
------------------------------------------------------------
On 2022-04-19 11:04, Mykhaylo Tyomkyn wrote:
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 _______________________________________________ TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz