In terms of $n\geq 1$, find the maximum possible number of edges in a subgraph $H$ of $K_{10}(n)$, the complete $10$-partite graph with $n$ vertices in each class, containing no copy of $K_4$.

It is suggested to apply Turan's theorem. For $n=1$ Turan gives $33$ (which is attainable, as $K_{10}(1) = K_{10}$ gives on restrictions on the edges of $H$). In general, Turan gives the bound $\lfloor \frac{100n^2}{3} \rfloor$ but is this always attainable, i.e. can we find $T_3(10n)$ in $K_{10}(n)$? I am not even sure this is always possible.

  • $\begingroup$ Yes, in order to find in $K_{10}(n)$ Turán’s graph with $10n$ vertices and $3$ partite sets when $n$ is not divisible by $3$ we have to split one of partite set of $K_{10}(n)$ to different partite set of Turán’s graph, but then vertices from different parts of the split set cannot be adjacent to each other. $\endgroup$ – Alex Ravsky Apr 26 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.