# Existence of $d$-regular expander graph that can be represented as a bipartite graph

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.

• I think there are construction of constant degree bipartite spectral expanders (e.g. the famous arxiv.org/pdf/1304.4132.pdf), which together with Cheeger should imply what you want. – Sasho Nikolov Jul 21 '17 at 23:31
• @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. – Stupid_Guy Jul 22 '17 at 3:07
• cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf – Sasho Nikolov Jul 22 '17 at 3:57
• 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 Jul 22 '17 at 13:14
• The probabilistic method usually used to show the existence of expanders also works in the bipartite case. It is sometimes presented this way first: people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf – holf Jul 22 '17 at 15:22