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?

Thanks in advance



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.