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

<ul>
<li>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$? </li>
<li>Is the case where $G$ and $H$ both have constant node degree any different?</li>
</ul>

<p>This is certainly true for the <em>edge expansion</em> of $G \cup H$, since it can only increase by adding edges. 
I know that spectral expansion and edge expansion are related by the <a href="http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29#Cheeger_Inequalities" rel="nofollow">Cheeger inequality</a>, but using this route we only get a bound on the <em>spectral expansion</em> of $G \cup H$ that is worse than the one given by $\lambda_G$ and $\lambda_H$. </p>

CC BY-SA 3.0
2014-04-03T18:55:07.667Z
How is $G \cup H$ defined here?
usul
CC BY-SA 3.0
2014-04-03T20:12:16.103Z
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.
Yuval Filmus
CC BY-SA 3.0
2014-04-04T07:21:02.647Z
@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.)
Peter
<graph-theory><expanders>
Expansion of the union of two expander graphs
Peter
# Expansion of the union of two expander graphs

(Asked by: username_0 on 2014-04-03)

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](http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29#Cheeger_Inequalities), 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$.

**Tags:** graph-theory, expanders

> **Comments:**
> **username_1**: How is $G \cup H$ defined here?  
> **username_2**: To paraphrase username_1'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.  
> **username_0**: @YuvalFilmus, username_1: 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.)  

---

## 0 answers

