Spectral techniques applied to sparse random graphs

被引:150
作者
Feige, U [1 ]
Ofek, E [1 ]
机构
[1] Weizmann Inst Sci, Dept Comp Sci & Appl Math, IL-76100 Rehovot, Israel
关键词
D O I
10.1002/rsa.20089
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:251 / 275
页数:25
相关论文
共 50 条
[21]   The largest eigenvalue of sparse random graphs [J].
Krivelevich, M ;
Sudakov, B .
COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (01) :61-72
[22]   Sparse random graphs: Eigenvalues and eigenvectors [J].
Tran, Linh V. ;
Vu, Van H. ;
Wang, Ke .
RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (01) :110-134
[23]   Uniformly Random Colourings of Sparse Graphs [J].
Hurley, Eoin ;
Pirot, Francois .
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, :1357-1370
[24]   The cover time of sparse random graphs [J].
Cooper, Colin ;
Frieze, Alan .
RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (1-2) :1-16
[25]   Sparse Quasi-Random Graphs [J].
Fan Chung ;
Ronald Graham .
Combinatorica, 2002, 22 :217-244
[26]   Sparse Graphs: Metrics and Random Models [J].
Bollobas, Bela ;
Riordan, Oliver .
RANDOM STRUCTURES & ALGORITHMS, 2011, 39 (01) :1-38
[27]   PUSH IS FAST ON SPARSE RANDOM GRAPHS [J].
Meier, Florian ;
Peter, Ueli .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (01) :29-49
[28]   FLOODING IN WEIGHTED SPARSE RANDOM GRAPHS [J].
Amini, Hamed ;
Draief, Moez ;
Lelarge, Marc .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) :1-26
[29]   Largest sparse subgraphs of random graphs [J].
Fountoulakis, Nikolaos ;
Kang, Ross J. ;
McDiarmid, Colin .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 35 :232-244
[30]   LARGE HOLES IN SPARSE RANDOM GRAPHS [J].
FRIEZE, AM ;
JACKSON, B .
COMBINATORICA, 1987, 7 (03) :265-274