For a graph $G = (V, E)$, its Cheeger constant $h(G)$ is defined by
$$h(G) = \min_{S \subseteq V,\; 0 < |S| \le \frac{|V|}{2}} \frac{|\partial S|}{|S|} ,$$
where $\partial S$ is the set of edges with one vertex in $S$ and one vertex outside of $S$. Expander graphs are families of graphs where $h(G) \ge C$, for some $C > 0$ independent of the size of the graph.
The ratio of boundary to interior seems similar to a property of the hyperbolic plane: as the radius of a circle increases, its circumference divided by its area approaches a fixed ratio. Since there are tilings of the hyperbolic plane, it seems like there may be a connection. Could the Octagonal tiling be turned into an expander graph family?
Best Answer
I am interested in both of these notions, so naturally I have thought about this a bit...
Expander graphs are by definition (families of) finite graphs, while the tilings of the hyperbolic plane are infinite. So you would need to either define infinite expander graphs (no idea how to do that) or to consider finite restrictions of the hyperbolic tilings.
The simplest method of making a finite hyperbolic tiling is to take a finite section of a hyperbolic tiling, for example, the set of vertices in distance at most $r$ steps from the given vertex $v_0$. The number of such vertices is exponential in $r$. However, this is not an expander graph, because it has a small separator: consider two geodesics from $v_0$ to the edge, they split our graph in two parts. Let $S$ be one of these parts (that is smaller than $|V|/2$ but still exponential in $r$); $\delta S$ will be proportional to $r$, so the Cheggar constant is arbitrarily small. (In other words, hyperbolic tilings have small separators/treewidth, while expanders do not.) In my opinion this shows that this approach does not work with any reasonable generalization of expanders to infinite graphs. (Infinite tiling seems to also have a "small" separator made of two infinite halflines, although it is not clear what "small" means if both the separator and the two subsets it separates are infinite.)
Another method would be to consider a finite area quotient of the hyperbolic plane, created for example using algorithms described here or here. I am quite sure these graphs should be expander graphs, but I have not tried to prove this.