Diferenciación de condiciones para dos gráficos infinitos

Question

1. Desde el enlosado de $\mathbb{R}^2$ con cuadrados obtengo un grafo infinito donde cada nodo tiene 4 vecinos.

2. Puedo crear un árbol infinito adjuntando 4 nodos a un nodo raíz y luego seguir adjuntando 3 nodos nuevos a cada nodo. Como resultado, de nuevo cada nodo tiene 4 vecinos, pero los grafos son claramente diferentes.

3. En ambos, (1) y (2) todos los nodos y aristas son idénticos, en el sentido de que no podemos encontrar una condición en el grafo que sea diferente para cualquier par de nodos (o aristas).

¿Cuál es la manera correcta de describir la diferencia entre estos dos grafos? De alguna manera, (1) parece "más denso", como si cortara $n$ nodos, tendría menos aristas "sobresaliendo". ¿Podemos tener, para cada grado $n$, grafos "densos" que cumplan (3)?

Answer 1

El primero contiene un ciclo, pero el segundo no.

Answer 2

En cualquier grafo localmente finito (grafo donde cada vértice tiene grado finito), se puede considerar una bola $B_r(x)$ de radio $r$ centrada en un vértice $x$, dada por el conjunto de todos los vértices conectados a $x$ por un camino de longitud a lo sumo $r$. La tasa de crecimiento del tamaño $|B_r(x)|$ como función de $r$ es una especie de "dimensión local" del grafo cerca de $x$. Esta idea se aplica comúnmente a los grafos de Cayley para describir la tasa de crecimiento de un grupo en teoría de grupos geométricos.

En $\mathbb{Z}^2$ las bolas crecen como $\Theta(r^2)$ (y más generalmente en $\mathbb{Z}^n$ crecen como $\Theta(r^n)$) pero en el árbol $4$-ario infinito las bolas crecen como $\Theta(3^r)$. Una forma de decir esto es que las caminatas aleatorias en el árbol infinito "se expanden" mucho más que las caminatas aleatorias en la cuadrícula infinita.

En términos de teoría de grupos, el primer grafo es el grafo de Cayley de $\mathbb{Z}^2$ y el segundo grafo es el grafo de Cayley del grupo libre $F_2$, y este cálculo de sus tasas de crecimiento muestra que no son cuasi-isométricos.