Suppose that $G$ and $H$ are both expander graphs on the same node set $V$ with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. Let $G\cup H$ be the graph on $V$ with the smallest set of edges such that both, $G$ and $H$, are subgraphs of $G \cup 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$?
  • Is the case where $G$ and $H$ both have constant node degree any different?

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 the one given by $\lambda_G$ and $\lambda_H$.

  • 2
    $\begingroup$ How is $G \cup H$ defined here? $\endgroup$ – usul Apr 3 '14 at 18:55
  • 1
    $\begingroup$ To paraphrase usul's question, if some edge belongs to both $G$ and $H$, will we get a double edge in $G \cup H$? If so, then at least in the regular case, you can get a good bound using trivial linear algebra, using the characterization of the eigenvalue gap as $\min_{x \perp \mathbf{1}} \langle Lx,x\rangle/\langle x,x\rangle$, where $L$ is the Laplacian. $\endgroup$ – Yuval Filmus Apr 3 '14 at 20:12
  • $\begingroup$ @YuvalFilmus, usul: I'm interested in the where we merge multiple copies of the "same" edge, if it is present in $G$ and $H$. (I've added a clarification.) $\endgroup$ – Peter Apr 4 '14 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.