Alon's conjecture in random bipartite biregular graphs with applications.

Probability Seminar

Gerandy Brito (Georgia Tech)

Thursday, November 2, 2017 -
3:15pm to 4:15pm
Location: 
119 Physics

This talk concerns to spectral gap in random regular graphs. We prove that almost all bipartite biregular graphs are almost Ramanujan by providing a tight upper bound for the second eigenvalue of its adjacency operator. The proof relies on a technique introduced recently by Massoullie, which we developed for random regular graphs. The same analysis allow us to recover hidden communities in random networks via spectral algorithms.

Last updated: 2017/11/18 - 10:21am