























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):=\binom p2-p+3$. Similarly they showed that $f(n, p, q)$ is quadratic in $n$ when $p$ is fixed and $q=q_{\text{quad}}(p):=\binom p2-\frac p2+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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。