David Conlon: The Erdős-Gyárfás problem on generalized Ramsey numbers

Fix positive integers p and q with 2 ≤ q ≤ {p \choose 2}. An edge-coloring of the complete graph K_n is said to be a (p, q)-coloring if every K_p receives at least q different colors. The function f(n, p, q) is the minimum number of colors that are needed for K_n to have a (p,q)-coloring. This function was introduced by Erdős and Shelah about 40 years ago, but Erdős and Gyárfás were the first to study the function in a systematic way. They proved that f(n, p, p) is polynomial in n and asked to determine the maximum q, depending on p, for which f(n,p,q) is subpolynomial in n. We prove that the answer is p-1.

Joint work with Jacob Fox, Choongbum Lee and Benny Sudakov.