A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

Abstract

The Erdős-Gyárfás number $f(n,p,q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that all of its $p$-clique spans at least $q$ colors. In this paper we improve the best known upper bound on $f(n,p,q)$ for many fixed values of $p,q$ and large $n$. Our proof uses a randomized coloring process, which we analyze using the so-called differential equation method to establish dynamic concentration.