<p>Two things come to mind when I hear "bipartite expanders" </p>

<ul>
<li><p>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. [<a href="http://arxiv.org/abs/1304.4132]" rel="nofollow">http://arxiv.org/abs/1304.4132]</a> </p></li>
<li><p>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. [ <a href="http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2" rel="nofollow">http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2</a> ][ <a href="http://arxiv.org/abs/math/0406038" rel="nofollow">http://arxiv.org/abs/math/0406038</a>  ]</p></li>
</ul>

<p>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) </p>

CC BY-SA 3.0
2015-04-16T03:22:09.407Z
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.
Joe Bebel
CC BY-SA 3.0
2015-04-16T04:44:10.473Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-04-16T22:14:03.670Z
@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.
Student
CC BY-SA 3.0
2015-04-13T05:36:42.070Z
2015-04-16T00:06:41.047Z
2015-04-16T00:06:41.047Z
Student
<p>It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. </p>

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

<p>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.</p>

<p>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.</p>

<p>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 <em>expanders</em> rather than spectral properties of bipartite graphs as a whole.</p>

<graph-theory><graph-algorithms><co.combinatorics><expanders><pseudorandomness>
Special properties of bipartite expanders
Joe Bebel
# Special properties of bipartite expanders

(Asked by: username_0 on 2015-04-12)

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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, expanders, pseudorandomness

---

## 1 answers

### Answer by username_1 on 2015-04-13. Score: 2

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)

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_1**: @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.  

---

