2
$\begingroup$

Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$?

My intuition is that $B_r$ will have very low expansion, perhaps exponentially small in $r$. The reason for this is that expander graphs are locally tree-like, and finite trees -- which is what I am imagining obtaining upon restricting to $B_r$ -- are the worst possible expanders.

I am thinking in particular about the case where $G$ is the Cayley graph of an infinite discrete group with exponential growth, but would be interested in understanding the answer more generally.

Improve this question
$\endgroup$
11
  • $\begingroup$ How does one define the notion of expander for a single infinite graph? The definition I know is for a sequence of finite graphs. $\endgroup$
    – Moishe Kohan
    Commented Dec 2, 2023 at 20:10
  • $\begingroup$ one normally just defines the expansion as the minimum expansion of any finite region. from this definition one sees that infinite trees are excellent expanders, while finite ones are very poor expanders (hence the intuition above) $\endgroup$
    – user3521569
    Commented Dec 2, 2023 at 20:25
  • $\begingroup$ Could you give an actual definition? I know how to define an expansion constant (the Cheeger constant) for a finite graph but then what? $\endgroup$
    – Moishe Kohan
    Commented Dec 2, 2023 at 20:30
  • 1
    $\begingroup$ @MoisheKohan - I believe that you and user3521569 are talking past each other. This is not helped by the fact that user3521569 gave the wrong definition for the expansion of an infinite graph. The correct definition is (I believe) given at the link user3521569 provided. $\endgroup$
    – Sam Nead
    Commented Dec 3, 2023 at 10:45
  • 1
    $\begingroup$ See this paper combinatorics.org/ojs/index.php/eljc/article/view/v29i2p23/pdf for a similar (open) question on sequences of finite graphs rather than infinite graphs (though infinite graphs are briefly mentioned in Section 3). $\endgroup$
    – Louis Esperet
    Commented Dec 11, 2023 at 17:04

1 Answer 1

Reset to default
1
$\begingroup$

Not an answer, but an intuition for an answer (suggesting that balls should have exponentially small Cheeger constant).

Suppose that $n \geq 2$. The volume of $B^n(R)$, the ball of radius $R$ in $n$-dimensional hyperbolic space, is basically some constant (depending on $n$) times $e^{(n - 1)R}$. In dimension one ($n = 1$) we instead have some constant times $R$.

Suppose now that $M$ is a closed connected hyperbolic $n$-manifold. Pick a basepoint $x$ in $M$ and pick a graph $\Gamma$ in $M$ that nicely carries the fundamental group of $M$. Lift all of this to the universal cover $M'$ to get a graph $\Gamma'$ which is quasi-isometric to $n$-dimensional hyperbolic space. So $\Gamma'$ will be expansive, and will be roughly as expansive as balls in the ambient hyperbolic space.

So we can move interchangably between large balls in the graph $\Gamma'$ and large balls in hyperbolic space. Let's assume that $n$ is at least three. Now consider $B^n(R)$, the ball of radius $R$ in $n$-dimensional hyperbolic space. This is cut exactly in half by its "equatorial disk", a copy of $B^{n-1}(R)$. The volume of half of $B^n(R)$ is roughly $e^{(n-1)R}$. The volume of the equatorial disk is roughly $e^{(n-2)R}$. So the ratio is $e^{-R}$, as suggested by the original question.

To make these examples work, we needed a notion of dimension. So it is not exactly clear how this generalises.

Improve this answer
$\endgroup$
1
  • $\begingroup$ great, thanks for making the above intuition more precise. might it be possible to always find some embedding of an expander into an appropriate hyperbolic space? some googling says that ML people will occasionally due this but I did not find any rigorous results. $\endgroup$
    – user3521569
    Commented Dec 3, 2023 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .