<p>The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the <a href="https://en.wikipedia.org/wiki/Bipartite_double_cover" rel="nofollow noreferrer">bipartite double cover</a>, which preserves regularity. But it might not preserve expansion; in particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover.</p>

<p>But if all you need is constant expansion (rather than stronger properties like, say, being a Ramanujan graph) then converting a non-bipartite graph to a bipartite one while preserving constant expansion is easy: just subdivide each edge to make it bipartite (as Yixin Cao already suggested in comments), and then add enough extra edges to the subdivision vertices to make it regular again.</p>

<p>For the stronger expansion that you get from Ramanujan graphs, see Marcus, Spielman, and Srivastava "<a href="https://doi.org/10.1109/FOCS.2013.63" rel="nofollow noreferrer">Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees</a>", FOCS 2013. Judging from the abstract (I haven't read the paper carefully) they appear to be using the bipartite double cover idea, but with a bit more care to avoid the bottlenecks.</p>

CC BY-SA 3.0
2017-07-23T02:37:06.137Z
The 2-lifts used by MSS are similar to the bipartite double cover but are not the same, and if you apply a 2-lift to a non-bipartite graph you may very well get a non-bipartite graph. MSS however start with a bipartite graph and repeatedly apply 2-lifts, which preserve bipartiteness. I would also say that "a bit more care" gives the wrong impression of the power of their methods :)
Sasho Nikolov
CC BY-SA 3.0
2017-07-22T21:26:57.087Z
2017-07-23T02:33:41.283Z
2017-07-23T02:33:41.283Z
David Eppstein
<p>It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander graph that is also a bipartite graph? Thus I have a sparse bipartite graph example that does not have a $o(n)$-vertex/edge separator. </p>

<p>Note that by definition this bipartite graph is not exactly a bipartite expander graph, which only requires that every small subset on the left side of the bipartite graph to have large neighbors on the right.</p>

CC BY-SA 3.0
2017-07-21T23:31:31.090Z
I think there are construction of constant degree bipartite spectral expanders (e.g. the famous https://arxiv.org/pdf/1304.4132.pdf), which together with Cheeger should imply what you want.
Sasho Nikolov
CC BY-SA 3.0
2017-07-22T03:07:21.013Z
@SashoNikolov Thanks so much for pointing out the direction that I can search for! Really appreciated! BTW, if you don't mind, I was wondering if you could help suggest some textbook or material about expander graphs that I can read to learn, as a beginner? I don't have a expander graph course here in my university, so I have to learn by myself.
zxzx179
CC BY-SA 3.0
2017-07-22T03:57:36.950Z
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
Sasho Nikolov
CC BY-SA 3.0
2017-07-22T13:14:57.657Z
How about the graph obtained from an expander graph by subdividing each edge? BTW, the claim that "does not have a $o(n)$-vertex/edge separator" is not correct without the cardinality requirement.
Yixin Cao
CC BY-SA 3.0
2017-07-22T15:22:47.753Z
The probabilistic method usually used to show the existence of expanders also works in the bipartite case. It is sometimes presented this way first:  https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf
holf
CC BY-SA 3.0
2017-07-22T23:49:18.720Z
@YixinCao Thanks for the nice idea of subdivision! It's really beautiful! For the last sentence, I guess you mean we need to assume $n$ is sufficiently large?
zxzx179
<graph-theory><co.combinatorics><expanders>
Existence of $d$-regular expander graph that can be represented as a bipartite graph
zxzx179
# Existence of $d$-regular expander graph that can be represented as a bipartite graph

(Asked by: username_0 on 2017-07-21)

It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander graph that is also a bipartite graph? Thus I have a sparse bipartite graph example that does not have a $o(n)$-vertex/edge separator.

Note that by definition this bipartite graph is not exactly a bipartite expander graph, which only requires that every small subset on the left side of the bipartite graph to have large neighbors on the right.

**Tags:** graph-theory, co.combinatorics, expanders
> **Comments:**
> **username_1**: I think there are construction of constant degree bipartite spectral expanders (e.g. the famous https://arxiv.org/pdf/1304.4132.pdf), which together with Cheeger should imply what you want.  
> **username_0**: @SashoNikolov Thanks so much for pointing out the direction that I can search for! Really appreciated! BTW, if you don't mind, I was wondering if you could help suggest some textbook or material about expander graphs that I can read to learn, as a beginner? I don't have a expander graph course here in my university, so I have to learn by myself.  
> **username_1**: http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf  
> **username_2**: How about the graph obtained from an expander graph by subdividing each edge? BTW, the claim that "does not have a $o(n)$-vertex/edge separator" is not correct without the cardinality requirement.  
> **username_3**: The probabilistic method usually used to show the existence of expanders also works in the bipartite case. It is sometimes presented this way first:  https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf  
> **username_0**: @YixinCao Thanks for the nice idea of subdivision! It's really beautiful! For the last sentence, I guess you mean we need to assume $n$ is sufficiently large?  

---

## 1 answers

### Answer by username_4 on 2017-07-22. Score: 4 | Accepted answer

The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the [bipartite double cover](https://en.wikipedia.org/wiki/Bipartite_double_cover), which preserves regularity. But it might not preserve expansion; in particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover.

But if all you need is constant expansion (rather than stronger properties like, say, being a Ramanujan graph) then converting a non-bipartite graph to a bipartite one while preserving constant expansion is easy: just subdivide each edge to make it bipartite (as Yixin Cao already suggested in comments), and then add enough extra edges to the subdivision vertices to make it regular again.

For the stronger expansion that you get from Ramanujan graphs, see Marcus, Spielman, and Srivastava "[Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees](https://doi.org/10.1109/FOCS.2013.63)", FOCS 2013. Judging from the abstract (I haven't read the paper carefully) they appear to be using the bipartite double cover idea, but with a bit more care to avoid the bottlenecks.

> **Comments:**
> **username_1**: The 2-lifts used by MSS are similar to the bipartite double cover but are not the same, and if you apply a 2-lift to a non-bipartite graph you may very well get a non-bipartite graph. MSS however start with a bipartite graph and repeatedly apply 2-lifts, which preserve bipartiteness. I would also say that "a bit more care" gives the wrong impression of the power of their methods :)  

---

