0
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ No? What makes you think this might be true? $\endgroup$
    – Huck Bennett
    Mar 2, 2015 at 17:34
  • $\begingroup$ After removing some edges, the graph will not be regular (usually). Is spectral gap even well-defined then? $\endgroup$
    – Emil Jeřábek
    Mar 2, 2015 at 17:39
  • 6
    $\begingroup$ 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). $\endgroup$
    – Huck Bennett
    Mar 2, 2015 at 18:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Mar 2, 2015 at 19:17
  • 1
    $\begingroup$ 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). $\endgroup$
    – Tyson Williams
    Mar 3, 2015 at 15:29

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.