Return to Colloquia & Seminar listing
On the Largest Eigenvalue of a Sparse Random Subgraph of the n-cube
ProbabilitySpeaker: | 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$.