The 123 Theorem

こんにちは. のぶしみです. 最近Mathlogという数学の記事共有サービスを使って記事を書くことにハマっておりまして, つい最近, エキスパンダーグラフの紹介記事を書きました. しかし今まで5年以上このブログをやってきているので, メジャーなトピックはmathlogで紹介し, マイナーなトピックは引き続きこのブログで紹介していきたいと思います.

そこで今回は123 Theoremと呼ばれる定理を紹介します. 変わった名前ですが, 次の定理です:

定理 (123 Theorem)

$X,Y$を同じ分布に従う実数上の二つの独立な確率変数とする. このとき

$$\Pr[|X-Y|\geq 2] \leq 3 \Pr[|X-Y|\geq 1].$$

123 Theoremという名前は不等式に出てくる三つの定数に由来します. 私がこの定理に初めて出会ったのは2021年1月に研究室の後輩とAlon & Spencer の The Probabilistic Method の輪読していた時に第1章の演習問題として出題されていた時でした. 私は基本的に本を読むときは演習問題は頑張って解く習慣があるので, 頑張って証明しようしたのですがかなり苦戦して, 結局丸一日を溶かして以下のようにして示すことが出来ました. 実は同じ証明が[1]に載っていてビックリしたので紹介します.

証明.

$x_1,\ldots,x_m\in\mathbb{R}$を$X$の分布に従って独立にサンプリングされた$m$個の点とし, $T_r=\{(i,j):|x_i-x_j|\leq r\}$とする ($(i,i)\in T_r$とする). まず

$|T_2| \leq 3|T_1|$ ......(1)

を示す. この主張は定理の離散化みたいなもので, 実は(1)を示せば良いということが以下の議論から分かります:

$$\mathrm{E}[|T_2|]=m+m(m-1)\Pr[|X-Y|\leq 2]$$

$$\mathrm{E}[|T_1|]=m+m(m-1)\Pr[|X-Y|\leq 1]$$

および(1)より

$$m+m(m-1)\Pr[|X-Y|\leq 2] \leq 3m+3m(m-1)\Pr[|X-Y|\leq 1].$$

これを整理すると,

$$\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1] + \frac{2}{m-1}.$$

これが任意の$m$に対して成り立つので, $m\to\infty$とすれば,

$$\forall\epsilon>0,\,\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1]+\epsilon.$$

即ち定理の主張が従う.

(1)の証明.

有向区間グラフの言葉で説明する. $\{x_1,\ldots,x_m\}$および$r>0$に対し, 有向グラフ$G_r$を, $V(G_r)=[m]=\{1,\ldots,m\}$, $E(G_r)=T_r$とする. 特に$(i,j)\in E(G_r)$ならば$(j,i)\in E(G_r)$でもあるので, 向きを付けることに本質的な意味はないが, 辺の本数=$|T_r|$として議論していきたいので有向グラフを考えることにする. つまり, $|E(G_2)|\leq 3|E(G_1)|$を示せば良い. 

二つのグラフ$G_1,G_2$を考える. 頂点$i$のグラフ$G_r$における出次数を$\deg_r^+(i)$とする. つまり, $\deg_r^+(i)=|\{j\in[m]:(i,j)\in E(G_r)\}|$であり, 自己ループも1としてカウントする.

主張(1)の証明は$m$に関する帰納法で行う. $m=1$なら$T_r=\{(1,1)\}$なので(1)は成り立つ. $m\geq 2$の場合を考える. $i\in[m]$を$G_1$内で最大出次数を持つ頂点とする. このとき, $\deg^+_2(i) \leq 3\deg^+_1(i)$が成り立つことを言う. もし$\deg^+_2(i)>3\deg^+_1(i)$とすると, 数直線上の区間 $[x_i+1,x_i+2]$ と $[x_i-2,x_i-1]$ のどちらかに必ず$>\deg^+_1(i)$個の点がある (下図).

図. もし$\deg_2^+(i)>3\deg_1^+(i)$なら, より出次数の大きい点がとれる.

これは$\deg^+_1(i)$が最大であることに矛盾します. 従って $\deg_2^+(i)\leq 3\deg_1^+(i)$です. $G_1$と$G_2$からそれぞれ頂点$i$を削除して得られるグラフを$G'_1$, $G'_2$とすれば, 帰納法の仮定より$|E(G'_2)|\leq 3|E(G'_1)|$であり, $|E(G_r)|=|E(G'_r)|+2\deg^+_r(i)+1$なので,

$$|E(G_2)|\leq 3|E(G'_1)|+6\deg^+_1(i)+1<|E(G_1)|$$

となり(1)が成り立つ.

補足

123 Theoremはタイトな例を作ることができ, 例えば$\Pr[|X-Y|\leq 2] \leq 2.99\Pr[|X-Y|\leq 1]$は一般には成り立ちません: $\{2,4,6,\ldots,2n\}$上の一様分布を考え, この分布に従う独立な二つの確率変数$X,Y$を考えます. このとき,

$$\Pr[|X-Y|\leq 2] = \frac{3}{n}-\frac{2}{n^2},$$

$$\Pr[|X-Y|\leq 1] = \Pr[X=Y]=\frac{1}{n}$$

より, $\Pr[|X-Y|\leq 2] = 3\Pr[|X-Y|\leq 1] - \frac{2}{n^2}.$

参考文献

[1] N. Alon and R. Yuster. The 123 Theorem and its extensions, Journal of Combinatorial Theory, Series A, 72(2)322--331, 1995.

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

ランダム正則グラフ理論において有名な sandwich conjecture と呼ばれる予想があるのですが, 最近この予想に大きな進展[3,4]が見られたので紹介します. このトピックは私が修士の頃から論文を読んで追っていたトピックなので, 今回の進展をもたらした論文の登場は個人的にはかなり衝撃的でした.

1. ランダム正則グラフとErdős–Rényiグラフ

1.1. 定義

$n$ 頂点 $d$-正則の頂点ラベル付きグラフ全体の集合から一様ランダムに取り出したグラフをランダム$d$-正則グラフと呼び, $G_{n,d}$ で表します. また, $n$頂点の各頂点のペアを独立に確率$p$で辺で引いて得られるランダムなグラフを Erdős–Rényiグラフと呼び, $G(n,p)$ で表します. $G(n,p)$の基本的な性質などは以前の記事を参照してください.

1.2. ランダムグラフの解析

ランダムグラフの解析をする上でそのランダムグラフの生成モデルに対する考察が不可欠です. たとえば, 

$p=o(n^{-1})$ に対して $G(n,p)$ は確率 $1-o(1)$ で三角形を含まない

という事実が知られていますが, これは, $X$ を $G(n,p)$内に含まれる三角形の個数と定めたときに, Markovの不等式より

$\Pr[X\geq 1] \leq \mathbb{E}[X] = \binom{n}{3}p^3 \leq (np)^3 = o(1)$

となることから従います. $G(n,p)$を考えると$\mathbb{E}[X]$の期待値が非常に計算しやすいためにこのような簡単に証明できるわけです.

それでは, $G_{n,d}$ に含まれる三角形の個数 $X$ に対して $\mathbb{E}[X]$ を求める時はどのようにすれば良いでしょうか？ $G(n,p)$の場合は各辺が独立に出現していたので簡単に $\mathbb{E}[X]$ を求められましたが, $G_{n,d}$ はそうとはいきません.

実は, $G_{n,d}$ には configuration model と呼ばれる生成モデルが知られていて, これを使えば $2^{O(d^2)} nd$ 時間でランダム $d$-正則グラフを生成することができます. 技術的な詳細は省きますが, このconfiguration model に基づけば $d=d(n)$が $n$ に依存しない定数ならば $G_{n,d}$ のさまざまな構造的性質を用意に解析することができます. 例えば, $d$が定数のときは $n\to\infty$ の漸近で三角形の個数$X$ はポアソン分布に従うことが証明できます. また, $d=d(n)$ が $o(\sqrt{\log n})$ くらいまでならなんとかできることもありますが, 例えば $d=(1+o(1))n^{1/3}$ などの場合は難しくなります.

$d=d(n)$ が大きいときの$G_{n,d}$の生成はそれ自体が一つの研究トピックになるほど難しい問題になっていて, 例えば $d=o(n^{1/2})$ に対して $G_{n,d}$ を $O(nd^3)$ 時間でサンプリングする論文がFOCS15に採択されています[6]. このトピックは多くの論文がありますが, 大体は switching method と呼ばれる手法に基づいたものになっていて, この手法を考えることで$G_{n,d}$ の解析を (時にはかなりアドホックな発想も必要になりつつも) 行うことができます ([2]の10章参照). しかしながら switching method を以てしても $d=o(n^{1/2})$ などの条件を課す必要があります. 

すなわち, $d=d(n)$ が大きくなるにつれて$G_{n,d}$の生成と解析は困難なものになっていきます.

1.3. 構造的類似性

$G(n,p)$ の平均次数 $np$ が $np=d=\omega(\log n)$ を満たすとき, $G_{n,d}$と近い構造を持つであろうことが以下の議論から推察できます: まず, $G(n,p)$の頂点 $v$ を固定しその次数 $\deg(v)$ を考えます. この値は$G(n,p)$ がランダムに生成されるので確率変数となっていますが, $\deg(v)=\sum_{u\in V\setminus \{v\}} \mathbb{1}_{uv\in E}$ と書けてこれは独立確率変数の和になっているため, 期待値 $(n-1)p\approx np$ に集中します. 具体的には, Chernoff bound (補足の章の補題A.1参照) とUnion boundを組み合わせると, 任意の$t>0$に対し $$\Pr[\forall v\in V, |\deg(v)-(n-1)p|\geq t] \leq 2n\exp\left(-\frac{t^2}{2(n-1)p+2t/3}\right)$$ が示せます. 特に, $np=\omega(\log n)$ が成り立つときに $t=10\sqrt{np\log n}$ を代入すると, 非常に高い確率で, 全ての頂点の次数が $np\pm 10\sqrt{np\log n}$ の範囲におさまることが示せます. この議論から, $G(n,p)$ は "ほぼ" $(np)$-正則グラフとみなすことができるので, $np=d$のときは $G(n,p)$と$G_{n,d}$は似た構造的性質を持つことが予想されます. 実際, 彩色数や最大クリークのサイズなどは漸近的にほぼ同じ値を持つことが知られています.

(*) あくまでもこの類似性は $d=np$ が大きい場合にのみ成り立つことに注意してください. 例えば $d=np=3$ のとき, $G_{n,d}$ は確率 $1-o(1)$ で連結である一方で $G(n,p)$ は確率 $1-o(1)$ で非連結です.

2. Sandwich conjecture

1章で述べた類似性をちゃんと議論した研究が幾つかあります [1,3,4,5]. 一番最初にこの類似性を研究したのは Kim & Vu [5] です. 彼らの定理を述べるために, $\mathcal{G}(n,p)$ を $G(n,p)$ の分布, $\mathcal{G}_{n,d}$ を $G_{n,d}$ の分布とし, $X\sim \mathcal{G}$ と書いた時は確率変数 $X$ は分布$\mathcal{G}$に従うことを意味します. また, 次の定理ではランダムグラフのカップリングについて考えていきます. カップリングの定義などについては補足A.2を参照ください.

定理1 (Informal; Theorem 2 of [5]).

$d=d(n)\in\mathbb{N}$ を, $d=\omega(\log n)$ かつ $d=o(n^{1/3}/\log^2 n)$ を満たす関数とする.

$p_1=p_1(n)=(1-O(\log n/d)^{1/3}) d/n$,

$p_2=p_2(n)=(1+o(1))d/n$

とする. このとき, 次を満たす $G_L\sim \mathcal{G}(n,p_1)$, $G_d\sim \mathcal{G}_{n,d}$, $G_U\sim \mathcal{G}(n,p_2)$ のカップリング $\pi$ が存在する:

(1) $\Pr[E(G_L) \subseteq E(G_d)] = 1-o(1)$.

(2) 確率 $1-o(1)$ で $E(G_U) \setminus E(G_d)$ のなすグラフの最大次数は $o(\log n)$

定理1の内容はinformalなもの (特に $p_2$ には実際にはもう少し条件が設定されている) であることに注意してください. 厳密なステートメントを知りたい方は元論文[5]を参照してください.

定理1から, $G_{n,d}$ は $d$ が定理1の条件を満たす場合は $p\approx d/n$ に対し $G(n,p)$ を部分グラフとして含むということが従います. 例えばこの $G(n,p)$ が直径$\leq 10$ であったならば, これを含む $G_{n,d}$ も直径$\leq 10$ になることが直ちに従います. より一般的に, 辺の追加における単調性を持つような性質を$G_{n,d}$が持つという証明をしたい場合は対応する $G(n,p)$ で考えれば良いという議論になるので, ランダム正則グラフの構造的性質の証明が一気にしやすくなるわけです.

その一方で, (2)の結果では単に $G(n,p_2)\setminus G_{n,d}$ の最大次数が抑えられるということしか主張しないので, $G(n,p_2)$が$直径>10$であることが言えたとしてもそこから$G_{n,d}$が直径$>10$になることが従うわけではありません. つまり, 定理1には

・ $d=d(n)$ に条件がついている (特に, $d=o(n^{1/3})$じゃないといけない).

・包含関係が片方しか示されていない.

という二つの問題点が残っていることになります. Kim と Vuは sandwich conjectureと呼ばれる次の予想を[5]で提示しています:

予想 (Sandwich conjecture, Conjecture 1 of [5]).

$d=d(n)=\omega(\log n)$ とする. ある関数 $p_1=(1-o(1))d/n$, $p_2=(1+o(1))d/n$ に対して, 以下を満たす $G_L\sim \mathcal{G}(n,p_1)$, $G_d\sim \mathcal{G}_{n,d}$, $G_U\sim \mathcal{G}(n,p_2)$ のカップリングが存在する:

$\Pr[G_L \subseteq G_d \subseteq G_U] = 1-o(1)$.

3. Sandwich conjecture 解決への進展

Sandwich conjectureに対する進展を簡単に紹介していきます.

・Kim & Vu [5] では上にあげた二つの問題点を残していました.

・Dudek, Frieze, Ruciński, and Šileikis [1] は, $d=\omega(\log n)$ かつ $d=o(n)$ ならば, ある$p_1=(1-o(1)) d/n$ に対して 定理1 の(1) の条件を満たすようなカップリングがあるということを示しています. 実際には[1]ではランダムグラフを一般化したランダムハイパーグラフを考えてカップリングの存在性を証明しています. ランダムグラフの本[2]の10章にこの結果の説明と証明が載っているので気になる方は参照ください. 実は, 私が2018年にSODAに通した論文も[1]の結果を用いています.

・Gao, Isaev, and McKay [4] は $d=\omega(n/\sqrt{\log n})$ に対して Conjecture 1 が真であることを主張しています. Kim and Vu の問題点だった逆方向の包含関係を ($d$が非常に大きいという仮定の下ではありますが) 解決したものになっています.

・Gao [3] は $d=\Omega((\log n)^7)$ に対して Conjecture 1 は真であることを主張しています. [4]では $d$ の仮定が非常に強いものでしたが, これをほぼ解決したということになります.

4. まとめ

ランダム正則グラフが研究に出てくるときは, $p=d/n$ に対して $G(n,p)$ を考えると良いです. もし $G(n,p)$ が望ましい性質を持つならば, sandwich conjecture より, 対応する $G_{n,d}$ も同様の性質を持つことが言えるかもしれません.

A. 補足

A.1. 集中不等式

補題A.1 (Chernoff bound; Theorem 21.6 of [2]).

$X_1,\ldots,X_n$を独立な確率変数で, $0\leq X_i\leq 1$ とする (必ずしも同一である必要はない). $S=\sum_{i=1}^n X_i$ とし, その期待値を $\mu$ とする. このとき, 任意の$t>0$に対して以下が成り立つ:

$$\Pr[S\geq \mu+t] \leq \exp\left(-\frac{t^2}{2\mu + 2t/3}\right),$$

$$\Pr[S\leq \mu-t] \leq \exp\left(-\frac{t^2}{2\mu + 2t/3}\right).$$

A.2. カップリング

$X$と$Y$をそれぞれ分布 $\mathcal{D}_X,\mathcal{D}_Y$ に従う確率変数とします. $X$と$Y$の同時分布 $\pi$ であって, $X$と$Y$の周辺分布$\pi_X$, $\pi_Y$ がそれぞれ$\mathcal{D}_X$, $\mathcal{D}_Y$と等しいものを, $X$と$Y$のカップリングと呼びます. この記事では$G(n,p)$や$G_{n,d}$をそれぞれ確率変数とみなし, ランダムグラフ同士のカップリングを考えることがあります. また, 確率変数と分布を区別するために, $G(n,p)$と$G_{n,d}$の分布をそれぞれ $\mathcal{G}(n,p)$, $\mathcal{G}_{n,d}$ と書くことにします.

例1: $G(n,p)$ と $G(n,p)$ のカップリング.

$\mathcal{G}(n,p)$に従って得られた二つのグラフ $G_1,G_2$ が, $G_1=G_2$を満たすようなカップリングが存在します. 最初に$X$として$G(n,p)$を考え, 次に$Y=X$とするだけです. このカップリングにしたがって得られた二つのグラフ $G_1,G_2$は必ず $G_1=G_2$ となっており, $G_1$と$G_2$の周辺分布はどちらも$\mathcal{G}(n,p)$ になっています. 自明な例です.

例2: $G(n,p_1)$ と $G(n,p_2)$ のカップリング.

$p_1\leq p_2$ とします. $G_1\subseteq G_2$ となるような $G_1\sim \mathcal{G}(n,p_1)$ と $G_2\sim \mathcal{G}(n,p_2)$ のカップリングが存在します. まず, $G_2\sim\mathcal{G}(n,p_2)$を生成します. そして得られたグラフ$G_2$の確辺を確率 $1-p_1/p_2$ で削除して得られたグラフを$G_1$とします. このように生成したグラフの組 $(G_1,G_2)$ は $G_1\subseteq G_2$の条件をみたします. $G_2$の周辺分布は明らかに$\mathcal{G}(n,p_2)$です. 最後に$G_1$の周辺分布を考えます. $G_1$の各辺は独立に現れ, その確率は$p_2\cdot (1-(1-p_1/p_2))=p_1$ となり, 確かに$G_1$の周辺分布は$\mathcal{G}(n,p_1)$となります.

この例で紹介したカップリングの存在生から, 例えば次の結果が用意に証明できます:

命題 A.2.

$G(n,p_1)$が確率$1-o(1)$で連結であるとする. このとき, 任意の $p_2\geq p_1$ に対して $G(n,p_2)$は確率$1-o(1)$で連結である.

証明:

例2のカップリング$\pi$を考える. このとき

$$\Pr[G(n,p_2)\text{ is connected}] = \Pr_{(G_1,G_2)\sim \pi}[G_2\text{ is connected}]\geq \Pr_{(G_1,G_2)\sim \pi}[G_1\text{ is connected}]$$

となり, $G_1\sim\mathcal{G}(n,p_1)$は確率$1-o(1)$で連結であることから主張は直ちに従います. 上式の不等号は$G_1\subseteq G_2$から従います.

一般に, 連結性といった, 辺の追加でinvariantなグラフの性質ならどんなものでも命題A.2のような結果が例2のカップリングを使えばすぐに示せます.

参考文献

[1] Andrzej Dudek, Alan Frieze, Andrzej Ruciński, and Matas Šileikis. Embedding the Erdős–Rényi hypergraph into the random regular hypergraph and Hamiltonicity, JCTB, 2017.

[2] Alan Frieze, and Michał Karoński. Introduction to random graphs, Cambridge University Press, 2015

[3] Pu Gao, Kim-Vu's sandwich conjecture is true for all $d=\Omega(\log^7n)$. arXiv, 2020. https://arxiv.org/abs/2011.09449

[4] Pu Gao, Mikhail Isaev, and Brendan D. McKay. Sandwiching random regular graphs between binomial random graphs. In Proceedings of SODA, 2020.

[5] Jeong Han Kim and Van H Vu. Sandwiching random graphs: Universality between random graph models. Advances in Mathematics, 2004.

[6] Pu Gao and Nicholas Wormald. Uniform Generation of Random Regular Graphs, In Proceedings of FOCS, 2015.