修士論文 要旨

群作用を通じた符号グラフ準同型の解析
数理情報学専攻 48206228
指導教員

1 はじめにグラフに対して値を返す関数をグラフパラメータという．その中でグラフ準同型関数と呼ばれるクラスは彩色多項式などの重要な例を含み，極値グラフ理論では特にグラフの列の極限を定式化するのに有用である．
グラフ準同型関数はあるグラフへのグラフ準同型の個

長谷川雄祐
谷川眞一 准教授

さらに，符号付きグラフと符号グラフの準同型は次のように定義される．

b = (G, σ), Hb = (H, τ ) を符号付きグラフと定義 3. G
するとき，φV : V (G) → V (H) と φE : E(G) → E(H)の組 φ = (φV , φE ) が符号付きグラフ準同型であるとは，グラフ準同型でありかつ，符号を保つすなわち

σ = τ ◦ φE数として表される．ただし，グラフ準同型は次のように隣接関係を保つグラフ間の写像として定義される．

b [H]b を符号グラフとするであることをいう．また，[G],定義 1. G, H を無向グラフとする．φV : V (G) →とき，φV : V (G) → V (H) と φE : E(G) → E(H) のV (H) と φE : E(G) → E(H) の組 φ = (φV , φE ) が組 φ = (φV , φE ) が符号グラフ準同型であるとは，代グラフ準同型であるとは，任意の e ∈ E(G) について，b (H, τ ) ∈ [H]b が存在して (G, σ) から表元 (G, σ) ∈ [G],e の端点を u, v とすると φE (e) の端点が φV (u), φV (v)(H, τ ) への符号付きグラフ準同型となることをいう．となるときをいう．
他方，符号グラフは正負の辺ラベルが付いたグラフをスイッチング同値という同値関係で割って得られ，社会ネットワークを中心に研究されている概念である．先行研究では符号グラフに対するグラフ準同型が定義され，その存在条件が興味の対象になっている．本研究ではさらに進んで符号グラフに対する符号グラフ準同型

このように定義した準同型の個数について関係式を示した．

b [H]b を符号グラフとし，(H, τ ) ∈ [H]b であ定理 4. [G],るとする．次が成り立つ．

b [H])
b =hom([G],∑hom((G, σ), (H, τ ))b(G,σ)∈[G]

関数を定義し，通常のグラフ準同型関数の代表的特性でただし，左辺は符号グラフ間の準同型の個数を表し，右ある特徴付けと同型性判定が同様に成り立つことを示

辺の各項は符号付きグラフ間の準同型の個数を表す．

した．

2 符号付きグラフから符号グラフへ
符号付きグラフとはグラフ G と写像 σ : E(G) →b = (G, σ) のことである．符号付きグラ{+, −} の組 G
フの頂点に関するスイッチングと呼ばれる操作を考え，符号グラフは台グラフがもつ部分サイクルの符号により特徴付けられることが知られている [4]．したがって，辺の縮約などの局所的変形により大きく状況が変化するため扱いが難しい．これは，準同型関数の理論の拡張がすでに行われているハイパーグラフや重み付きグラフとは事情が異なる点である．

スイッチングで移り合うものを同一視した符号付きグラフ同値類が符号グラフである．

3 符号グラフと Z2 -対称グラフ

b = (G, σ) の u ∈ V (G) に関
定義 2. 符号付きグラフ Gグラフ S に Z2 が作用しており頂点集合への作用はするスイッチングとは，u を端点とする辺のうち自己辺自由であるとき，台グラフ S とその作用 ρ の組 (S, ρ)でないもの全ての符号を反転させた符号付きグラフをを Z2 -対称グラフという．ただし，グラフに群が作用す得ることである．有限回のスイッチングで移り合うとるとは頂点集合と辺集合それぞれへの作用が隣接関係いう同値関係により符号付きグラフ全体を割って得らと整合的であるときをいう．このとき，符号グラフとb とスイッチング同値れる同値類を符号グラフといい，GZ2 -対称グラフは 1 対 1 に対応することが簡単な観察かb とな符号付きグラフを集めてできる符号グラフを [G]らわかる．さらに，Z2 -対称グラフ間の準同型を台グラ書く．

フ間のグラフ準同型であって作用と可換であるものとすることにより個数についての関係式を得た．

群作用を通じた符号グラフ準同型の解析 (長谷川雄祐)

b [H]b に対応する Z2 -対称グラフ
定理 5. 符号グラフ [G],をそれぞれ (S, ρ), (T, λ) とする．次が成り立つ．

b [H])
b = hom((S, ρ), (T, λ))2c(G) hom([G],ただし，c(G) は連結成分の個数を表し，右辺は Z2 -対称グラフ間の準同型の個数を表す．

M (g, k) とは，各行各列を k-ラベル付き符号グラb α) かつ行 ([H],b β) でフにより添字づけし，列 ([G],b α) ∗ ([H],b β)) とした無限次行列ある成分を f (([G],をいう．また，無限次行列が正定値であるとは任意の主小行列が正定値であることとする．
続いて，符号グラフ準同型の個数の一致から符号グラ

この変換から，Z2 -対称グラフにおいて定まる準同型フの同型性判定が行えることを示した．この証明では，関数の特徴付けと同型性判定を示せば符号グラフにも通常のグラフに対する証明をラベル付けの意味で解釈同様の結果が与えられることがわかる．

し直すことで，Z2 -対称グラフに対するラベル付けの議

4 特徴付け及び同型性判定
通常のグラフ準同型関数と同様の特徴付けを得るた
めにはラベル付けの定式化が要請されるので，軌道グラフという概念を定義することで Z2 の対称性が加味されるように Z2 -対称グラフのラベル付けと糊付け積を定式化した．

論を適用した．具体的には，頂点集合の分割によるグラフの縮約を，辺のないラベル付きグラフとの糊付け積とみなした．

c1 ], [Hc2 ] を 符 号 グ ラ フ と す る ．|V (G)| ≤定 理 8. [Hmax{|V (H1 )|, |V (H2 )|} であるような任意の符号グラb についてフ [G]b [Hc1 ]) = hom([G],b [Hc2 ])hom([G],定義 6. Z2 -対称グラフ (S, ρ) について，軌道グラフ

Orb(S, ρ) とは V (Orb(S, ρ)) = V (S) であって同じ軌

c1 ] ∼c2 ]．となるならば，[H= [H

道に属する相異なる 2 頂点間を辺で結んだ単純グラフ

b に対応する Z2 -対称グラフがをいう．符号グラフ [G]b と準同型 α : K k → Orb(S, ρ) の(S, ρ) であるとき，[G]2組を k-ラベル付き符号グラフという．ただし，K2k は k個の K2 の非交叉和である．そこから，2 つの k-ラベルb α), ([H],b β) の糊付け積を次のよ付き符号グラフ ([G],うに定める．すなわち，それぞれに対応する Z2 -対称グラフの非交叉和をとり，各 u ∈ K2k について α(u), β(u)を同一視して得られる k-ラベル付き符号グラフを糊付b β) と書く．
b α) ∗ ([H],け積とする．また，これを ([G],以上から，符号グラフ準同型関数の特徴付けが記述される．ただし，証明には Lovász[2] による圏論的拡張を用いた．
定理 7. 符号グラフパラメータ f が符号グラフ準同型でb を用いて f = f bある，すなわちある符号グラフ [H][H]と表されるための必要十分条件は以下の (i) と (ii) が成立することである．

(i) f が乗法的である．すなわち，任意の符号グラフc1 ], [Gc2 ] について
[Gc1 ] ⊔ [Gc2 ]) = f ([Gc1 ])f ([Gc2 ])f ([Gb = 2c(G) f ([G])
b とおくと，任意の正整数 k に(ii) g([G])
対して関係行列 M (g, k) が正定値となる．ただし，5 まとめ
符号グラフ準同型関数の特徴付けと識別が通常のグラフと同様に成り立つことを示し，符号グラフにおける準同型関数の理論の基礎を整備した．符号グラフ準同型関数に望まれる他の性質も Z2 -対称グラフのラベル付けの議論を適用できる可能性がある．また，ゲイングラ
フをはじめとして一般の群対称性をもつグラフへの拡張も考えられる．今後の課題として，符号グラフの列の極限を考えたときの収束先となる符号グラフォンを定式化することが挙げられる．

参考文献[1] M. Freedman, L. Lovász, and A. Schrijver. Reflection
positivity, rank connectivity, and homomorphism ofgraphs. Journal of the American Mathematical Society, 20(1):37–51, 2007.
[2] L. Lovász and A. Schrijver. Semidefinite functions oncategories. The Electronic Journal of Combinatorics,
16(2):R14, 2009.
[3] L. Lovász. Large networks and graph limits, Volume60. American Mathematical Society, 2012.
[4] R. Naserasr, E. Sopena, and T. Zaslavsky. Homomorphisms of signed graphs: An update. European
Journal of Combinatorics, 91:Article 103222, 2021.