1
$\begingroup$
  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)?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.