4
$\begingroup$

It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc.

However, I am curious if there are any special properties of bipartite expanders that more general families of expanders don't have (or vice versa). In particular, are there any extreme differences, where bipartite and non-bipartite expanders differ greatly (especially in a combinatoric, algorithmic, or complexity-theoretic sense)?

A priori, we might expect that bipartite and non-bipartite expanders would likely share many pseudorandom properties, and in fact are constructible from each other. So that would suggest a negative answer to this question.

On the other hand, bipartite graphs in general have many special properties (eg. König's theorem) that have complexity-theoretic implications. So it's not unreasonable to think that differences between random bipartite and non-bipartite graphs may yield interesting differences between bipartite and non-bipartite expanders.

This is sort of a vague, open ended question, since I'm not exactly sure what kind of answer I'd like, and I am open to any interpretation. However, an example of a 'non-answer' might be 'bipartiteness is distinguished by the smallest eigenvalue in the spectrum'; I'm more interested in specifically bipartite expanders rather than spectral properties of bipartite graphs as a whole.

$\endgroup$
2
$\begingroup$

Two things come to mind when I hear "bipartite expanders"

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)

$\endgroup$
  • $\begingroup$ Yeah - it's not intuitive for me when results are true only of bipartite expanders vs. our limited ability to prove such properties about expanders. $\endgroup$ – Joe Bebel Apr 16 '15 at 3:22
  • $\begingroup$ The special property that makes the MSS construction of Ramanujan graphs go though for bipartite graphs but does not hold in general graphs is that the eigenvalues are symmetric around 0. $\endgroup$ – Sasho Nikolov Apr 16 '15 at 4:44
  • 1
    $\begingroup$ @SashoNikolov Actually the MSS proof doesn't even need the parity symmetric nature. Thats why I said that the proof is little more general than that. All that they need is that the spectral radius of the graph is upper bounded by the largest eigenvalue. It just so happens that for bipartite graphs this condition is true. $\endgroup$ – Anirbit Apr 16 '15 at 22:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.