그룹 성장률이 Cayley 그래프에서 꼭짓점을 벗어나는 가장자리 수를 제한합니까?
그룹 의 성장률 $B_n(G, T)$ 주어진 하나에서 도달 할 수있는 정점의 수를 기반으로합니다. $n$ 그룹의 Cayley 그래프에서 가장자리를 따라 이동합니다. $G$ 그룹 (또는 해당 그래프)이고 $T$ 그룹의 생성기 세트 또는 그래프의 각 간선입니다.
내가 배운 여기에 그$\mathbb{Z}^3$ 성장률은 다음과 같습니다. $n^3$. 그래프 (반드시 Cayley는 아님)를 보면 다음이 임의적이지만 고정되어 있는지 궁금합니다.$n_0\in\mathbb{N}$:
- 그래프는 무한합니다.
- 그래프는 대칭 입니다.
- 성장률은 순서입니다 $n^3$.
- 각 정점에는 $m>=n_0$ 가장자리.
이것은 존재합니다 $m=n_0=6$ 큐브가있는 3 차원 공간의 타일링에 따라.
질문 : 내가 찾을 수있는 다음 증거는$m$ 어떠한 것도 $n_0$옳은? ( 이 메타 게시물에 따라 예 / 아니오 질문을 던집니다 .)
그래프 정의 $G_1 = (V, E_1)$ 그런 $V=\mathbb{Z}^3$. 정점은 타일링하는 큐브의 중심으로 간주 될 수 있습니다.$\mathbb{R}^3$. 측면, 모서리 또는 모서리에서 직접 "접촉"하는 각 두 큐브에 대해 그래프의 모서리를 정의합니다. 중앙 큐브가 모든 주변 큐브에 가장자리가있는 루빅스 큐브를 고려하십시오. 좀 더 공식적으로$v, w\in V$ 연결됨, 즉 $\{v, w\}\in E_1$, 좌표 조합을 따라 "직접 이웃"인 경우, 즉 $v-w \in \{-1,0,1\}^3$ 과 $v\neq w$.
공 $B_n(G_1, v)\subset V$ 도달 할 수있는 노드 집합이어야합니다. $v$ 최소 경로 길이 $\leq n$. 에 대한$n=1$ 이것은 다시 루빅스 큐브를 보는 것과 같습니다. $|B_1(G_1, v)| = 3^3 = 27$. 일반적으로 볼의 요소 수$B_n$ 항상 한 차원을 따라 홀수 개의 큐브가 있지만 더 큰 "루빅 큐브"입니다. $$|B_n(G_1, v)| = (1+2n)^3$$ 따라서 성장률은 $n^3$, 그러나 주어진 정점에 대해 임의의 많은 수의 이웃이 아직 없습니다.
이제 그래프를 정의합니다. $G_k=(V,E_k)$ 기반 $G_1$ 가장자리를 추가하도록 $E_1$ ...에서 $v$ 모든 정점에 $w\in B_k(G_1, v)\setminus E_1$, 이제 해당 공의 모든 정점이 $v$.
새 그래프에는 $$ |B_n(G_k, v)| = (1+kn)^3$$ 여전히 질서의 성장률입니다 $n^3$,하지만 우리는 자유롭게 선택할 수 있기 때문에 $k$, 우리는 순서의 대칭 그래프를 만들 수 있습니다 $n^3$ 각 정점에 임의의 많은 가장자리가 있습니다.
특정 헤드 스크래 처
- 이다 $|B_n(G_k, v)|$ 옳은?
- 생성 된 그래프 $G_k$ 정말 대칭인가요?
답변
예, 이것은 훌륭한 구조입니다. (또는 : 아니요, 그룹 성장률은 꼭지점의 정도를 제한하지 않습니다.) 이것의 일반화 : 무한 그래프를 찾은 경우$G$ 대칭적이고 연결되어 있으며 성장률이 $|B_n(G,v)| = O(f(n))$, 그러면 우리는 $G^k$ 모서리가있는 그래프 $vw$ 할때는 언제나 $d(v,w) \le k$ 에 $G$. 우리는 만들 수 있습니다$G^k$ 임의로 큰 최소 학위를 가지고 있으며 여전히$ |B_n(G^k,v)| = O(f(n))$.
원하는 속성을 가진 Cayley 그래프도 찾을 수 있습니다. 그룹 가져가$\mathbb Z^3 \times \mathbb Z_2^k$, 그리고 $T$ 세트로 $3+k$각 요인에 해당하는 발전기. 그러면 Cayley 그래프의 각 정점은$6+2k$, 성장률은 $O(n^3)$. (아이디어는$n$ 단계가 있습니다 $O(n^3)$ 요소에 대한 가능성 $\mathbb Z^3$ 우리는 가지고 있고, 기껏해야 $2^k = O(1)$ 요소에 대한 가능성 $\mathbb Z_2^k$.)
또는 우리는 $\mathbb Z^3$, 그러나 다른 더 큰 생성 세트가 있습니다. 성장률은 여전히$O(n^3)$, 생성기가 없으면 좌표를 $M$, 그러고 나서 $n$ 우리는 큐브로 제한되는 단계 $(2Mn+1)^3$그것의 정점. 각 정점의 차수는 생성기 수의 두 배입니다.