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)


  • $\begingroup$ You haven't given a construction. For example, which graph with degree sequence $5,5,5,4,4,4,3,3,3$ is $D_1$? $\endgroup$ – Misha Lavrov Mar 4 at 21:41
  • $\begingroup$ Oh okay I'll explain it better $\endgroup$ – Ultradark Mar 4 at 21:43
  • $\begingroup$ Okay, now we could compute, for instance, the eigenvalues of $D_1$ and $D_2$, but a construction should give us a rule for actually finding any graph $D_n$. Without that, the question remains under-specified. $\endgroup$ – Misha Lavrov Mar 4 at 22:31
  • $\begingroup$ Do I need to list all the vertices and what they connect to ? $\endgroup$ – Ultradark Mar 4 at 22:52
  • $\begingroup$ That's something you could do for any particular graph such as $D_1$ or $D_2$, but it still won't say what the family of graphs is. You should explain how someone would be able to list the vertices and edges of $D_3$, $D_4$, and so on, however far they wanted to go. $\endgroup$ – Misha Lavrov Mar 4 at 22:57

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)$.

  • $\begingroup$ Would anything change if the vertices were numbered differently? $\endgroup$ – Ultradark Mar 5 at 23:00
  • $\begingroup$ Nothing at all: I am just using the vertex numbering to have a convenient way to refer to the set $S$. Such a set of vertices would still exist (and have a neighborhood of the same size) no matter how the vertices were labeled. $\endgroup$ – Misha Lavrov Mar 6 at 0:57

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.