1
$\begingroup$

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.

$\endgroup$

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.