エクスパンダーグラフにまつわる数理科学と応用
| 整理番号 | 2025a037 |
|---|---|
| 種別 | 若手・学生研究-短期共同研究 |
| 研究計画題目 | エクスパンダーグラフにまつわる数理科学と応用 |
| 研究代表者 | 佐竹 翔平（熊本大学 半導体・デジタル研究教育機構 総合情報学部門・准教授） |
| 研究実施期間 |
2025年8月25日(月) ～
2025年8月29日(金) |
| 研究分野のキーワード | エクスパンダー、情報科学、数理科学、産学研究 |
| 本研究で得られた成果の概要 |
有限体上のMarkoff方程式に基づくグラフ、いわゆるMarkoff mod p graphのエクスパンダー性に関する共同研究を継続的に進めた。Markoff方程式は3変数のDiophantine方程式であり、Markoffの古典的結果により、非負有理整数解全体はMarkoff moveによって連結な3正則木（Markoff tree）を成すことが知られている。一方、有限素体上で同様の構成を行うと3正則有限無向グラフ（Markoffグラフ）が得られる。Bourgain–Gamburd–SarnakによりMarkoffグラフがエクスパンダーであるとの予想が提示されているが、現時点では十分大きな素数に対する連結性の証明にとどまっており、エクスパンダー性の本質的解明には至っていない。MarkoffグラフはCayleyグラフやSchreierグラフのような有限群に基づく構成ではないため、従来手法が適用できず、新たな解析的・組合せ論的手法の開発が不可欠である。 本共同研究では、昨年度までの成果を拡張し、Markoffグラフおよび一般化Markoffグラフの内部構造を詳細に解析した。その結果、巨大連結成分内に複数の完全2部グラフマイナーが存在することを証明し、低種数閉曲面への埋め込み不可能性や非apex性を導いた。これらはエクスパンダー性を示唆する重要な傍証であり、一般化Markoffグラフに関する近年の研究進展とも整合的である。得られた成果は現在論文として取りまとめており、国際学術誌への投稿を予定している。 さらに産業界への貢献に向けて、暗号理論的な研究も進めてきた。Markoffグラフを用いた暗号学的ハッシュ関数が既に提案されているものの、その安全性評価や数理的基盤は十分に確立されていなかった。本共同研究では、一般化Markoffグラフの巨大連結成分内におけるサイクルの存在性と分布に注目し、特定の短サイクルの構成法や具体的位置を明らかにした。これらの成果は、ハッシュ関数の安全性解析や耐量子計算機暗号への応用に資するものであり、SCIS2026において発表予定である。 |
| 組織委員(研究集会) 参加者(短期共同利用) |
相川 勇輔（東京大学 大学院情報理工学系研究科・助教） 池松 泰彦（九州大学IMI・准教授） Cid Reyes Bustos（NTT基礎数学研究センタ・研究主任） 清水 伸高（東京科学大学 工学院・助教） Hyungrok Jo（横浜国立大学 先端科学高等研究院・特任助教） 見村 万佐人（東北大学 大学院理学研究科・准教授） 佐竹 翔平（熊本大学 半導体・デジタル研究教育機構・准教授） |