The maximal number of induced \(r\)-partite subgraphs (Q1805369): Difference between revisions

Let \(K_ r(t)\) denote the complete \(r\)-partite graph with \(t\) vertices in each class and let \(T_ r(n)\) denote the \(r\)-partite Turán graph with \(n\) vertices. The authors show, among other things, that if \(t> 1+\log r\) then the graph \(T_ r(n)\) is the graph with \(n\) vertices that contains the largest number of induced subgraphs isomorphic to \(K_ r(t)\); moreover, the bound on \(t\) is essentially best possible.