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 |
Description
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$.