# Bound on the number of monochromatic $K_i$ in a $K_k$ free colored graph

I have a question that I need help with. Suppose you have some integers $$k,q$$ and $$N$$ and a fixed q-coloring on the edges of $$K_N$$ such that it contains no monochromatic $$K_k$$. Is there a nice way to bound the number of possible monochromatic $$K_i$$ for $$i and a fixed color? So for $$i=2$$ we know every two vertices form a monochromatic K_2 so that's pretty useless. But what about $$K_{k-1}$$ for example? Intuitively it seems like there can't be a lot of them in the same color. I tried to find a bound using an induction argument but I'm stuck & a quick internet search didn't help. Maybe someone knows an answer to this?

• What kind of bounds do you expect? If you want a bound in terms of $k, q, N$ and $i$, this will be probably be attained by a monochromatic balanced complete $K_{k-1}$-partite graph (with the other edges of a second color) since this is the biggest $K_k$-free graph and the one containing the most $K_i$ cliques for $i<k$. Commented Mar 4 at 8:15
• Thanks for answering. Yes I'm looking for any bound in terms of $k,q,N$and $i$. How does your suggestion then depend on $N$ or $q$? Commented Mar 4 at 8:41
• If my guess is correct, assuming $K> \frac{N}{2}$ and $i\geq \frac{N}{k}$, the upper bound would be asymptotically $\binom{k-1}{i}(\frac{N}{k})^i$. The bound does not depend on $q$ because we will have the most cliques for $q=2$. If $k$ is small, my construction will not be optimal, the problem is more complicated than what I thought. My best guess would be to define recursively maximum complete $K_{k−1}$-partite graph on the remaining uncolored cliques, but I'm less confident and this one, and this will work if $q$ is sufficiently large. Commented Mar 4 at 8:56
• Thanks for your input! Commented Mar 4 at 9:12