Bipartite Ramanujan Graphs of all Sizes

We show that a random d-regular bipartite graph is an optimal (i.e., Ramanujan) expander with nonzero probability. Notably, we use tools inspired by asymptotic (i.e., large n limit) random matrix theory to prove statements about finite dimensional matrices. The mediating role is be played by the expected characteristic polynomials of the random matrices in question, exploiting in particular their real-rootedness, interlacing, and invariance properties.