<p>Does Spectral Gap remains same after removal of some edges from a Expander Graph ? </p>

<p>Suppose we take a d-regular graph and remove m edges from it. For a $d$-regular graph We have $\lambda_1 = d$ and $\lambda_2 \leq (1-\epsilon)d $. After removing $m &gt;=0 $ edges, will we have the same spectral gap i.e. $|\lambda_1 - \lambda_2|$ . </p>

CC BY-SA 3.0
2015-03-02T17:34:37.487Z
No? What makes you think this might be true?
Huck Bennett
CC BY-SA 3.0
2015-03-02T17:39:43.487Z
After removing some edges, the graph will not be regular (usually). Is spectral gap even well-defined then?
Emil Jeřábek
CC BY-SA 3.0
2015-03-02T17:43:19.597Z
After removing some edges, we may have a large connected component. So can we determine size of that component using spectral gap ?
user1590205
CC BY-SA 3.0
2015-03-02T18:55:57.510Z
The whole purpose of the spectral gap is as a measure of how connected the graph is, so it's weird to think that removing edges wouldn't affect it. Imagine starting with the complete graph (which has spectral gap 1), and deleting edges until you have another connected, regular graph (which must have spectral gap <1).
Huck Bennett
CC BY-SA 3.0
2015-03-02T19:17:17.820Z
Based on your last comment, do you want to give a lower bound on the size of the largest connected component of an expander graph $G$ after removing $k$ edges? I think you can get such a lower bound easily from the Cheeger constant.
Sasho Nikolov
CC BY-SA 3.0
2015-03-03T09:25:12.617Z
@Huck I am new to expanders. Correct me if i am wrong. I think spectral gap for complete graph is $n$ as eigen values are $n-1$ and $-1$. Actually what i need is size of the connected component. What factors gonna affect it. Spectral gap gonna reduce, So can i relate that ??
user1590205
CC BY-SA 3.0
2015-03-03T09:33:06.133Z
@Sasho Cheeger constant gives lower bound for d-regular graph. Can you please tell me how can i relate Cheegar constant to a d-regular graph after removal of m edges ??
user1590205
CC BY-SA 3.0
2015-03-03T15:29:25.340Z
User1590205, a d-regular graph has d as it's largest eigenvalue (even in absolute value) so we often normalize things by dividing all eigenvalues by d. That is why Huck starts with 1 as an eigenvalue, removed edges to get another regular graph with regularity parameter d' < d, doesn't renormalize (of course), and ends with a graph having largest eigenvalue < 1 (even in absolute value).
Tyson Williams
CC BY-SA 3.0
2015-03-03T16:13:16.107Z
Thanks Sasho .One more thing.. How to prove that size of the connected component is at least $n-m/h$ ?
user1590205
<expanders>
Spectral Gap in Expander Graphs
user1590205
# Spectral Gap in Expander Graphs

(Asked by: username_0 on 2015-03-02)

Does Spectral Gap remains same after removal of some edges from a Expander Graph ?

Suppose we take a d-regular graph and remove m edges from it. For a $d$-regular graph We have $\lambda\_1 = d$ and $\lambda\_2 \leq (1-\epsilon)d $. After removing $m >=0 $ edges, will we have the same spectral gap i.e. $|\lambda\_1 - \lambda\_2|$ .

**Tags:** expanders

> **Comments:**
> **username_1**: No? What makes you think this might be true?  
> **username_2**: After removing some edges, the graph will not be regular (usually). Is spectral gap even well-defined then?  
> **username_0**: After removing some edges, we may have a large connected component. So can we determine size of that component using spectral gap ?  
> **username_1**: The whole purpose of the spectral gap is as a measure of how connected the graph is, so it's weird to think that removing edges wouldn't affect it. Imagine starting with the complete graph (which has spectral gap 1), and deleting edges until you have another connected, regular graph (which must have spectral gap <1).  
> **username_3**: Based on your last comment, do you want to give a lower bound on the size of the largest connected component of an expander graph $G$ after removing $k$ edges? I think you can get such a lower bound easily from the Cheeger constant.  
> **username_0**: @Huck I am new to expanders. Correct me if i am wrong. I think spectral gap for complete graph is $n$ as eigen values are $n-1$ and $-1$. Actually what i need is size of the connected component. What factors gonna affect it. Spectral gap gonna reduce, So can i relate that ??  
> **username_0**: @Sasho Cheeger constant gives lower bound for d-regular graph. Can you please tell me how can i relate Cheegar constant to a d-regular graph after removal of m edges ??  
> **username_4**: User1590205, a d-regular graph has d as it's largest eigenvalue (even in absolute value) so we often normalize things by dividing all eigenvalues by d. That is why Huck starts with 1 as an eigenvalue, removed edges to get another regular graph with regularity parameter d' < d, doesn't renormalize (of course), and ends with a graph having largest eigenvalue < 1 (even in absolute value).  
> **username_0**: Thanks Sasho .One more thing.. How to prove that size of the connected component is at least $n-m/h$ ?  

---

## 0 answers

