In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. In an expander graph most vertices are far apart from each other.
Expander graphs are known to be very difficult to explicitly construct, so I'm skeptical that this construction is an expander. However, I'm still curious. It seems plausible that this graph is an expander but I want to prove it or disprove it either way.
Expander graphs are studied extensively in computer science relating to the nearest neighbor problem, but have continued to attract more and more attention in pure math settings such as number theory, group theory, and geometry.
Here is the construction of this graph (need help making this mathematical):
$1)$ Take four vertices at the corners of a square with edges connecting all but the diagonals.
$2)$ Do number $1)$ for a mini square inside the previous square, rotated by $90$ degrees.
$3)$ Connect the larger to smaller square by connecting the two closest vertices for each corner.
$4)$ Make another mini square inside the previous square.
$5) $Keep repeating the process.
The degree sequence is:
$$ D_N=\{4^8,6^{4N}\}, $$
for $N\in \Bbb N_0,$
where the superscripts are the number of vertices with the given degree.
So to go from $D_0 \to D_1 \to D_2 \to … \to D_N$ you essentially keep connecting square graphs inside square graphs.
Here is an example of the construction. This graph is $D_2:$ (need help making the image smaller)
[!][ConstructBackwards]1
Best Answer
These graphs are not good expander graphs.
If the vertices of $D_n$ are numbered $1, 2, 3, 4, \dots, 4(n+2)$ in order of construction, the way they are in the diagram, then for any $k$, the boundary of the vertex set $S_k = \{1,2,\dots, 4k\}$ consists of $8$ edges joining the vertices $\{4k-3,4k-2,4k-1,4k\}$ to the vertices $\{4k+1, 4k+2, 4k+3,4k+4\}$. Take $k$ to be about $\frac n2$ for maximum effect; by any measure, the boundary of $S$ is constant while $|S| \approx 2n$.
So $D_n$ has vertex expansion and edge expansion both on the order of $O(\frac1n)$.