琉球大学理学部数理科学科

Department of Mathematical Sciences,
University of the Ryukyus

本講義では、グラフの隣接行列の固有値に着目するスペクトルグラフ理論の基礎から、 優れた連結性をもつラマヌジャングラフの概念と構成を学びます。前半では、スペクトルギャップ、 チーガーの不等式、Alon-Boppanaの定理を通して、固有値とグラフの構造の関係を解説します。 後半では、長年未解決であった「任意の次数のラマヌジャングラフの無限族の存在」を 二部グラフの場合に示したMarcus-Spielman-Srivastavaによる構成を取り上げ、2-lift、 マッチング多項式、interlacing familiesの考え方をたどりながら、その証明の核心をなるべく丁寧に紹介します。

非線形スペクトルギャップは、有限グラフと距離空間のペアに対して定義される量であり、幾何学的群論、距離空間の幾何学などの いくつかの文脈で現れ、重要な役割を果たすことが分かっている。その具体的な計算については分かっていないことが多いが、 一つの重要なアプローチである Wirtingerの不等式について述べ、研究の現状と可能性について概観する。