1
$\begingroup$

Consider the family of graphs of degree $6$ with vertex set $V_n=(a, b, c)$ for all $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,c-1), (a,b, c+1)$, with all operations modulo $n$. Show that this is not a family of expander graphs.

I've been struggling with this question for over a week. I tried looking at from the algebraic perspective and show that the spectral gap is getting smaller as n(the number of vertexes) rise. But I got stuck a long the way and now I don't know if I'm on the right track at all.

$\endgroup$
0
$\begingroup$

Given $n$, consider the set of vertices $S = \{ (a,b,c) : c < n/2 \} \subseteq V_n$. Assuming for simplicity that $n$ is even, this set contains exactly half the vertices. An edge connects $x \in S$ to $y \notin S$ iff $x = (a,b,n/2-1)$ and $y = (a,b,n/2)$, for a total of $n^2$ edges. Therefore the expansion of $S$ is $|E(S,\overline{S})|/|S| = n^2/(n^3/2) = 1/n$, which converges to zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.