有限有向グラフに対する一般荷重ゼータ函数の伊原表示 (代数的組合せ論と関連する群と代数の研究)

Abstract

"伊原表示"とは, グラフゼータ函数でのみ定義されている行列式表示であり, "今野-佐藤の定理"以来, 量子ウォークの性質の解析においても用いられている重要な表示である. これまでのグラフゼータ函数の大半は有限無向グラフに対して定義され, その伊原表示の導出が行われてきた. 主題にある"一般荷甫ゼータ函数"は, Morita [1]によって導入された有限有向グラフに対するグラフゼータ函数である. これはグラフゼータ函数の"指数表示", "オイラー表示", "橋本表示"の鼎立を議論するために, 既存のグラフゼータ函数を特別な場合にもつよう定義されている. 本稿では, 一般荷重ゼータ函数が伊原表示をもつかを問題とする. 有向グラフ上でグラフゼータ函数を定義するためには, "逆アーク"の定義を見直す必要がある. 無向グラフの場合は, 各辺e= {u, v}を2つの互いに他の逆向きのアークae=(u, v), ae-1=(v, u)に対応させた対称有向グラフに対して定義する. . したがって, 対称有向グラフの任意のアークaには, 対称有向化でペアとなった逆向きのアークa-1が唯一つ対応する. その逆向きのアークをaの逆アークと定義して扱っているのが従来のグラフゼータ函数である. しかし一般の有向グラフの場合, 必ずしも逆向きのアークが存在するとも限らない. さらには, 逆アークが一意に定まるとも限らない. 本稿では, 任意のアークaに対して逆向きのアークを全てaの逆アークと定義することで, その問題点を解消した. したがって, 逆向きのアークが存在しないアークには逆アークが存在しない. さらに, ループa=(u, u)に対する逆アークはaを含む頂点uに接続するループ全てとなる. 以上の設定に従って, 一般荷重ゼータ函数の伊原表示を導出した. グラフゼータ函数の研究の発端は, Ihara[2]により定義された2X2p-進特殊線形群のある離散群の共役類の数え上げに関するゼータ函数(伊原ゼータ函数)の研究である. Serreが伊原ゼータ函数は正則グラフに対するゼータ函数であることを指摘し, その後Sunadaは伊原ゼータ函数をグラフ理論的解釈により定義した. それを機に, Hashimoto[3], Bass [4], Bartholdi [5], Mizuno [6], Sato [7]をはじめとする多くの研究者により, 様々なグラフに付随するグラフゼータ涵数が定義・研究されてきた. 近年では, 量子ウォークとの関係についても研究されている. その切掛の一つが今野-佐藤の定理[8]である. これは"佐藤ゼータ函数"[7]が"グローヴァーウォーク”の遷移行列の特性多項式を与えることを述べている. また, 伊原表示は他の行列式表示よりも量子ウォークの性質を調べるのに適した表示であることも示した. グローヴァーウォークとはランダムウォークの量子化・非可換化である量子ウォークの代表的なモデルの一つである. 量子探索に用いられることもあり, 情報数学の分野をはじめとする多くの分野で広く研究されている. さらに, グローヴァーウォークはグラフの同型間題に関する予想[9]にも関与している. 今野-佐藤の定理はその予想の解決や, さらなるグラフ同16型問題の結果や予想にも寄与した. また, グローヴァーウォークが佐藤ゼータに対応することに甚づいて, 一般荷重ゼータ函数に対応しうる量子ウォークモデルの族を決定することに成功した[10]. その族にはグローヴァーウォークや新たな量子ウォークモデルも含まれている. 今後の研究では, 量子ウォークとグラフゼータ函数は互いに発展の一助となり合うだろう. 以降, 単に「ゼータ」と言えばグラフゼータ函数を指すこととする. なお, 本研究は森田英章(室蘭工大), 佐藤巖(小山高専)との共同研究[11]に基づく.