Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$.

  • What can be said about the expansion of graph $G \cup H$? In particular, is the spectral gap of $G \cup H$ at least as large as the minimum of the spectral gaps of $G$ and $H$?
  • Does it make a difference whether $G$ and $H$ both have constant node degree?

This is certainly true for the edge expansion of $G \cup H$, since it can only increase by adding edges. I know that spectral expansion and edge expansion are related by the Cheeger inequality, but using this route we only get a bound on the spectral expansion of $G \cup H$ that is worse than $\lambda_G$ and $\lambda_H$.


closed as off-topic by Yuval Filmus, Juho, David Richerby, FrankW, Gilles Apr 4 '14 at 1:17

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Perhaps you should ask this on cstheory. $\endgroup$ – Yuval Filmus Apr 3 '14 at 1:54
  • 1
    $\begingroup$ Or MathOverflow? But please don't just post a second copy there: pick one place, click the "flag" link and ask the moderators to migrate your post. $\endgroup$ – David Richerby Apr 3 '14 at 7:55
  • 1
    $\begingroup$ now on tcs.se $\endgroup$ – vzn Apr 3 '14 at 15:44
  • 3
    $\begingroup$ Manually migrated to another site, cstheory.se. $\endgroup$ – Yuval Filmus Apr 3 '14 at 20:13
  • $\begingroup$ Although the question is on-topic, it has been reposted on Theoretical Computer Science, so I am closing it here. $\endgroup$ – Gilles Apr 4 '14 at 1:17