Spectral techniques applied to sparse random graphs

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