Small topological complete subgraphs of ``dense'' graphs (Q1101464): Difference between revisions

The authors show that, for each \(t\in N\) and \(\epsilon >0\), every graph of n vertices and \(4^{t^ 2}n^{1+\epsilon}\) edges contains a subgraph of at most \(7t^ 2\log t/\epsilon\) vertices which is homeomorphic to the complete graph of t vertices.