埋め込みクリーク問題

与えられたグラフ$G=(V,E)$に含まれる最大クリークを求めよという問題はKarp's 21 Complete Problemの一つであり, おそらく最も有名なNP困難な問題の一つとして知られています. 本記事ではこの問題の平均時困難性について考えます. すなわち, 与えられたグラフがErdos-Renyiランダムグラフ$G(n,1/2)$のときの最大クリーク(を見つける問題)について紹介し, 関連問題として埋め込みクリーク問題を紹介します.

ランダムグラフ上の最大クリーク問題

Erdős--Rényiグラフ$G(n,1/2)$を考えます. このグラフは$n$個の頂点からなり, 各頂点のペアは独立に確率$1/2$で辺を持ちます. 言い換えれば, $n$頂点の頂点ラベル付きグラフの中から一様ランダムに選ばれたグラフが$G(n,1/2)$です. このように, 入力がランダムに生成された時に問題が効率的に解けるかどうかを議論する枠組みを平均時計算量といいます.

最大クリーク問題に戻りましょう. Erdős--Rényiグラフ$G(n,1/2)$は高確率でおよそサイズ$2\log_2 n$のクリークを持つことが示せます. ここでは厳密な証明はしませんが, なぜ$2\log_2 n$という値が出るかについて, $k$-クリークの個数の期待値を使って簡単に説明します. グラフ$G(n,1/2)$に含まれる$k$-クリークの個数を$X_k$とします. $X_k>0$ならば最大クリークのサイズは$k$以上であり, $X_k=0$ならば$k$未満となります. 頂点部分集合$S\subseteq[n]$に対し, $S$がクリークであるかどうかのindicatorを$X_S$とします. すなわち$S$が$G(n,1/2)$内でクリークになっているならば$X_S=1$, そうでなければ$X_S=0$です. 固定した$S$に対して$X_S=1$となる確率は$(1/2)^{\binom{|S|}{2}}$です. さて, $X_k = \sum_{S\subseteq[n],|S|=k} X_S$ と書けます. 期待値の線形性より, $X_k$の期待値は
$$\begin{align*} \mathbb{E}[X_k] &= \sum_{S\subseteq[n],|S|=k} \Pr[X_S=1] \\ &= \binom{n}{k}\cdot 2^{-\binom{k}{2}} \\ &\approx \frac{n^k}{k!} 2^{-k^2/2} \\ &\approx 2^{-k\log_2 n - k^2/2} \\ &\approx 2^{-k(\log_2 n - k/2)} \end{align*}$$
となります. 途中で突然$k!$が消えたのは, $k!=2^{(1-o(1))\cdot k\log k}$は$2^{-\binom{k}{2}}$に比べて無視できるほど小さいからです. $k\gg \log_2 n$ならば指数部が負となり$X_k$の期待値は非常に$0$に近い値となります. $k\ll \log_2 n$ならば期待値は非常に大きい値となるので, $G(n,1/2)$は$k$-クリークを含むだろうことがわかります. 前半の議論(非存在性)はMarkovの不等式, 後半の議論(存在性)はChebyshevの不等式を使うと厳密な議論にできます. 詳しく知りたい方はこちらの記事を参照してください.

すなわち, 入力が$G(n,1/2)$だと最大クリークのサイズはおよそ$2\log_2 n$であることがわかります. では, この$2\log_2 n$-クリークを見つけられるでしょうか?

成功確率の枠組み

そもそも「ランダムグラフ上で問題を解く」とはどういうことなのでしょうか?

最悪時計算量の枠組みでは, 「全ての入力に対して正しい答えを出力する」効率的なアルゴリズムの構成が焦点になっていました. 一方で平均時計算量では「全ての入力に対して」という部分を「多くの入力に対して」に緩和した枠組みを考えます. 本当はerrorless/error-proneの二つの概念があるのですが, ここではerror-proneの枠組みを考えます.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, 成功確率$\gamma$で$G(n,1/2)$上で最大クリークを解くという:
$$\begin{align*} \Pr_{G \sim G(n,1/2)} [ A(G) \text{ outputs a maximum clique in }G]\ge \gamma. \end{align*}$$

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

直感的に言えば成功確率とはアルゴリズム$A$が解く(固定サイズの)入力の割合を意味します. 平均時計算量の理論では, 効率的(例えば多項式時間)なアルゴリズムの中で最大の成功確率$\gamma$をもつものが研究の対象となります.

入力によって解けるか解けないかが決まるので, 乱択アルゴリズムのように
「繰り返して成功確率を増幅させる」ことはできない.

例えば, 成功確率$\gamma=1$のアルゴリズムは最悪時の意味において最大クリーク問題を解くことを意味します. これはNP困難なので, $\gamma=1$を満たす多項式時間アルゴリズムは存在しないと広く信じられています. 従って$\gamma<1$の範囲で考えます. この記事では確率$1-o(1)$を「高確率」と呼ぶことにします(注1).

(注1). 「高確率」という言葉は専門用語として扱われることが多いです. ランダムグラフの文脈では漸近的に確率$1$で成り立つことを「a.a.s. (asymptotically almost surely)」「w.h.p. (with high probability)」と言うことがあります. また, 乱択アルゴリズムの文脈では, 何らかの定数$c>0$が存在して確率$1-n^{-c}$で成り立つことを「高確率」ということもあります.

上の定義では誤った答えを出力しうるものの常に多項式時間で終了するアルゴリズムを考えていました. このようにアルゴリズムの「誤りうる」という性質をerror-proneと言います. 一方で, 常に正しい答えを出力するが入力によっては指数時間かかりうるという性質をerrorlessといいます. 乱択アルゴリズムの文脈で例えるとラスヴェガス法か, モンテカルロ法かという話です. 

最悪時と平均時のギャップ

さて, $G(n,1/2)$上での最大クリーク問題に話を戻しましょう. 証明はしませんが, $G(n,1/2)$は確率$1-n^{-\Omega(\log n)}$で最大クリークのサイズが高々$2.01\log_2 n$であることが証明できます. 従って, サイズ$2.01\log_2 n$以下の頂点部分集合$S \subseteq [n]$ を全て列挙し, クリークをなした$S$の中で最大のものを出力すると, $n^{O(\log n)}$時間で成功確率$1-n^{-\Omega(\log n)}$で$G(n,1/2)$上で最大クリークを解けます.

最悪時の世界では最大クリーク問題はETH(強指数時間仮説)の下では$2^{\Omega(n)}$時間かかると予想されていますが, 平均時の世界では単純なbrute-forceを考えれば$n^{O(\log n)}$時間で高確率で解くことができます.

貪欲法

最大クリーク問題に対する最も単純なアプローチが貪欲法です. 何でも良いので極大クリークを一つ選び, 出力するというアルゴリズムです. 例えばクリークに追加できる頂点のうち, インデックスが一番若い頂点を選んで追加するというルールを考えてみましょう.

定理 (Karp, 1976, informal).

入力$G(n,1/2)$上の貪欲法で得られる極大クリークを$S$とすると, 確率$1-o(1)$で$|S| = (1\pm o(1))\log_2 n$を満たす.

すなわち, 貪欲法は"ほぼ2近似"アルゴリズムであるといえます. 最悪時の世界では, 任意の小さな定数$c>0$に対して最大クリークを多項式時間で$n^{1-c}$近似するのはNP困難であることが知られているので, この定理もまた最悪時と平均時の世界のギャップを意味します.

証明(の概要).
貪欲法の$t$回目の反復で得られる頂点部分集合を$S_t$とします. すなわち, $S_0=\emptyset$であり, $S_{t+1}$は$S_t\cup \{u\}$がクリークになるような頂点$u$のうち最もインデックスが若いものとします (例えば一番最初に追加される頂点は必然的に最もインデックスの若い$v_1$になります). $S_t$の要素数は$t$なので, 貪欲法が終了したときのステップ数$t$の上下界を求めればよいことになります.

この「若い頂点を優先する」貪欲法は, 頂点を$v_1,\dots,v_n$の順に見ていき初めて追加できる頂点を見つけたらそれを追加するというように実装することができます. この実装では, 例えば時刻$t$で頂点$v_i$が追加されたとすると, その反復までにアルゴリズムは以降の頂点$v_{i+1},\dots,v_n$を見ていないことになります (もちろんこれは実装依存ですが, $v_{i+1},\dots,v_n$を見ないように実装したものと同じ出力を得るので, 見ていないということを仮定できます). すなわち, この反復までの挙動は誘導部分グラフ$G[\{v_1,\dots,v_i\}]$にのみ依存するのであって, $v_{i+1},\dots,v_n$に接続する辺の情報とは独立です. ですので, 頂点$v_{i+1}$を見たとき, その時初めて辺$\{v_{i+1},v_j\}$ ($j=1,\dots,n\}$) に関する入力の情報をサンプルする (つまり, 入力を生成→アルゴリズムの解析, ではなく, アルゴリズムの反復に応じて入力を徐々に生成していく) という確率過程によってアルゴリズムの振る舞いを解析ができます.

時刻$t$における反復において$S_t$の要素数は$t$であり, $S_t$の全ての頂点と隣接している頂点が新たに$S_{t+1}$に加わるわけですが, 固定した頂点$v_j$が追加される確率は$(1/2)^t$です. 従って, 任意の定数$c>0$に対し$t\ge (1+c)\log_2 n$ならば, $v_j \in [n]$に関するunion boundより一つも頂点が追加されないので, $t \le (1+c)\log_2 n$を得ます. 逆に, $t<(1-c)\log_2 n$ならばこの確率は$n^{-1+c}$となり, 追加できる頂点の個数の期待値はおよそ$n^c$で非常に大きいので, そのような頂点は高確率で存在することになります.

$v_j$は$S_t$の全ての頂点と隣接していればクリークに追加できる.

(証明終)

衝撃的なことに, 本質的に貪欲法より良い多項式時間アルゴリズムはいまだに知られていません (それどころか存在しないと予想されています). 具体的には, 以下の主張が正しいかどうかは非常に重要な未解決問題です.

ある定数$\varepsilon>0$と多項式時間アルゴリズムが存在して, $G(n,1/2)$上で$(1+\varepsilon)\log_2 n$-クリークを確率$2/3$で見つける.

埋め込みクリーク問題

Erdős--Rényiグラフ$G(n,1/2)$上の最大クリーク問題の変種として, $k$-クリークが埋め込まれたランダムグラフから$k$-クリークを復元する問題を考えます. 具体的には, 入力として次の操作によって得られるランダムグラフ$G(n,k,1/2)$が与えられます:

1. Erdős–Rényiグラフ $G(n,1/2)$を生成する, ランダムに$k$個の頂点$v_1,\dots,v_k$を選び, $C=\{v_1,\dots,v_k\}$とする.
2. 各$1\leq i<j\leq k$に対して辺$\{v_i,v_j\}$を追加して$C$をクリークにする (元々$\{v_i,v_j\}$が辺をなす場合は追加しない).

ここで埋め込むクリークサイズ$k$は$k \gg \log n$とします. Erdős--Rényiグラフ$G(n,1/2)$はサイズが$O(\log n)$のクリークを持つので, 直感的にはサイズ$k$のクリークをランダムに埋め込むと一意になる気がします.

最大クリークのときと同様に, アルゴリズムの成功確率を以下のように定義します.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, $G(n,k,1/2)$上で成功確率$\gamma$で埋め込みクリーク問題を復元するという:
$$\begin{align*} \Pr_{G \sim G(n,k,1/2)} [ A(G,k) \text{ outputs the planted $k$-clique $C$ in }G]\ge \gamma. \end{align*}$$

ここでは, 簡単のため, アルゴリズム$A$はクリークサイズ$k$知っていると仮定する.

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,k,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

情報理論と計算量理論のギャップ

例えば$k=2$の場合はただの辺が埋め込まれただけなので, ランダムな辺を出力するしかできないので情報理論的に成功確率の上回は$O(1/n^2)$となります. 一方で任意の定数$c>0$に対し, $k\ge (2+c)\log_2 n$のとき, $G(n,k,1/2)$は確率$1-2kn 2^{-k/2}$で$k$クリークを一つだけ含むことが初等的な数え上げで示すことができます. このとき, 全探索によって高確率で埋め込んだクリークを復元できます.

実は, $G(n,1/2,k)$上でも$k\ge (2+c)\log_2 n$であれば ($k=n^{0.1}$とかであっても), $n^{O(\log n)}$時間で$k$-クリークを確率$1-o(1)$で解くことができます. 一方で$k \le 2\log_2 n$のときはErdős--Rényiグラフ$G(n,1/2)$は$2\log_2 n$クリークを持つので情報理論的に埋め込まれた$k$-クリーク$C$を復元することはできません.

命題.

任意の定数$c > 0$および$k\ge (2+c)\log_2 n$に対し, $G(n,1/2,k)$上で成功確率$1-o(1)$で埋め込みクリーク問題を解く$n^{O(\log n)}$時間アルゴリズムが存在する. 

証明.

アルゴリズムは非常にシンプルです: サイズ$2\log_2 n$の頂点部分集合$S \subseteq V$を列挙し, もしも$S$が$G(n,1/2,k)$においてクリークをなすならば貪欲法によって極大クリークを一つ選び, そのサイズが$k$と等しいならばその極大クリークを出力する. 最終的にサイズ$k$のクリークが見つからなかったら特別な記号$\bot$ (見つからなかった, を意味する)を出力する.

列挙した各$S$に対して一つの極大クリークしか考えないので計算時間は$n^{O(\log n)}$です. あとはこれで「取りこぼしがない」ことを証明する必要があります. $C$を埋め込まれたクリークとします. 列挙したときにある$S \subseteq C$に対して, $C$以外の頂点が貪欲法で追加され得ないことを示せばよいです. フォーマルに言うと, ある$S\subseteq C,|S|=2\log_2 n$が存在して, $C$の外側の頂点$v$であって$\Gamma(v) \supseteq S$を満たすものがないことを示せば, $V\setminus C$の頂点が貪欲法で追加され得ないため必ず極大クリークは$C$になります.

こうなるような$S$の存在性を示したい.

埋め込む位置$C$と$V\setminus C$の間の辺は全て独立なコイントスによって決まります. そこで固定した$C$で条件つけたときに所望の$S\subseteq C$が高確率で存在することが言い, その後に$C \sim \binom{[n]}{k}$に関する期待値をとれば$G(n,1/2,k)$上の確率を抑えたことになります.

固定した$C\subseteq [n]$に対し, $S\subseteq V$を$C$内からインデックスの若い$2\log_2 n$個の頂点からなる集合とします. $C$は固定されているため$S$もまた固定されています. 従って, 各$v \in V \setminus C$について$v$が$S$の全ての頂点に隣接している確率は$(1/2)^{2\log_2 n}\le n^{-2}$です (これは$S$が固定されているため, $S$の情報と辺の有無の情報が独立だから成り立つ). $v$についてのunion boundより, 確率$1-O(n^{-2})$で$\Gamma(v)\supseteq S$を満たす$v \in V\setminus C$は存在しません. すなわち, この$S$の構成は高確率で所望の性質を満たします. なお, この議論は$\log_2 n$の係数が$1$より真に大きければ同様に適用できます.

以上より, $G(n,1/2,k)$において, 埋め込んだクリーク$C$の中からインデックスの若い順に$2\log_2 n$個の頂点集合を$S$とすれば, $S$を含む極大クリークは$C$のみになりますので, 確かに列挙するアルゴリズムは埋め込みクリークを解きます. (証明終)

ここまでで単純な列挙によって$n^{O(\log n)}$時間で埋め込みクリーク問題は$k\ge 2.01\log_2 n$ならば高確率で解けることを確認し, $k\le 2\log_2 n$では情報論的に解けないことを見てきました. これは$k=2\log_2 n$が情報理論的に解けるかどうかの境界になっていると解釈できます. では, 同様の範囲の$k$で埋め込みクリーク問題を多項式時間で解けるでしょうか?

結論から言うと$k\ge \sqrt{n}$であれば確率$1-o(1)$で埋め込みクリーク問題は多項式時間で解けることが知られている[Alon, Krivelevich, Sudakov, '98]のですが, $k = o(\sqrt{n})$に対して多項式時間で解けるかどうかは30年来の未解決問題で, 実はある$c>0$に対して$k=n^{1/2-c}$に対して多項式時間で確率$2/3$で埋め込みクリーク問題を解く多項式時間アルゴリズムは存在しないのではないかと予想されています (埋め込みクリーク予想).

ここではAlonらの結果より少し弱い, $k\ge 10\sqrt{n\log n}$のときに埋め込みクリーク問題を解くアルゴリズム[Kučera, 95]を紹介します.

命題.

$k\ge 10\sqrt{n\log n}$のとき, $G(n,1/2,k)$上の埋め込みクリーク問題を高確率で解く多項式時間アルゴリズムが存在する.

証明 (概要).

アルゴリズムは「次数の大きい順に頂点を$k$個出力する」です. 埋め込まれたクリーク$C$に属する頂点は, クリークの分だけ次数が大きくなるはずであり, $k\ge 10\sqrt{n\log n}$ならばその差が有意であるという議論をします.

頂点$v \not\in C$の次数の周辺分布は二項分布$\mathrm{Bin}(n,1/2)$なので, Hoeffdingの不等式および$v$に関するunion boundより
$$\begin{align*} \Pr[\exists v\not\in C,\deg(v) > n/2 + \sqrt{n\log n}] \le n\cdot \exp(-2\log n) \le n^{-1} \end{align*}$$

を得ます. 一方, $v\in C$の次数の周辺分布は$k+\mathrm{Bin}(n-k,1/2)$なので, 同様にHoeffdingの不等式より, 任意の$t>0$に対し

$$\begin{align*} \Pr\left[\exists v\in C,\deg(v) < \frac{n-k}{2}+k-t\right] \le n\exp\left(-\frac{2t^2}{n}\right). \end{align*}$$

特に$t=4\sqrt{n\log n}$を代入すると, 確率$1-o(1)$で全ての$v\in C$は$\deg(v) \ge \frac{n}{2} + \sqrt{n\log n}$を満たします. 従って$k\ge 10\sqrt{n\log n}$のとき確かに次数を見ることで$C$が復元できます. (証明終)

Appendix. 埋め込みクリークの一意性

ランダムグラフ$G(n,k,1/2)$は埋め込まれたものが一つあるので, $k$クリークを一つ以上部分グラフとして含みます. ここでは$k\ge (2+c)\log_2 n$の場合は高確率で$k$クリークが一つであることを証明します.

この主張は直感的には自明に思えます. Erdős--Rényiグラフ$G(n,1/2)$の最大クリークは$2\log_2 n$なので, それより大きい$k$-クリークを埋め込むと確かに埋め込まれたクリーク以外に$k$-クリークは登場しなさそうです. ところが, $k$-クリークを埋め込むことによって非自明に大きいクリークが発生しうる懸念をケアしなければなりません.

$G(n,1/2,k)$における他のクリークのサイズはどのくらいになるのでしょうか? 埋め込まれたクリークを表す頂点部分集合を$C$とします. 任意の頂点$v \not \in C$は$C$内におおよそ$k/2$個の隣接点を持ちます.

これは, $v$と$C$の間の辺は独立に確率$1/2$で生起するので, $\Gamma(v)$を$v$の隣接点の頂点集合とすると, $|\Gamma(v) \cap C|$の周辺分布は$\mathrm{Bin}(k,1/2)$になり, これにHoeffdingの不等式を適用することでわかります (より詳しくいうと, 確率$1-n^{-100}$で, 全ての頂点$v$に対し$|\Gamma(v) \cap C| \le k/2 + 100\sqrt{k\log n}$がいえる.)

また, $\{v\} \cup \Gamma(v)$は$G(n,k,1/2)$内でクリークをなすので, $C$以外にも$k/2$-クリークを持つことがわかります. 実は$C$以外のクリークのサイズは全て$k/2 + O(\sqrt{k\log n}) \approx (1+o(1))k/2$以下になります.

この議論に基づくと, $k\ge 100\log_2 n$に対して$k$-クリークの一意性が証明できます (特に, Hoeffdingの不等式でネイピア数が出てくるのでlogの底に関して慎重にならなければなりません). $k\ge (2+c)\log_2 n$に対して一意性を示すにはもう少し丁寧な議論が必要です.

命題 [Theorem 4, Jerrum '92]. 任意の$k$に対して, $G(n,k,1/2)$が二つ以上の$k$クリークを含む確率は高々$2kn2^{-k/2}$である.

証明 (概要).

$V=[n]$を頂点集合, $C\subseteq V$を埋め込まれた$k$クリークとします. $C$とは別の$k$-クリーク$C' \neq C$の個数を$X$とし, その期待値を考えます. すなわち
$$\begin{align*} \mathbb{E} = \sum_{C'\in \binom{V}{k},C'\neq C} \Pr[C'\text{ is a $k$-clique}] \end{align*}$$

を上から抑えます. 各$t=0,1,\dots,k-1$に対し, $|C'\cap C|=t$なる$C'$を列挙して$t$に関する和を考えると

期待値$\mathbb{E}[X]$は
$$\begin{align*} \mathbb{E}[X] &= \sum_{t=0}^{k-1} \binom{k}{t}\binom{n-k}{k-t}\cdot 2^{-\binom{k}{2} + \binom{t}{2}} \\ &\le \sum_{t=0}^{k-1} \left(kn 2^{-k/2}\right)^{k-t} \\ &\le kn 2^{-k/2} \cdot \sum_{t=0}^\infty (1/2)^t \\ &\le 2kn 2^{-k/2} \end{align*}$$
を得ます.

STOC2日目以降の感想 (主にsunflower conjecture周り)

STOCが終わったので記憶が残っているうちに勢いに任せて前回に引き続きSTOC参加記(2日目〜5日目)を駆け足で書いていきます. 聴講して特に印象に残ったものについて記載しています. 勢いに任せて書いているのでテクニカルな内容はありません. ただし, sunflower lemmaの話については結構面白いと思ったので自分が理解した範囲で定義とかを書いていきます.

2日目

朝にLength-Constrained Expandersというワークショップに参加しました. 近年巷を騒がせているエクスパンダー分解や小直径分解という概念があるのですが, length-constrained expanderとはどちらの性質も同時に兼ね備えた分解を与える概念のようです. どちらの分解でも共通して頂点部分集合の分割$\mathcal{P}=(P_1,\dots,P_\ell)$であって, 各部分集合$P_i$のなる誘導部分グラフ$G[P_i]$が小直径または(Cheeger定数の意味で)エクスパンダーグラフとなるようなものを求めます. そして各$P_i$を縮約して得られるグラフに対して再帰的に分解を適用することによって, エクスパンダーからなる階層構造が得られます.

端的に言えば, 最悪時の問題例を分解によってエクスパンダー上で解くことに帰着するみたいなことをするようです. length-constrained expanderとは小直径分解とエクスパンダー分解両方の嬉しい性質を同時に達成するような分解らしいです.

2日目の午後は自分の発表を行いました. その次のセッションはランダムウォークなど確率解析のセッションでした. 時差ボケであまりちゃんと聞けなかったのですが最後の発表

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs (Kiril Bangachev and Guy Bresler)

が印象的でした. この論文ではランダム幾何グラフとErdős--Rényiグラフの識別問題に対してよく知られる計算量と情報理論のギャップ (computational-statistical gap) について議論しており, low-degree polynomialと呼ばれるアルゴリズムのクラスでは両者のギャップが埋まる, という話でした.

3日目

午後は誤り訂正符号のセッションに行きました. 近年のTCSでは3クエリのlocally correctable codeのレートに関する効率性の下界を, これまで知られていたものより指数的に改善したという論文

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes (Pravesh K. Kothari, Peter Manohar)

の発表がありました. これはTCSの符号界隈で非常に大きな話題になりました.

その次のセッションは

Complexity-Theoretic Implications of Multicalibration, (Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan)

でした. この論文はarXivに出た瞬間から個人的に注目していた論文です. additive combinatoricsにおけるdense model theorem (Green-Taoの定理の証明で重要な役割を果たした定理), Impagliazzoのhardcore補題, そしてFrieze-Kannanの正則化補題がどれも同じような構成的証明を与えていることに着目して共通の一般化を与えたという論文があるのですが, この論文はそれをmulticalibrationの観点でさらに一般化したというものです. この論文もquanta magazineの記事で紹介されています.

4日目

Applications of Turán-type problems in Theoretical Computer Scienceというワークショップに参加しました. Turánの定理とは完全グラフ$K_r$を部分グラフとして含まないグラフのうち最も辺数が多いものは, 等分割された完全$(r-1)$部グラフであるという主張です. 例えば三角形を含まないグラフの中で最もデンスなのは完全二部グラフです.

この問題は次のような自然な設定で登場します:

$n$個の電池があり, そのうち$r$個のみが充電されていて他は全て充電が空なのですが, どれが充電されていてどれが空か分からないとします. 手元には懐中電灯があり, 充電されている電池を2個入れると光ります. $n$個の中から二つの電池を入れて試すという試行を何回か行って懐中電灯を光らせたいとき, 最も試行回数を少なくするにはどうすればよいか?

グラフの言葉に翻訳すると以下になります: $n$個の頂点があってサイズ$r$の独立点集合を含まないグラフのうち最も辺数が少ないものは何か? グラフを一つ固定したとき, 各辺は懐中電灯の一回の試行に対応します. このグラフがもしもサイズ$r$の独立点集合$I$を持つならば, この頂点部分集合$I$が「充電された電池」であったときにこの試行で懐中電灯を光らせることができません. この解となるグラフの補グラフをとるとTuránの定理の設定になります.

Turán-typeな問題とは, 固定されたグラフ$H$を含まないグラフの中で最も密なものは何かという極値グラフ理論の問題です. 例えば奇数長の閉路は完全二部グラフを考えれば辺数$\Omega(n^2)$を達成しますが, 四角形を含まない任意の$n$頂点グラフは辺数が$O(n^{1.5})$になります (こちらの記事で証明しています). 応用として, ワークショップではErdősの内周予想やそれの最近の進展について取り上げられていました. 特に興味深かったのは$H=C_8$のときは未解決であるということでした. つまり, 長さ$8$の閉路を含まない$n$頂点グラフのうち最大辺数を$\mathrm{ex}(n;C_8)$とすると現在知られている最善のバウンドが

$$\Omega(n^{6/5}) \le \mathrm{ex}(n;C_8) \le O(n^{5/4})$$
となっており, このギャップを埋めるのはこの分野の中心的な未解決問題らしいです.

5日目

前日に引き続きTuranのワークショップに参加しました. とあるpseudorandomnessを満たす部分集合族を使ってsunflower lemmaの改善を与えた論文の話がありました. 集合$S_1,\dots,S_r \subseteq [n]$は, 全ての$i\neq j$に対して$S_i \cap S_j = S_1 \cap \dots \cap S_r$を満たすとき, $r$-ひまわりと呼びます. 

$[n]$上の集合族$\mathcal{S}=\{S_1,\dots,S_m\}$は, ある$S_{i_1},\dots,S_{i_r}\in\mathcal{S}$が$r$-ひまわりをなすとき, $r$-ひまわりを含むといいます. $r$-ひまわりを含まない部分集合族$\mathcal{S}$であって最も多くの集合を持つものはどのようなものになるでしょうか?

定理 (Erdős-Rado, '60)

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. もし$|\mathcal{S}| > w! \cdot (r-1)^w$を満たすならば, $\mathcal{S}$は必ず$r$-ひまわりを含む.

この$m$のバウンド$w!\cdot (r-1)^w$を漸近的に改善できるのではないか? というのがひまわり予想です.

予想 (Erdős-Rado, '60).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. 各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>C^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

Alweiss, Lovett, Wu, and Zhang (STOC20) はErdős-Radoの定理のバウンドを改善し以下の定理を証明しました:

定理 (Alweiss, et al. (2021)).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする.  各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>(Cr^3 \log w \log\log w)^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

ワークショップではこの定理の証明の雰囲気が紹介されました. まず, 集合族$\mathcal{S}$の擬似ランダム性を以下で定義します:

定義.

$[n]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. この集合族$\mathcal{S}$は, 任意の$T\subseteq[n]$に対して
$$\begin{align*} \Pr_{S \sim \mathcal{S}} [ S \supseteq T ] \le \kappa^{|T|} \end{align*}$$
を満たすとき, $\kappa$-spreadという.

部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$および$T\subseteq[n]$に対し, $T$のリンク$\mathcal{S}_T$とは, 部分集合族であって,
$$\begin{align*} \mathcal{S}_T = \{S\setminus T \colon T \subseteq S\in\mathcal{S} \} \end{align*}$$
によって定まるものです. リンクの言葉を使うと, $\mathcal{S}$が$\kappa$-spreadであるというのは, 任意の$T$のリンク$\mathcal{S}_T$が
$$\begin{align*} |\mathcal{S}_T| \ge \kappa^{-|T|}\cdot |\mathcal{S}| \end{align*}$$
を満たすことを意味します ($\mathcal{S}_T$の要素数は$T$を含む$\mathcal{S}$に属す部分集合の個数に等しいから).

重要な観察として, もしもリンク$\mathcal{S}_T$が$r$-ひまわり$\{S'_1,\dots,S'_r\}$を含むとしましょう. すると, $S'_1\cup T, \dots, S'_r \cup T$は$\mathcal{S}$における$r$-ひまわりになっているはずです. すなわち, リンクをとった後にひまわりがあるならば元の集合族に復元することができます.

適切な$\kappa$を選びます. もしも今持っている集合族$\mathcal{S}$が$\kappa$-spreadでないとするならば, 定義よりある$T$が存在して$|\mathcal{S}_T| > \kappa^{|T|}\cdot |\mathcal{S}|$となります. このリンク$\mathcal{S}_T$に対してひまわりの存在性を言えば, $\mathcal{S}$がひまわりを持つことが示せます. これを再帰的に繰り返していくと, $\kappa$-spreadingな集合族に対して議論すれば良いことになります. Alweissらの貢献は$\kappa$-spreadingな集合族に対してはdisjointな部分集合$S_{i_1},\dots,S_{i_r}$がとってこれることを示したこと(らしい)です. disjointな部分集合族はひまわりをなすので, これで定理の主張が証明できたことになります.