Generalized Ramsey numbers at the linear and quadratic thresholds

Abstract

The generalized Ramsey number $f(n,p,q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that every $p$-clique spans at least $q$ colors. Erdős and Gyárfás showed that $f(n,p,q)$ grows linearly in $n$ when $p$ is fixed and $q=q_{\text{lin}}(p):=\left(\genfrac{}{}{0ex}{}{p}{2}\right)-p+3$. Similarly they showed that $f(n,p,q)$ is quadratic in $n$ when $p$ is fixed and $q=q_{\text{quad}}(p):=\left(\genfrac{}{}{0ex}{}{p}{2}\right)-\frac{p}{2}+2$. In this note we improve on the known estimates for $f(n,p,q_{\text{lin}})$ and $f(n,p,q_{\text{quad}})$. Our proofs involve establishing a significant strengthening of a previously known connection between $f(n,p,q)$ and another extremal problem first studied by Brown, Erdős and Sós, as well as building on some recent progress on this extremal problem by Delcourt and Postle and by Shangguan. Also, our upper bound on $f(n,p,q_{\text{lin}})$ follows from an application of the recent forbidden submatchings method of Delcourt and Postle.

14 pages