# Eigenvalues of Random Regular Bipartite Graphs

I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am looking to extend the estimates to a more general scenario I dont want to get into very involved techniques. The kind of bounds I am looking for can have constant (or even log factors) thrown around.

One way I have in my mind is to use the matrix Bernstein inequality by expressing a random bipartite d-regular graph as a sum of d independent random matchings and then black box the Matrix Bernstein Inequality result. This gives satisfactory answers for me with the caveat that summing up d random matchings does not necessarily produce simple graphs (edges can get repeated), however I feel that the estimate that we get from Matrix Bernstein should hold for the random regular graph case too. Is there an easy way to get around this difficulty?

• In what range of $d$ are you interested (compared to the size of the graph)? – ofer zeitouni Jan 12 '15 at 13:30
• Ideally I wouldnt want that constrained but for the first step I am looking at $d$ about $\log(n)$ – user1189053 Jan 13 '15 at 13:34
• I don't know about bipartite graphs but for G(n,p) one can estimate the probability that a G(n,p) graph is np regular and use it to deduce results for d-regular graphs for $d\to\infty$. I learnt that this can be useful from arxiv.org/pdf/1011.6646.pdf (see the beginning of section 2) and I suspect something similar could work in your setup. – ofer zeitouni Jan 13 '15 at 14:10