Special properties of bipartite expanders

Question

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.

Answer 1

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

• The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing. [http://arxiv.org/abs/1304.4132]

• The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders. [ http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2 ][ http://arxiv.org/abs/math/0406038 ]

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)