How does the size of an n-ball (of a graph) scale as a function of n for various centers of the ball

Let $G$ be a connected locally finite graph with countably infinitely many vertices. Consider $B_n(v)$, the ball of radius $n$ centerd at vertex $v\in G$, that is, the set of all vertices that are a distance $n$ or less to $v$. I suspect that the way that the ball grows as $n$ increases should be independent of $v$. To be more precise, I suspect that if the function $f_v(n) := |B_n(v)| \in O(g(n))$, then so must $f_w(n) \in O(g(n))$ for any $w\in G$.

My reason for suspecting this is that, because the graph $G$ is assumed to be connected, we have a finite path between any two vertices $v$ and $w$. As $n$ grows, the balls of radius $n$ will overlap evermore, and thus the size of the balls should be similar.

I would like a proof/counter example of this claim, and if applicable, the name of the theorem.

Solution 1:

If two vertices $v,w$ are at distance $d$, then $f_v(n) \ge f_w(n-d)$ and $f_w(n) \ge f_v(n-d)$. Whether this gets us what we want depends on how quickly these functions grow: can we say that $f_v(n) = O(f_v(n-d))$? That's true when the growth rate is at most exponential, which covers all graphs you typically encounter.

However, it's possible to write down functions that don't have this behavior. For example, if $f_v(n)$ grows like $2^{n^2}$, then it is not even true that $2^{n^2} = O(2^{(n-1)^2})$; there is a factor of $2^{2n-1}$ difference.

It's also possible to draw locally finite graphs where $f_v(n)$ will have this growth rate. Take a half-infinite path $v_1, v_2, v_3, \dots$ and let $w = v_1$ and $v = v_2$. Right now, we have $$f_v(n) = \begin{cases}1 & n=0 \\ n+2 & n \ge 1\end{cases}$$ But suppose we add $\ell_i$ leaves to $v_i$ for every $i \ge 3$. Then we will have $$ f_v(n) = \begin{cases}1 & n=0 \\ 3 & n=1 \\ (n + 2) + \ell_3 + \dots + \ell_{n+1} & n\ge 2\end{cases} $$ and it is easy to choose $\ell_3, \ell_4, \dots$ so that for all $n \ge 2$, $f_v(n) = 2^{n^2}$.

In this example, $f_w(n)$ will lag behind: its growth rate will be "merely" $O(2^{(n-1)^2})$. Even though it is always just one step behind $v$, that one step makes all the difference.