A Ramsey‐type problem and the Turán numbers*

For each n and k , we examine bounds on the largest number m so that for any k ‐coloring of the edges of K n there exists a copy of K m whose edges receive at most k− 1 colors. We show that for k ≥ √n\;+\,Ω(n1/3) , the largest value of m is asymptotically equal to the Turá number t(n, n 2/k) , while for any constant ε > 0,\; if\; k ≤ (1-ε) √n then the largest m is asymptotically larger than that Turá number.