m-反復準同型写像によるダイグラフ

この小節では V(B(d, n))の各頂点に対し，m-反復準同型写像によって写像された K_d^∗ 上 での値をもとに頂点集合を分割することを考える．和と差による準同型写像に対し，以下の 基本的な性質が成り立つ．

定理 5.2 V(B(d, n)) からV(K_d^∗)への (n−1)-反復準同型写像 ϕⁿ_a⁻¹, ϕⁿ_s⁻¹ に対し，

ϕⁿ_a⁻¹(x₀⊕dα, x₁, . . . , x_n−1) = α⊕d(ϕⁿ_a⁻¹(x₀, x₁, . . . , x_n−1)) (5.1) ϕⁿ_a⁻¹(x0, x1, . . . , xn−1 ⊕dα) = α⊕d(ϕⁿ_a⁻¹(x0, x1, . . . , xn−1)) (5.2) ϕⁿ_s⁻¹(x₀⊕dα, x₁, . . . , x_n−1) = α⊕d(ϕⁿ_s⁻¹(x₀, x₁, . . . , x_n−1)) (5.3) ϕⁿ_s⁻¹(x₀, x₁, . . . , x_n−1 ⊕dα) = α⊕d(ϕⁿ_s⁻¹(x₀, x₁, . . . , x_n−1)). (5.4) ただし，α は d−1 以下の任意の正整数である．

和および差による準同型写像において，先頭および末尾のアルファベットは他の桁の演算 に対し影響を与えないことから，定理 5.2は容易に得られる．この事実から，さらに次が得 られる．

定理 5.3 α̸=β であるような任意の α, β ∈Zd に対し，

ϕⁿ_a⁻¹(α, x₁, . . . , x_n−1) ̸= ϕⁿ_a⁻¹(β, x₁, . . . , x_n−1) (5.5) ϕⁿ⁻¹_a (x₀, . . . , x_n−2, α) ̸= ϕⁿ⁻¹_a (x₀, . . . , x_n−2, β) (5.6) ϕⁿ_s⁻¹(α, x₁, . . . , x_n−1) ̸= ϕⁿ_s⁻¹(β, x₁, . . . , x_n−1) (5.7) ϕⁿ_s⁻¹(x0, . . . , xn−2, α) ̸= ϕⁿ_s⁻¹(x0, . . . , xn−2, β). (5.8)

また，和による準同型写像と差による準同型写像が持つ異なる性質として，次が与えら れる．

定理 5.4 B(d, n)の任意の頂点v = (v₀, v₁, . . . , v_n−1)とおき，v⊕dα= (v_j⊕dα), 0≤j ≤n−1 と定義する．このとき，

{ϕⁿ_a⁻¹(v)̸=ϕⁿ_a⁻¹(v⊕dα) if n is odd, ϕⁿ_a⁻¹(v) = (ϕⁿ_a⁻¹(v⊕dα))⊕d2k, ^∃k if n is even,

(5.9) ϕⁿ_s⁻¹(v) =ϕⁿ_s⁻¹(v⊕dα). (5.10) V(B(d, n)) から V(K_d^∗) への (n−1)-反復準同型写像 ϕⁿ⁻¹_a , ϕⁿ⁻¹_s によって写像される頂 点の値によって B(d, n) の頂点を分割することを考える．頂点の分割集合を次のように定義 する．

P V_i ={v | v ∈B(d, n) and ϕⁿ_a⁻¹(v) =i}, (5.11) M Vi ={v | v ∈B(d, n) and ϕⁿ_s⁻¹(v) =i}, 0≤i≤d−1. (5.12) 上記の定義より，P Vi(M V_i) は ϕⁿ_a⁻¹ により K_d^∗ の頂点 i に写像される B(d, n) のすべて の頂点を含む．今，P V_i およびM V_i の頂点により誘導される部分ダイグラフについて，以 下が得られる．

定理 5.5 B(d, n) の頂点部分集合 P V_i によって誘導される部分ダイグラフを ⟨P V_i⟩ とおく．

このとき，⟨P V_i⟩ は有向サイクルの和集合である．

証明 P Vi が1正則ダイグラフであることを示す．B(d, n)上の頂点v = (v0, v1, . . . , vn−1)に 対し，ϕⁿ_a⁻¹ =i であると仮定する．このとき，定理5.3-(5.6)より，(v1, v₂, . . . , v_n−1, α)と表 される頂点はただ一つだけ P V_i に含まれている．したがって，⟨P V_i⟩ 上における v の出字 数は1となる．同様に，定理5.3-(5.5)より (β, v₀, v₁, . . . , v_n−2)と表される頂点はただ一つだ け P V_i に含まれており，v の入字数は1となる．以上より，⟨P V_i⟩ は1正則ダイグラフであ

り，有向サイクルの和集合である． 2

M V_i の誘導部分ダイグラフに対しても，定理5.3-(5.7)(5.8)から同様に有向サイクルの和 集合となる．

上記の定理により，各 P Vi, M Vi が有向サイクルの集合を誘導することがわかった．次に，

各誘導部分ダイグラフがどのような有向サイクルを含んでいるかについての考察を行う．

定理 5.6 M V_i をB(d, n)の頂点分割集合とおき，M V_i⁻ を B(d, n−1)の頂点分割集合とお く．このとき，

⟨M V0⟩ ∼= ∪

0≤i≤d−1

⟨M V_i⁻⟩

証明 B(d, n−1)の各誘導部分ダイグラフ⟨M V_i⁻⟩のラインダイグラフL(⟨M V_i⁻⟩)を考える．

このとき，⟨M V_i⁻⟩はそれぞれ有向サイクルの和集合であるから，⟨M V_i⁻⟩ ∼=L(⟨M V_i⁻⟩)とな る．今，L(⟨M V_i⁻⟩)の各頂点をB(d, n)上の頂点として対応させて考える．M V_i⁻上で隣接す る2頂点を u= (x₀, x₁, . . . , x_n−2), v = (x₁, . . . , x_n−2, x_n−1)とおくと，ϕⁿ_s⁻²(u) =ϕⁿ_s⁻²(v) = i である．これら2頂点の弧から得られる B(d, n) 上の頂点 w = (x₀, x₁. . . , x_n−2, x_n−1) に対 し，ϕs を再帰的に適用し B(d,1) で写像される値を見ていくと，

ϕs(w) = ((x0⊖dx1),(x1⊖dx2), . . . ,(xn−2⊖dxn−1))

ϕ²_s(w) = ((x₀ ⊖dx₁)⊖d(x₁⊖dx₂),(x₁⊖dx₂)⊖d(x₂⊖dx₃), . . . ,(x_n−3⊖dx_n−2)⊖d(x_n−2⊖dx_n−1)) ...

ϕⁿ_s⁻²(w) = (ϕⁿ_s⁻²(u), ϕⁿ_s⁻²(v))

ϕⁿ_s⁻¹(w) =ϕⁿ_s⁻²(u)⊖dϕⁿ_s⁻²(v) = i−i= 0,

となり，すべての i に対し L(⟨M V_i⁻⟩) に含まれる頂点は ϕⁿ_s⁻¹(w) によって B(d,1) ∼= K_d^∗ の頂点0に写される．次に，B(d, n) のこれらの頂点以外が ϕⁿ_s⁻¹ により B(d,1) の頂点0 に写像されないことを示す．今，上記によって与えられた，頂点0に写像される B(d, n)の 頂点の総数は ⊕

0≤i≤d−1|L(⟨M V_i⁻⟩)| = d×dⁿ⁻² = dⁿ⁻¹ である．定理2.1により，ϕs は頂 点一様な準同型写像であり，この反復準同型写像も頂点一様である．したがって，B(d, n) に (n−1)-反復準同型写像 ϕⁿ_s⁻¹ を適用することで写像される B(d,1) の各頂点の負荷はそ れぞれ dⁿ⁻¹ となる．これは上記の頂点の総数と等しいため，これらの頂点以外が頂点0に 写像されることがないといえる．以上から，∪

0≤i≤d−1L(⟨M V_i⟩)⁻ は ⟨M V₀⟩ と同型であり，

∪

0≤i≤d−1⟨M V_i⁻⟩ ∼=⟨M V₀⟩を導く． 2

和の準同型写像に対して次の考察が得られる．

定理 5.7 d を奇整数とし B(d, n) の和による準同型写像を ϕ_a とおく．このとき，任意の i, j ∈Zd に対し，

⟨P M_i⟩ ∼=⟨P M_j⟩.

証明 定理5.4-(5.9)式により，B(d, n) の頂点 x= (x₀, x₁, . . . , x_n−1) に対し，x⊕dα, (0 ≤ α≤n−1)は ϕⁿ_a⁻¹ によりそれぞれ B(d,1)の異なる頂点へ写像される．今，P Vi のすべて の頂点 xに対し，x⊕dj となるような頂点集合 V_j を考える．x⊕dj に ϕⁿ⁻¹_a を作用させる と，得られる値は i⊕dj·2ⁿ となる．仮定より，d は奇であるから，これらの値はそれぞれ 異なる Zd 内の値となる．したがって，Vj のすべての頂点は B(d,1)の頂点 i⊕dj ·2ⁿ へと 写像され，その誘導部分ダイグラフは ⟨P Mi⟩ と同型である． 2

図 5.1に B(3,3) の和による準同型写像から構成された誘導部分ダイグラフを表す．

000

011 201 121

110 102 022

121

212

111

001 100 210

012 122 221

020

202

222

002 200 120

021 211 112

010

101

図 5.1: B(3,3)の和による準同型写像から構成された誘導部分ダイグラフ