Spectral techniques applied to sparse random graphs

We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let lambda(1) >= (...) >= lambda(n) be the eigenvalues of an n-vertex graph, and lambda = max[lambda(2), P.,,11, Let c be a large enough constant. For graphs of average degree d = c log n it is well known that lambda(1) >= d, and we show that lambda = O(root d). For d = c it is no longer true that lambda = O(root 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(root 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. (c) 2005 Wiley Periodicals, Inc.