3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 21 '17 at 23:31
  • $\begingroup$ @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. $\endgroup$ – Stupid_Guy Jul 22 '17 at 3:07
  • 2
    $\begingroup$ cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf $\endgroup$ – Sasho Nikolov Jul 22 '17 at 3:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Yixin Cao Jul 22 '17 at 13:14
  • 2
    $\begingroup$ 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 $\endgroup$ – holf Jul 22 '17 at 15:22
4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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 :) $\endgroup$ – Sasho Nikolov Jul 23 '17 at 2:37
  • $\begingroup$ Ok, thanks for the clarification. $\endgroup$ – David Eppstein Jul 23 '17 at 2:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.