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.

Improve this question
$\endgroup$
6
  • 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, 2017 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$
    – zxzx179
    Jul 22, 2017 at 3:07
  • 2
    $\begingroup$ cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf $\endgroup$
    – Sasho Nikolov
    Jul 22, 2017 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, 2017 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, 2017 at 15:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2017 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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