ランダム正則グラフの sandwich conjecture

理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home ランダム正則グラフ理論において有名な sandwich conjecture と呼ばれる予想があるのですが, 最近この予想に大きな進展[3,4]が見られたので紹介します. このトピックは私が修士の頃から論文を読んで追っていたトピックなので, 今回の進展をもたらした論文の登場は個人的にはかなり衝撃的でした. 1. ランダム正則グラフとErdős–Rényiグラフ 1.1. 定義$n$ 頂点 $d$-正則の頂点ラベル付きグラフ全体の集合から一様ランダムに取り出したグラフをランダム