5
$\begingroup$

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$.

$\endgroup$
  • $\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 'SO- stop being evil' Apr 4 '14 at 1:17