There is a well-known relation between combinatoric expansion and the gap between the first and the second largest eigenvalues (Dodziuk 1984) : $$ h(G) \le d \sqrt{2 (1 - \alpha)} $$ where $$h(G) = \min\limits_{S\subseteq V;\; |S|\le|V|/2} \frac{|E(S,V\setminus S)|}{|S|},$$ $\lambda_2 = \alpha \lambda_1 = \alpha d$ and $E(X,Y) = E \cap (X \times Y)$.

The problem is that this connection holds only for $d$-regular graphs, for non-regular graphs the largest eigenvalue is harder to compute.

However the expansion $h(G)$ is defined for non-regular graphs. $G$ is $(n/2, d, c)$-expander if $h(G) \ge c$ and all degrees of the vertices of $G$ is at most $d$. I would like to somehow convert such graph into an algebraic expander. What I really need from an algebraic expander that combinatoric one lacks is the mixing lemma: $$ \left|{|E(S,T)| \over |V|} - {d |S| |T| \over |V|}\right| \le \alpha d \sqrt{|S||T|}. $$

What I can do is add loops to $G$ such that it is $d$-regular. This modification does not affect $h(G)$ so the resulting graph $G'$ is $(n,d,\alpha)$ algebraic expander for some $\alpha$. Therefore the mixing lemma works for $G'$. But for disjoint $S$ and $T$ $E_G(S,T) = E_{G'}(S,T)$ so the mixing lemma works for disjoint $S$ and $T$ in $G$ as well.

Is there a flaw in this argument? And is there a better way to extract an algebraic properties from a combinatoric expander? Is there a way to get mixing lemma for non-disjoint sets?

Dodziuk, Jozef, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Am. Math. Soc. 284, 787-794 (1984). ZBL0512.39001.


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.