On the Largest Eigenvalue of a Random Subgraph of the Hypercube

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 λ_1(G)= (1+o(1)) max(Δ^{1/2}(G),np), where Δ(G) is the maximum degree of G and o(1) term tends to zero as max (Δ^{1/2}(G), np) tends to infinity.

Final version (to appear in Commun. Math. Phys.)