On the Largest Eigenvalue of a Random Subgraph of the Hypercube
Skip to main content
eScholarship
Open Access Publications from the University of California

On the Largest Eigenvalue of a Random Subgraph of the Hypercube

  • Author(s): Soshnikov, Alexander
  • Sudakov, Benny
  • et al.

Published Web Location

https://arxiv.org/pdf/math/0209178.pdf
No data is associated with this publication.
Abstract

Let G be a random subgraph of the n-cube where each edge appears randomly and independently with probability p. We prove that the largest eigenvalue of the adjacency matrix of G is almost surely \lambda_1(G)= (1+o(1)) max(\Delta^{1/2}(G),np), where \Delta(G) is the maximum degree of G and o(1) term tends to zero as max (\Delta^{1/2}(G), np) tends to infinity.

Item not freely available? Link broken?
Report a problem accessing this item