Reciprocal research on graph asymmetry and expander graphs

点击翻译按钮获取中文摘要

前年度には, Ganguly-Srivastava (2019)によって示された内周の上界式を漸近的に達成する正則なエクスパンダーグラフをほとんどすべての次数に対して明示的に構成することに成功していた. その成果をまとめた論文が,国際一般誌Journal of the Ramanujan Mathematical Societyに本年度に採択された.次に, Ramanujanグラフの構成問題と暗号理論の専門家であるHyungrok Jo氏 (横浜国立大学, IAS 特任助教)と共同で, 弧推移的グラフのエクスパンダーとしての性質に着目し, グラフ上のウォークとして定義される新しい暗号学的ハッシュ関数を提案した. そのハッシュ関数としての性質は, グラフの内周や拡大定数に影響するため, 一般的に調べることが難しいエクスパンダーとしての性質を調べる上で重要となることがわかった. 特に, 弧推移的グラフであり内周の高いtripletグラフに着目し, その非2部性を証明したが, これによって, スペクトラルグラフ理論の結果とランダムウォークの混合性の議論を合わせることで, tripletグラフの拡大定数の評価が可能になると期待される. また, 小さな直径を持つというエクスパンダーとしての典型的な性質も観察できた. (2022年度のその後の研究で, 特定の頂点数の系列に対して, tripletグラフがエクスパンダーとなることも証明することができた.) 一方で, 内周の高さが予想されるsextetグラフにも着目し, 計算機実験をもとに内周の評価を継続中である. 以上の一部成果をまとめた論文は, 暗号理論の国内シンポジウムSCIS2022の論文集に掲載されている.