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.



Graphs with edges corresponding to powers of 2
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}}$.


