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

Abstract

Fix positive integers $p$ and $q$ with $2\le q\le \left(\genfrac{}{}{0ex}{}{p}{2}\right)$. 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$.

22 pages