Spectral Techniques Applied to Sparse Random Graphs

Feige, U and Ofek, E (2003) Spectral Techniques Applied to Sparse Random Graphs . Technical Report MCS03-01, Mathematics & Computer Science, Weizmann Institute of Science.

Full text available as:
Postscript - Requires a viewer, such as GhostView

Abstract

We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let $\lambda_1 \geq \ldots \geq \lambda_n$ be the eigenvalues of an $n$ -vertex graph, and let $\lambda = \max[\lambda_2,\vert\lambda_n\vert]$ . Let $c$ be a large enough constant.For graphs of average degree $d = c\log n$ it is well known that $\lambda_1 \geq 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 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.

Subjects:	Q Science: QA Mathematics: QA75 Mathematics & Computer science
ID Code:	307
Deposited By:	Feige, Prof. Uriel
Deposited On:	27 Febuary 2003


Wisdom Archive	Home \|\| About \|\| Browse \|\| Search \|\| User Area \|\| Help