Le taux de croissance du groupe limite-t-il le nombre d'arêtes sortant d'un sommet dans son graphe de Cayley?

Question

Le taux de croissance d'un groupe $B_n(G, T)$ est basé sur le nombre de sommets qui peuvent être atteints à partir d'un point donné par $n$ marches le long d'une arête dans le graphique de Cayley du groupe, où $G$ est le groupe (ou son graphique) et $T$ est un ensemble de générateurs du groupe ou des arêtes respectives du graphe.

J'ai appris ici que$\mathbb{Z}^3$ a un taux de croissance de l'ordre de $n^3$. En regardant les graphiques (pas forcément Cayley), je me demande si ce qui suit existe pour un arbitraire mais fixe$n_0\in\mathbb{N}$:

1. Le graphique est infini.
2. Le graphique est symétrique .
3. Le taux de croissance est d'ordre $n^3$.
4. Chaque sommet a $m>=n_0$ bords.

Cela existe pour $m=n_0=6$ par le carrelage d'un espace tridimensionnel avec des cubes.

Question: Est-ce que la preuve suivante que je peux trouver un$m$ pour toute $n_0$correct? (Risquer une question oui / non selon ce méta-post .)

Définir un graphique $G_1 = (V, E_1)$ tel que $V=\mathbb{Z}^3$. Les sommets peuvent être considérés comme des centres de cubes qui tuiles$\mathbb{R}^3$. Définissez un bord du graphique pour chaque deux cubes qui "touchent" directement, soit sur les côtés, les bords ou les coins. Considérez un Rubik's Cube, où le cube central a une arête sur tous les cubes environnants. Plus formellement, laissez$v, w\in V$ être connecté, c'est à dire $\{v, w\}\in E_1$, s’ils sont "voisins directs" le long de toute combinaison de coordonnées $v-w \in \{-1,0,1\}^3$ et $v\neq w$.

Le ballon $B_n(G_1, v)\subset V$ doit être l'ensemble des nœuds accessibles depuis $v$ avec une longueur de chemin minimale de $\leq n$. Pour$n=1$ c'est encore comme regarder Rubik's Cube et $|B_1(G_1, v)| = 3^3 = 27$. En général, le nombre d'éléments dans le ballon$B_n$ est un "Rubik's Cubes" toujours plus grand mais toujours avec un nombre impair de cubes dans une dimension: $$|B_n(G_1, v)| = (1+2n)^3$$ Le taux de croissance est donc de l'ordre de $n^3$, mais nous n'avons pas encore un grand nombre arbitraire de voisins pour un sommet donné.

Maintenant, nous définissons le graphique $G_k=(V,E_k)$ basé sur $G_1$ de sorte que nous ajoutions des arêtes à $E_1$ de $v$ à chaque sommet $w\in B_k(G_1, v)\setminus E_1$, de sorte que maintenant tous les sommets de cette boule sont des voisins directs de $v$.

Dans le nouveau graphique, nous avons $$ |B_n(G_k, v)| = (1+kn)^3$$ qui est encore un taux de croissance de l'ordre $n^3$, mais puisque nous sommes libres de choisir $k$, on peut créer un graphe symétrique d'ordre $n^3$ où chaque sommet a de nombreux arêtes en sortie.

Grattoirs spécifiques

1. Est $|B_n(G_k, v)|$ correct?
2. Le graphe construit est-il $G_k$ vraiment symétrique?

Answer 1

Oui, c'est une belle construction. (Ou: non, le taux de croissance du groupe ne limite pas le degré de sommets.) Une généralisation de ceci: si vous trouvez un graphe infini$G$ qui est symétrique, connectée et a un taux de croissance $|B_n(G,v)| = O(f(n))$, alors nous pouvons laisser $G^k$ être le graphe avec une arête $vw$ n'importe quand $d(v,w) \le k$ dans $G$. Nous pouvons faire$G^k$ ont un diplôme minimum arbitrairement élevé et ont toujours$ |B_n(G^k,v)| = O(f(n))$.

Nous pouvons même trouver un graphe Cayley qui aura la propriété que vous souhaitez. Emmenez le groupe$\mathbb Z^3 \times \mathbb Z_2^k$, et prend $T$ être un ensemble de $3+k$générateurs correspondant à chacun des facteurs. Ensuite, chaque sommet du graphe de Cayley aura un degré$6+2k$, et le taux de croissance sera $O(n^3)$. (L'idée est qu'après$n$ étapes, il y a $O(n^3)$ possibilités pour l'élément de $\mathbb Z^3$ nous avons, et au plus $2^k = O(1)$ possibilités pour l'élément de $\mathbb Z_2^k$.)

Ou, nous pourrions même prendre $\mathbb Z^3$, mais avec un groupe électrogène différent et plus grand. Le taux de croissance sera toujours$O(n^3)$, car si aucun générateur ne vous permet de modifier une coordonnée de plus de $M$, puis après $n$ étapes nous sommes limités à un cube avec $(2Mn+1)^3$sommets dedans. Le degré de chaque sommet est le double du nombre de générateurs.