Graphs with edges corresponding to powers of 2 I am interested in the following graphs: $\Gamma_n$ has vertex set $V_n=\{0,\ldots,2^n-1\}\subset\mathbb{Z}$ and two vertices $a,b$ span an edge whenever $|a-b|$ is a power of $2$.
Does the family of graphs $(\Gamma_n)$ form an expander? 
These graphs are not regular, so perhaps one way would be to show that the following value (called the Cheeger constant) is bounded away from $0$:
$$
h(\Gamma_n) = \inf\left\{ \frac{|\partial A|}{|A|} \mid A\subset V_n,\ 0<|A|\leq 2^{n-1}\right\}
$$
where $\partial A$ is the set of all vertices in $V\setminus A$ with a neighbour in $A$.
A lower bound of the form $h(\Gamma_n)\geq Cn^{-1/2}$ for some uniform constant $C$ follows from the fact that $\Gamma_n$ contains a hypercube graph.
 A: No, the same sets that show that the hypercube is not a vertex expander show that this graph is not a vertex expander.
Suppose $n$ is even.  Let $\theta(x)$ be the number of 1's in the binary expansion of $x$ and let
$S=\theta^{-1}([0,n/2])$ be the set of integers between $0$ and $2^n$ whose binary expansion contains at most $n/2$ 1's.  This is about half of the vertices.  
$\theta$ is not quite a Lipschitz function on $\Gamma_n$, but it's usually Lipschitz.  The only way that two adjacent vertices, say $x$ and $x+2^k$, can have a large difference in $\theta$ is if the binary expansion of $x$ has a long run of 1's that ends at the $2^k$'s digit.  
So let $\rho(x)$ be the largest number of consecutive 1's or consecutive 0's in the binary expansion of $x$.  For all $x,k$, $|\theta(x\pm 2^k)-\theta(x)|\le \rho(x)$.  
That means that $\partial S$ consists of points $x\not \in S$ such that $\rho(x)\ge \theta(x)-\frac{n}{2}$.
The number of integers below $2^n$ with $\theta(x)=\frac{n}{2}+k$ and $\rho(x)=k$ is roughly $\frac{2^n}{\sqrt{n}}$ when $k\le \log_2(n)$ and at most $\frac{n2^n}{2^k}$ when $k\ge \log_2(n)$, so 
$$|\partial S|\le C \log_2(n)\frac{2^n}{\sqrt{n}}+\sum_{k=2\log_2(n)}^\infty \frac{n2^n}{2^k}\le C' \log_2(n)\frac{2^n}{\sqrt{n}}$$
and $h(\Gamma_n)\le C'' \frac{\log n}{\sqrt{n}}$.
