PIMS-UVic Discrete Math Seminar: Emily Heath

Given graphs $G$ and $H$ and a positive integer $q$, an $(H,q)$-coloring of $G$ is an edge-coloring in which each copy of $H$ receives at least $q$ colors. Erdős and Shelah raised the question of determining the minimum number of colors, $f(G,H,q)$, which are required for an $(H,q)$-coloring of $G$. Determining $f(K_n,K_p,2)$ for all $n$ and $p$ is equivalent to determining the classical multicolor Ramsey numbers. Recently, Mubayi and Joos introduced the use of a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the values of $f(K_{n,n},C_4,3)$ and $f(K_n,K_4,5)$. In this talk, we will show how to generalize their approach to give bounds on the generalized Ramsey numbers for several families of graphs. This is joint work with Deepak Bal, Patrick Bennett, and Shira Zerbib.