On edge colorings with at least \(q\) colors in every subset of \(p\) vertices (Q1594601)

For fixed integers \(p\) and \(q\), an edge coloring of \(K_{n}\) is called a \((p,q)\)-coloring if the edges of \(K_{n}\) in every subset of \(p\) vertices are colored with at least \(q\) distinct colors. Let \(f(n,p,q)\) be the smallest number of colors needed for a \((p,q)\)-coloring of \(K_{n}\). \textit{P. Erdős} and \textit{A. Gyárfás} [Combinatorica 17, No. 4, 459-467 (1997; Zbl 0910.05034)] studied this function if \(p\) and \(q\) are fixed and \(n\) tends to infinity. They determined for every \(p\) the smallest \(q\) \((=p(p-1)/2-p+3)\) for which \(f(n,p,q)\) is linear in \(n\) and the smallest \(q\) for which \(f(n,p,q)\) is quadratic in \(n\). They raised the question whether this is the only \(q\) value which results in a linear \(f(n,p,q)\). In this paper the behavior of \(f(n,p,q)\) between the linear and the quadratic order of magnitude is studied. In particular it is shown that we can have at most \(\log p\) values of \(q\) which give a linear \(f(n,p,q)\), where \(\log p\) denotes the base 2 logarithm.