Conflict-free hypergraph matchings and generalized Ramsey numbers (Emily Heath, Iowa State University)

Graph Theory Seminar
Tuesday, April 16, 2024 - 3:30pm for 1 hour (actually 50 minutes)
Skiles 006
Emily Heath – Iowa State University – eheath@iastate.edu
Evelyne Smith-Roberge

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.