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.
Existence of $d$-regular expander graph that can be represented as a bipartite graph
graph theory;co.combinatorics;expanders
The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the 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, 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.