The Erdős–Gyárfás problem on generalized Ramsey numbers

By David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov. 2014

56 citations recorded by the source corpus.

Fix positive integers p and q with 2⩽q⩽(p2) . An edge coloring of the complete graph Kn is said to be a (p,q) ‐coloring if every Kp receives at least q different colors. The function f(n,p,q) is the minimum number of colors that are needed for Kn 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 .

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6204053dab7d0ab74a320f4664d5b3c38804aa7a