Spectral techniques applied to sparse random graphs

Abstract

We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ 1 ≥ … ≥ λn be the eigenvalues of an n‐vertex graph, and let λ = max[λ 2,|λn|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ 1 ≥ d, and we show that $\lambda = O(\sqrt{d})$. For d = c it is no longer true that $\lambda = O(\sqrt{d})$, but we show that by removing a small number of vertices of highest degree in G, one gets a graph G′ for which $\lambda = O(\sqrt{d})$. Our proofs are based on the techniques of Friedman Kahn and Szemeredi from STOC 1989, who proved similar results for regular graphs. Our results are useful for extending the analysis of certain heuristics to sparser instances of NP‐hard problems. We illustrate this by removing some unnecessary logarithmic factors in the density of k‐SAT formulas that are refuted by the algorithm of Goerdt and Krivelevich from STACS 2001. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005