A variant of the classical Ramsey problem (Q1280270)

The following quantity is estimated. Let \(f(n,p,q)\) be the minimum number of colors needed to color all edges of \(K_n\) such that every \(K_p\) gets at least \(q\) colors. A general upper bound is given using the Lovász local lemma. If \(q={p\choose 2}-p+3\) then \(f(n,p,q)\) is linear while \(f(n,p,q-1)\) is sublinear. If \(q={p\choose 2}-\lfloor{p\over 2}\rfloor+2\) then \(f(n,p,q)=\Omega(n^2)\) while \(f(n,p,q-1)=O(n^{2-{4\over p}})\) but is \(\Omega(n^{{4\over 3}})\) for \(p\geq 7\). \(f(n,p,p)=\Omega(n^{{1\over{p-2}}})\). Also, \({5\over 6}(n-1)\leq f(n,4,5)\) and \(f(n,9,34)={n\choose 2}-o(n^2)\).