A variant of the classical Ramsey problem

For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK_pK are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK_p subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK_n. We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erds and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414.