Bollobás–Nikiforov conjecture holds asymptotically almost surely

Abstract

Bollobás and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured that for a graph G that is not complete, with e ( G ) edges and the clique number ω ( G ) , then λ 1 2 + λ 2 2 ≤ 2 e ( G ) 1 − 1 ω ( G ) , where λ 1 and λ 2 are the largest and the second largest eigenvalues of the adjacency matrix of G , respectively. In this paper, we prove that for a sequence of random graphs the conjecture holds true with probability tending to one as the number of vertices tends to infinity.