[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Spectral gap in random bipartite biregular graphs and applications
Ioana Dumitriu
UCSD Department of Mathematics
Abstract:
The asymptotics of the second-largest eigenvalue in random regular graphs (also referred to as the "Alon conjecture") have been computed by Joel Friedman in his celebrated 2004 paper. Recently, a new proof of this result has been given by Charles Bordenave, using the non-backtracking operator and the Ihara-Bass formula. In the same spirit, we have been able to translate Bordenave's ideas to bipartite biregular graphs in order to calculate the asymptotical value of the second-largest pair of eigenvalues, and obtained a similar spectral gap result. Applications include community detection in equitable graphs or frames, matrix completion, and the construction of channels for efficient and tractable error-correcting codes (Tanner codes). This work is joint with Gerandy Brito and Kameron Harris.
Tuesday, November 5, 2019
11:00AM AP&M 2402
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Ioana Dumitriu
UCSD Department of Mathematics
Abstract:
The asymptotics of the second-largest eigenvalue in random regular graphs (also referred to as the "Alon conjecture") have been computed by Joel Friedman in his celebrated 2004 paper. Recently, a new proof of this result has been given by Charles Bordenave, using the non-backtracking operator and the Ihara-Bass formula. In the same spirit, we have been able to translate Bordenave's ideas to bipartite biregular graphs in order to calculate the asymptotical value of the second-largest pair of eigenvalues, and obtained a similar spectral gap result. Applications include community detection in equitable graphs or frames, matrix completion, and the construction of channels for efficient and tractable error-correcting codes (Tanner codes). This work is joint with Gerandy Brito and Kameron Harris.
Tuesday, November 5, 2019
11:00AM AP&M 2402