組合せ数学セミナー
発表内容の概要

5/31(金): 佐藤巌（小山工業高等専門学校）
伊原ゼータ関数とその一般化

先ず、グラフの伊原ゼータ関数の定義と行列式表示を述べる。次に、伊原ゼータ関数の
一般化の一つであるweightedゼータ関数について、定義とそれらの行列式表示を与える。
その応用として、離散時間量子ウォークの一つであるGrover walkの時間発展行列(Grover行列)に
関する今野-佐藤の定理を与える。また、今野-佐藤の定理の応用として、Grover/Zeta対応について
述べる。最後に、伊原ゼータ関数の別の一般化であるalternatingゼータ関数を
定式化して、その行列式表示を用いて、Alternating Walk/Zeta対応について触れる。

7/19(金): 権英哲（東京大学）
証明の長さと、量的なモデル理論

数理論理学における古典的結果である（各種論理・形式系の）健全性定理・完全性
定理により、様々な設定のもとで、「命題Aの数学的証明の非存在」と、「Aが破れ
ているモデルの存在」とは同値である。これは、組み合わせ論的対象である「証明」
と、代数的対象である「モデル」とを結び付けており、興味深い。では、「命題Aの
長さn以下の証明が存在しない」ことを言うには、どんな対象の「存在」を言えば
よいだろうか？
  本講演では、数理論理学の一分野、Proof Complexityにおける重要な考察対象であ
るresolution, Nullstellensatz proof system, Frege systemについて、この観点
から紹介を行い、応用として、（命題論理における）鳩の巣原理の証明の長さにつ
いての知見を概観する。
  また、この中でも特にゲームの概念を用いた論法により、（数理論理学内の別分野
である）順序数解析の古典的結果が再解釈できることについても触れたい。

（講演スライド）