Speaker: Emily Heath
Title: The Erdos-Gyarfas Problem on Generalized Ramsey Numbers
Abstract:
A (p,q)-coloring of a graph G is an edge-coloring of G in which each p-clique contains edges of at least q distinct colors. We are interested in the function f(n,p,q), first introduced by Erdos and Shelah, which is the minimum number of colors needed for a (p,q)-coloring of the complete graph K_n. In 1997, Erdos and Gyarfas initiated the systematic study of this function. Among other results, they gave upper and lower bounds on f(n,p,p), which are still the best known bounds for general p today. In this talk, I will give an overview of this problem and describe recent improvements on the probabilistic upper bound of Erdos and Gyarfas for several small cases of p.
This is joint work with Alex Cameron.