The Erdős-Gyárfás problem on generalized Ramsey numbers
Fix positive integers p and q with [equation; see abstract in PDF for details]. 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 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.
© 2014 London Mathematical Society. Received 2 March 2014; revised 28 April 2014; published online 16 October 2014. David Conlon was supported by a Royal Society University Research Fellowship. Jacob Fox was supported by a Packard Fellowship, by a Simons Fellowship, by NSF grant DMS‐1069197, by an Alfred P. Sloan Fellowship and by an MIT NEC Corporation Award. Benny Sudakov was supported in part by SNSF grant 200021‐149111 and by a USA‐Israel BSF grant. We thank the anonymous referee for a number of helpful comments on the manuscript.
Submitted - 1403.0250.pdf