Spectral techniques applied to sparse random graphs
2005; Wiley; Volume: 27; Issue: 2 Linguagem: Inglês
ISSN
1098-2418
Autores Tópico(s)Advanced Graph Theory Research
ResumoWe 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
Referência(s)