Czy tempo wzrostu grupy ogranicza liczbę krawędzi wychodzących z wierzchołka na wykresie Cayleya?

Question

Tempo wzrostu z grupy $B_n(G, T)$ opiera się na liczbie wierzchołków, do których można dotrzeć z danego $n$ przechodzi wzdłuż krawędzi na wykresie Cayleya grupy, gdzie $G$ to grupa (lub jej wykres) i $T$ jest zbiorem generatorów grupy lub odpowiednich krawędzi na wykresie.

Nauczyłem się tego tutaj$\mathbb{Z}^3$ ma tempo wzrostu rzędu $n^3$. Patrząc na wykresy (niekoniecznie Cayley), zastanawiam się, czy poniższe istnieją dla dowolnego, ale ustalonego$n_0\in\mathbb{N}$:

1. Wykres jest nieskończony.
2. Wykres jest symetryczny .
3. Tempo wzrostu jest w porządku $n^3$.
4. Każdy wierzchołek ma $m>=n_0$ krawędzie.

To istnieje dla $m=n_0=6$ na kafelkowanie przestrzeni trójwymiarowej z kostkami.

Pytanie: Czy następujący dowód na to, że mogę znaleźć plik$m$ dla każdego $n_0$poprawny? (Ryzykując pytanie tak / nie, jak w tym poście meta ).

Zdefiniuj wykres $G_1 = (V, E_1)$ takie że $V=\mathbb{Z}^3$. Wierzchołki można uznać za środki kostek na tym kafelku$\mathbb{R}^3$. Zdefiniuj krawędź wykresu dla każdych dwóch sześcianów, które „stykają się” bezpośrednio, na bokach, krawędziach lub rogach. Rozważmy kostkę Rubika, w której środkowy sześcian ma krawędź do wszystkich otaczających kostek. Bardziej formalnie, niech$v, w\in V$ być podłączony, tj $\{v, w\}\in E_1$, jeśli są „bezpośrednimi sąsiadami” wzdłuż dowolnej kombinacji współrzędnych, tj $v-w \in \{-1,0,1\}^3$ i $v\neq w$.

Piłka $B_n(G_1, v)\subset V$ będzie zbiorem węzłów dostępnych z $v$ przy minimalnej długości ścieżki wynoszącej $\leq n$. Dla$n=1$ to znowu jak patrzenie na kostkę Rubika i $|B_1(G_1, v)| = 3^3 = 27$. Ogólnie liczba elementów w piłce$B_n$ to coraz większe „Kostki Rubika”, aczkolwiek zawsze z nieparzystą liczbą kostek wzdłuż jednego wymiaru: $$|B_n(G_1, v)| = (1+2n)^3$$ Zatem tempo wzrostu jest rzędu $n^3$, ale nie mamy jeszcze dowolnie dużej liczby sąsiadów dla danego wierzchołka.

Teraz definiujemy wykres $G_k=(V,E_k)$ oparte na $G_1$ tak, że dodajemy krawędzie $E_1$ od $v$ do każdego wierzchołka $w\in B_k(G_1, v)\setminus E_1$, tak że teraz wszystkie wierzchołki tej kuli są bezpośrednimi sąsiadami $v$.

Na nowym wykresie mamy $$ |B_n(G_k, v)| = (1+kn)^3$$ co nadal jest stopniem wzrostu zamówienia $n^3$ale ponieważ mamy wolny wybór $k$, możemy stworzyć symetryczny wykres porządku $n^3$ gdzie każdy wierzchołek ma dowolnie wiele wychodzących krawędzi.

Specyficzne drapaki do głowy

1. Jest $|B_n(G_k, v)|$ poprawny?
2. Czy skonstruowany wykres $G_k$ naprawdę symetryczne?

Answer 1

Tak, to dobra konstrukcja. (Lub: nie, tempo wzrostu grupy nie ogranicza stopnia wierzchołków.) Uogólnienie tego: jeśli znajdziesz nieskończony graf$G$ który jest symetryczny, połączony i ma tempo wzrostu $|B_n(G,v)| = O(f(n))$, wtedy możemy pozwolić $G^k$ być wykresem z krawędzią $vw$ kiedy tylko $d(v,w) \le k$ w $G$. Możemy zrobić$G^k$ mają arbitralnie duży minimalny stopień i nadal je posiadają$ |B_n(G^k,v)| = O(f(n))$.

Możemy nawet znaleźć wykres Cayleya, który będzie miał pożądaną właściwość. Weź grupę$\mathbb Z^3 \times \mathbb Z_2^k$, i weź $T$ być zbiorem $3+k$generatory odpowiadające każdemu z czynników. Wtedy każdy wierzchołek wykresu Cayley będzie miał stopień$6+2k$, a tempo wzrostu będzie $O(n^3)$. (Chodzi o to, że później$n$ kroki, są $O(n^3)$ możliwości dla elementu $\mathbb Z^3$ mamy i co najwyżej $2^k = O(1)$ możliwości dla elementu $\mathbb Z_2^k$.)

Albo możemy nawet wziąć $\mathbb Z^3$, ale z innym, większym zespołem prądotwórczym. Tempo wzrostu będzie nadal$O(n^3)$, ponieważ jeśli żaden generator nie pozwala zmienić dowolnej współrzędnej o więcej niż $M$, następnie po $n$ kroki jesteśmy ograniczeni do sześcianu z $(2Mn+1)^3$wierzchołki w nim. Stopień każdego wierzchołka jest dwukrotnie większy niż liczba generatorów.