Common Graphs with Arbitrary Chromatic Number

          @misc{ scivideos_22594,
            doi = {},
            url = {https://old.simons.berkeley.edu/node/22594},
            author = {},
            keywords = {},
            language = {en},
            title = {Common Graphs with Arbitrary Chromatic Number},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {sep},
            note = {22594 see, \url{https://scivideos.org/simons-institute/22594}}
          }
          

Abstract

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 the 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 2012, 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