# Turan-like bound for $k$-partite graphs

This is a question I've implicitly asked on AoPS five years ago, and has not been answered. I apologize for its possible simplicity, as I am not a graph theorist.

Let $$n$$ and $$k$$ be two positive integers. Let $$G$$ be a graph with vertex set $$V$$. Assume that $$V$$ is partitioned into $$k$$ disjoint subsets $$V_1, V_2, \ldots, V_k$$, each of which has exactly $$n$$ elements (so that $$\left|V\right| = nk$$). Assume that for each $$i \in \left\{1, 2, \ldots, k\right\}$$, the set $$V_i$$ is an independent set of $$G$$ (that is, no two vertices of $$V_i$$ are connected by an edge). Assume also that each vertex of $$G$$ has degree $$\geq \left(k-2\right)n+1$$.

Prove or disprove that $$G$$ has a $$k$$-clique (that is, $$k$$ distinct vertices pairwise connected by edges).

This is a triviality when $$k = 1$$ or $$k = 2$$, and a known contest problem in the case when $$k = 3$$ (see http://artofproblemsolving.com/community/c6h40982 , and http://artofproblemsolving.com/community/c6h49347 for an extension which is not completely true as stated). In my AoPS thread linked above, I have asked whether the $$k = 4$$ case is true, but of course the real question is the general case.

It is not true in general that $G$ under your conditions contains a $k$-clique. For example, if $k = 4$ consider the following construction by Gouping Jin (see the proof of Theorem 3.1 in ):
Let $V_i = A_i \cup B_i$ for $i \in \{1,2,3,4\}$, where $\left|A_i\right| = \lfloor n/3 \rfloor$ and $\left|B_i\right| = n - \lfloor n/3 \rfloor$. Join vertices so that the following pairs of sets induce complete bipartite subgraphs: $(A_1,V_2 \cup B_3 \cup B_4)$, $(A_2,V_1\cup B_3 \cup B_4)$, $(A_3,V_4\cup B_1 \cup B_2)$, $(A_4,V_3 \cup B_1 \cup B_2)$ and $(B_1 \cup B_2, B_3 \cup B_4)$ (i.e. join every vertex of $A_1$ with every vertex of $V_2 \cup B_3 \cup B_4$, and so on). The resulting graph, $H_n$, is clearly $4$-partite and it is not difficult to see that it has minimum degree $\delta(H_n) = \lfloor (2 + 1/3)n \rfloor$. Furthermore, $H_n$ contains no $4$-clique. Now, since $\lfloor (2 + 1/3)n \rfloor \geq (4-2)n + 1$ for $n \geq 3$ this gives us examples of graphs that satisfy your conditions but do not contain a $4$-clique.
In fact, Jin shows in  that the best lower bound (to guarantee a $k$-clique) on the degrees of a $k$-partite graph with each part of size $n$ is $\lfloor (2 + 1/3)n \rfloor + 1$ for $k = 4$, $\lfloor (3 + 1/3)n \rfloor + 1$ for $k = 5$ and $\leq \left(k - 1 - \frac{1}{1 + 1/2 + 1/3 + \dots + \frac{1}{k-2}} \right)n + 1$ for all $k \geq 4$.
 G. Jin, "Complete Subgraphs of $r$-partite Graphs", Combinatorics, Probability and Computing 1, (1992), 241-250.
• Very nice counterexample; thanks a lot! Actually, if we take $n = 3$, then we get a counterexample where the degree of each vertex is exactly $\left(k-2\right)n+1$. – darij grinberg Aug 10 '16 at 14:17
• Thanks for the reference, too! Nitpick: the generalized bound holds for all $k \geq 3$, not only for $k \geq 4$ :) – darij grinberg Aug 10 '16 at 14:18
• It might be easier to say which edges are not present: $(B_1,B_2), (B_3,B_4), (A_1\cup A_2, A_3\cup A_4)$. – Jan Kyncl Aug 11 '16 at 10:14