Published January 2015
| Version Submitted
Journal Article
Open
The Erdős-Gyárfás problem on generalized Ramsey numbers
Abstract
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
1403.0250.pdf
Additional details
Identifiers
- Eprint ID
- 97832
- Resolver ID
- CaltechAUTHORS:20190812-162959803
Related works
- Describes
- https://arxiv.org/abs/1403.0250 (URL)
Funding
- Royal Society
- David and Lucile Packard Foundation
- Simons Foundation
- NSF
- DMS-1069197
- Alfred P. Sloan Foundation
- MIT NEC Corporation
- Swiss National Science Foundation (SNSF)
- 200021-149111
- Binational Science Foundation (USA-Israel)
Dates
- Created
-
2019-08-15Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department