arXiv (Cornell University) · 2012 · 34 citations · 29 references
Open access
Natural SciencesMathematicsPhysicsProbability TheoryStochastic ProcessesTopologyFundamental GroupGraph TheoryGroup TheoryHomology TheoryConnectivity ThresholdsEigenvaluesErdős - Rényi GraphsFundamental Group Of A GraphGeometric Group TheoryGraph LaplacianRandom GraphsSpectral Gaps
We prove that for delta > 0, if p > (1/2 + delta) log n / n, then the normalized Laplacian of an Erdos-Renyi random graph has its nonzero eigenvalues tightly concentrated around 1. We also give sharp estimates for the concentration of the eigenvalues. This extends earlier work on spectra of random graphs into and through the threshold for connectivity. These new spectral results establish the existence of several sharp thresholds in random topology and geometric group theory. In particular, we show that the threshold for the fundamental group of random 2-complexes to have Kazhdan's property (T) agrees with the homology-vanishing threshold found earlier by Linial and Meshulam.
29
The eigenvalues of random symmetric matrices
Zoltán Füredi, János Komlós · COMBINATORICA · 1981 · 673 citations
On Tail Probabilities for Martingales
David A. Freedman · The Annals of Probability · 1975 · 646 citations · Full text
Random matrices: Universality of local eigenvalue statistics
Terence Tao, Van Vu · Acta Mathematica · 2011 · 454 citations · Full text