Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

On the Largest Eigenvalue of a Sparse Random Subgraph of the n-cube

Probability

Speaker: Alexander Soshnikov, UC Davis
Location: 693 Kerr
Start time: Tue, Nov 13 2001, 4:10PM

We consider a sparse random subgraph G of the n-cube where each edge appears independently with small probability $p(n) = O(n^{-1 +o(1)})$. We prove that the largest eigenvalue of the adjacency matrix is $\Delta(G)^{1/2} (1+o(1)) = \frac{ n \log 2}{ \log(p^{-1}) } \* (1+o(1))$ almost surely, where $ \Delta(G) $ is the maximum degree of $G$.