5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ In what range of $d$ are you interested (compared to the size of the graph)? $\endgroup$ Jan 12, 2015 at 13:30
  • $\begingroup$ Ideally I wouldnt want that constrained but for the first step I am looking at $d$ about $\log(n)$ $\endgroup$ Jan 13, 2015 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$ Jan 13, 2015 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$ Jan 13, 2015 at 19:06

0

Your Answer

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