3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Good point about the small separator. What about this for a generalization to infinite graphs: Cheeger constant is defined as usual, but as a minimum over all finite subsets $S$. An infinite graph is an expander graph if and only if its Cheeger constant is positive. I think the hyperbolic tiling would satisfy this. $\endgroup$ – qbt937 Jul 2 '18 at 6:25
  • $\begingroup$ I think the tilings of quotients of the hyperbolic plane are just what I wanted. It seems like they should work as long as there are infinitely many finite quotient groups of the tiling's symmetry group. $\endgroup$ – qbt937 Jul 2 '18 at 6:38
  • 2
    $\begingroup$ Yes, hyperbolic tilings do satisfy this property. (Sketch of the proof: consider the polygon which contains all the points of the hyperbolic plane which are closer to elements of $S$ than to grid points not in $S$; |S| is proportional to the area of this polygon, which equals its defect, which is proportional to the number of vertices, which is proportional to $|\delta S|$) $\endgroup$ – Zeno Rogue Jul 2 '18 at 21:47
  • 1
    $\begingroup$ However, your property is satisfied by the full infinite binary tree. It feels to me that a definition of an infinite expander graph should not allow trees, because one of the most important properties of expander graphs is their strong connectivity, and trees are the opposite. Hyperbolic tilings have stronger connectivity than trees, but they are still very tree-like, so it feels to me that it should not be enough either (a good measure of tree-likeness here is the Gromov hyperbolicity of a graph -- it is finite for hyperbolic tilings). $\endgroup$ – Zeno Rogue Jul 2 '18 at 21:48
  • 2
    $\begingroup$ Actually, the infinite binary tree is a good conception of an infinite expander graph in a lot of ways. Expander graphs are "locally tree-like" graphs; under the random walk mass is not likely to be concentrated on any set, just like a random walk on an infinite binary tree. And spectrally, no finite d-regular graph can have better second eigenvalue than the infinite d-regular tree (Ramanujan graphs achieve this). A difference between the finite/infinite worlds is the uniform distribution is stationary distribution, whereas tree has no stationary distribution. $\endgroup$ – Chris Jones Feb 25 at 19:01

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.