統計学輪講（第２８回）

日時      2010年11月16日(火)    15時～15時50分
場所      経済学部新棟３階第３教室
講演者    小川 光紀 (情報理工M1)
演題      グラフのグレイバー基底とそのランダムグラフへの応用

概要

トーリックイデアルは，計算代数の分野で重要な研究対象である．特に，無向グ
ラフから生起するトーリックイデアルは，その扱いやすさから，トーリックイデ
アルの構造を理解するためのよい対象として，盛んに研究されている[1]．
一方，統計におけるマルコフ連鎖モンテカルロ法に基づく正確検定では，既約な
マルコフ連鎖を構成する道具としてマルコフ基底が必要となる．しかし，一般に
マルコフ基底を求める問題は難しい．ところで，グレイバー基底と呼ばれるもの
はマルコフ基底を含んでいる．したがって，実用上はグレイバー基底を構成すれ
ばよい．
本発表ではまず，応用先として考えているランダムグラフの検定について触れる．
その上で，無向グラフから生起するトーリックイデアルについて確認し，そのグ
レイバー基底の元に対応するグラフ中の原始的閉路について既知の分類を紹介す
る．そして，今回行った再帰的構造に基づく原始的閉路のいくつかの特徴付けと，
それにより自然に導かれるグレイバー基底の抽出アルゴリズムについて説明する．

参考文献：
[1] H. Ohsugi and T. Hibi: Toric ideals generated by quadratic binomials.
Journal of Algebra, vol. 218 (1999), pp. 509--527.