# Differentiating condition for two infinite graphs

1. From the tiling of $$\mathbb{R}^2$$ with squares I get an infinite graph where each node has 4 neighbors.

2. I can create an infinite tree by attaching 4 nodes to a root node and then keep attaching 3 new nodes to each node. As a result, again each node has 4 neighbors, but the graphs are distinctly different.

3. In both, (1) and (2) all nodes and edges are identical, in that we can't find a condition on the graph that would be different for any two nodes (or edges).

What is the right way to describe the difference between these two graphs? Somehow (1) seems "denser", like if I cut out $$n$$ nodes, it has less edges "sticking out". Can we have, for every degree $$n$$, "dense" graphs that fulfill (3)?

## 2 Answers

On any locally finite graph (graph where every vertex has finite degree) you can consider a ball $$B_r(x)$$ of radius $$r$$ centered at a vertex $$x$$, given by the set of all vertices connected to $$x$$ by a path of length at most $$r$$. The growth rate of the size $$|B_r(x)|$$ as a function of $$r$$ is a kind of "local dimension" of the graph near $$x$$. This idea is commonly applied to Cayley graphs to describe the growth rate of a group in geometric group theory.

On $$\mathbb{Z}^2$$ the balls grow like $$\Theta(r^2)$$ (and more generally on $$\mathbb{Z}^n$$ they grow like $$\Theta(r^n)$$) but on the infinite $$4$$-ary tree the balls grow like $$\Theta(3^r)$$. One way to say this is that random walks on the infinite tree "spread out" much more than random walks on the infinite grid.

In group theory terms the first graph is the Cayley graph of $$\mathbb{Z}^2$$ and the second graph is the Cayley graph of the free group $$F_2$$, and this computation of their growth rates shows that they are not quasi-isometric.

The first one contains a cycle, but the second one not.