A fixed positive excess over the Turan theorem threshold forces logarithmic balanced complete multipartite graphs. There is an elementary induction using common neighbourhood from bipartite density: first obtain a logarithmic -partite subgraph from the induction hypothesis, and select disjoint transversal -cliques in it. Each such clique has at least common neighbours, by the union bound on non-neighbour sets. Apply the bipartite common-neighbour count to these cliques as left-side objects. Their selected union and a large common neighbourhood form the extra part.

Articles by others on the same topic (NaN)

There are currently no matching articles.