On the largest eigenvalue of a sparse random subgraph of the hypercube

2001/07/31 by Alexander Soshnikov, Soshnikov, Alexander
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #math-ph #math.CO #math.MP #math.PR

paper · pdf · doi:10.48550/arxiv.math/0107229

arxiv created 2001/07/31 · arxiv updated 2009/11/30

Abstract

We consider a sparse random subraph of the n-cube where each edge appears independently with small probability p(n) =O(n^-1+o(1)). In the most interesting regime when p(n) is not exponentially small we prove that the largest eigenvalue of the graph is asymtotically equal to the square root of the maximum degree.

Related

• THe largest eigenvalue of sparse random graphs
• Eigenvalues of subgraphs of the cube
• Sparse random graphs: Eigenvalues and Eigenvectors
• Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large\n Deviations
• A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts