Condition de différenciation pour deux graphes infinis
Du carrelage de $\mathbb{R}^2$ avec des carrés, j'obtiens un graphe infini où chaque nœud a 4 voisins.
Je peux créer un arbre infini en attachant 4 nœuds à un nœud racine, puis continuer à attacher 3 nouveaux nœuds à chaque nœud. En conséquence, à nouveau, chaque nœud a 4 voisins, mais les graphiques sont nettement différents.
Dans les deux, (1) et (2) tous les nœuds et arêtes sont identiques, en ce sens que nous ne pouvons pas trouver une condition sur le graphe qui serait différente pour deux nœuds (ou arêtes).
Quelle est la bonne façon de décrire la différence entre ces deux graphiques? (1) semble plus "dense", comme si je découpais$n$nœuds, il a moins d'arêtes "dépassant". Pouvons-nous avoir, pour chaque degré$n$, des graphes «denses» qui remplissent (3)?
Réponses
Sur tout graphe localement fini (graphe où chaque sommet a un degré fini), vous pouvez considérer une boule $B_r(x)$ de rayon $r$ centré sur un sommet $x$, donné par l'ensemble de tous les sommets connectés à $x$ par un chemin de longueur au plus $r$. Le taux de croissance de la taille$|B_r(x)|$ en tant que fonction de $r$ est une sorte de "dimension locale" du graphe proche $x$. Cette idée est couramment appliquée aux graphiques de Cayley pour décrire le taux de croissance d'un groupe dans la théorie des groupes géométriques.
Sur $\mathbb{Z}^2$ les boules poussent comme $\Theta(r^2)$ (et plus généralement sur $\mathbb{Z}^n$ ils grandissent comme $\Theta(r^n)$) mais sur l'infini $4$-arbre, les boules poussent comme $\Theta(3^r)$. Une façon de dire ceci est que les marches aléatoires sur l'arbre infini "s'étalent" beaucoup plus que les marches aléatoires sur la grille infinie.
En termes de théorie des groupes, le premier graphe est le graphe de Cayley de $\mathbb{Z}^2$et le deuxième graphique est le graphique de Cayley du groupe libre $F_2$, et ce calcul de leurs taux de croissance montre qu'ils ne sont pas quasi-isométriques .
Le premier contient un cycle, mais pas le second.