Ramsey Theory: A Rainbow Version of Ramsey Multiplicities

Seminar: 
Combinatorics Seminar
Event time: 
Thursday, February 1, 2018 - 4:00pm to 5:00pm
Speaker: 
Yunus Tuncbilek
Speaker affiliation: 
Yale University
Event description: 

For a graph G with m vertices, Mr(G,n) is the minimumnumber of monochromatic copies of G in any r-edge-coloring of Kn and is called \textitthe Ramsey multiplicity. A graph G with e edges is called \textitcommon if \displaystyle{\limn → ∞ \fracMr(G\;n){\binomnm(m!)/(|Aut(G)|)} = 21-e}, \textiti.e.\ the proportion of monochromatic copies of G in any coloring of a complete graph is asymptotically minimized by the random coloring. We introduce the \textitAnti-Ramsey Multiplicity rb(G,n,r), which is defined as the maximum number of \textitrainbow copies of agraph G in any r-edge-coloring of Kn. A graph is r-anti-common if \displaystyle{\limn → ∞ r/b(G,n,r){\binomnm(m!)/(|Aut(G)|)} = \frac{\binomree!}re}, \textiti.e. the proportion of rainbow copies of G is asymptotically maximized by the random coloring. A graph is anti-common if it is r-anti-common for any r greater than or equal to the graph's size. We show that matchings, stars and disjoint stars are anti-common. We also prove that for any c such that c+(1-c)\log(1-c) ≥ (2)/(m-1) + 1/12\binomm22, if e ≥ c\binomm2, then G is not \binomm2-anti-common. Using blowup constructions, we show that C4 is not 4-anti-common and C5 is not 5-anti-common.