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

  • $\begingroup$ In what range of $d$ are you interested (compared to the size of the graph)? $\endgroup$ – ofer zeitouni Jan 12 '15 at 13:30
  • $\begingroup$ Ideally I wouldnt want that constrained but for the first step I am looking at $d$ about $\log(n)$ $\endgroup$ – user1189053 Jan 13 '15 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – ofer zeitouni Jan 13 '15 at 14:10
  • $\begingroup$ Thanks for the reference. I agree something like this would work here. We would need to show a similar result for random bipartite graphs which is not immediately clear to me. $\endgroup$ – user1189053 Jan 13 '15 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.