A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts

Charles Bordenave

It was conjectured by Alon and proved by Friedman that a random $d$-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the no…