7
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ How is $G \cup H$ defined here? $\endgroup$
    – usul
    Apr 3, 2014 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, 2014 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, 2014 at 7:21

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.