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<k$ 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?
4
-
$\begingroup$ 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$. $\endgroup$– cadukCommented Mar 4 at 8:15
-
$\begingroup$ 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$? $\endgroup$– ImmanuelCommented Mar 4 at 8:41
-
1$\begingroup$ 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. $\endgroup$– cadukCommented Mar 4 at 8:56
-
$\begingroup$ Thanks for your input! $\endgroup$– ImmanuelCommented Mar 4 at 9:12
Add a comment
|