- Date: 19 Jun. (Thu.)
- Place: West Wing, 6th floor, Colloquium Room and on the Web (zoom)
- Time: 16:50-19:00
- Speaker 1: Hoang Vu (UC santa barbara)
- Time: 16:50-17:50
- Title: Combinatorial Optimization Via Quantum Walks
- Abstract:
Combinatorial optimization is a crucial area of research focused on finding optimal solutions from a finite set of discrete options. The landscape of this field has evolved significantly in recent years, driven by the increasing complexity of problems and the demand for efficient algorithmic solutions with applications spanning logistics, transportation, finance, and beyond. A transformative shift in combinatorial optimization has arisen with the introduction of quantum computing methodologies. We will review recent quantum algorithms and introduce some new ideas on using quantum walks to solving the combinatorial optimization problem.
- Speaker 2: 佐竹 翔平 (熊本大学)
- Time: 18:00-19:00
- Title: On the embeddability of the Markoff mod $p$ graph
- Abstract:
“素数$p>3$に対し, Markoff mod $p$ graph $G_p$は位数$p$の有限体上のMarkoff方程式の非自明な解の集合上で定義される有限3-正則グラフである.
Bourgain-Gamburd-Sarnak (2016) によって$G_p$はエクスパンダー族をなすことが予想されており (BGS予想), 現在も未解決である.
一方で, BGS予想の傍証に関してはいくつかの結果が知られており, Courcy Ireland (2023) は $p=7$の場合を除いて, $G_p$が平面グラフではないことを証明した.
実際, 平面グラフはLipton-Tarjan (1971) のセパレーター定理よりエクスパンダー族をなしえないことから, 非平面性はエクスパンダー性の一つの必要条件でもある.
本発表では, $G_p$内の完全2部グラフ$K_{3,3}$の細分を具体的に複数構成することで, $p=7$の場合を除いて, $G_p$が射影平面にもトーラスにも埋め込み不可能であることを示す.
この結果はCourcy Ireland (2023) の結果の拡張となっており, 有界種数をもつグラフに関するセパレーター定理から, やはりBGS予想の傍証を与えている.
時間が許せば, 一般化したMarkoff mod $p$ graphに関する結果も紹介する.
本発表は山﨑 義徳 氏 (愛媛大学) との共同研究に基づく.”
日本語
English