Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2015 | public
Journal Article Open

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.

Additional Information

© 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.

Attached Files

Submitted - 1403.0250.pdf


Files (238.0 kB)
Name Size Download all
238.0 kB Preview Download

Additional details

August 20, 2023
August 20, 2023