A Spectral Erdős–Stone–Bollobás Theorem

Source abstract

Let r ≥ 3 and ( c / r r ) r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ( G ) satisfies then G contains a complete r -partite subgraph with r − 1 parts of size ⌊( c / r r ) r log n ⌋ and one part of size greater than n 1− c r −1 . This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F 1 , F 2 , . . . are r -chromatic graphs satisfying v ( F n ) = o (log n ), then