2018-01-22

ハイパーグラフ除去補題ー４

定義記事３の正則化補題の記号・仮定・帰結を考え、 $\mathcal{H}:=\bigcup_{0 \leq j \leq d}H_j$ とする。各 $e \in \mathcal{H}$ に対して、 $\mathcal{B}_e$ のアトム $A_e$ をとる。このとき、 $\displaystyle \bigcap_{e \in \mathcal{H}}A_e$ (これは空集合か $\bigvee_{e \in \mathcal{H}}\mathcal{B}_e$ のアトム)がgoodであるとは、任意の $0 \leq j \leq d$ および $e \in H_j$ に対して次の二つの評価が成り立つときにいう:

$\displaystyle \mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) \geq \frac{1}{\log F(M_j)}\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr)$ −①

$\displaystyle \mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2 \prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \frac{1}{F(M_j)}\mathbb{E}\Bigr(\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr)$ −②

$\log F$ が負となるような状況は扱わない。 $0 \leq j \leq d, \ e \in H_j$ , $\mathcal{B}_e$ のアトム $A_e$ に対して、 $B_{e, A_e}$ を

$\displaystyle B_{e, A_e} := \bigcup_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① or ② 不成立}}}\Bigl(\bigcap_{f \subsetneq e}A_f\Bigr) \in \bigvee_{f \subsetneq e}\mathcal{B}_f$

と定める。 $\displaystyle \bigcap_{e' \in \mathcal{H}}A_{e'}$ がgoodでなければ、或る $e \in \mathcal{H}$ が存在して

$\displaystyle \bigcap_{e' \in \mathcal{H}}A_{e'} \subset A_e \cap B_{e, A_e}$

が成り立つ。次の補題は殆どのアトムはgoodであることを意味する。

補題正則化補題の記号・仮定・帰結および上記記号設定を考える。このとき、任意の $0 \leq j \leq d$ , $e \in H_j$ および $\mathcal{B}_e$ のアトム $A_e$ に対して

$\displaystyle \mathbb{E}\left(\mathbf{1}_{A_e}\mathbf{1}_{B_{e, A_e}}\right) = O\left(\frac{1}{\log F(M_j)}\right)$

が成り立つ。

証明. 定義より

$\displaystyle B_{e, A_e} \subset \bigcup_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\Bigl(\bigcap_{f \in \partial e}A_f\Bigr) \cup \bigcup_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\Bigl(\bigcap_{f \subsetneq e}A_f\Bigr)$

が成り立つので、

$\displaystyle \mathbb{E}\left(\mathbf{1}_{A_e}\mathbf{1}_{B_{e, A_e}}\right) \leq \sum_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) + \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr)$

と評価できる。一つ目の和は

$\displaystyle \sum_{\substack{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{① 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) < \sum_{\{A_f\}_{f \in \partial e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f)}\frac{1}{\log F(M_j)}\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr) = \frac{1}{\log F(M_j)}$

と評価できる。二つ目の和は

$\begin{align} &\sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \\ &< \sum_{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f)}F(M_j)\mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2 \prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \\ &\leq F(M_j)\mathbb{E}\Bigl( \Big| \ \mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr) - \mathbb{E}\Bigl( \mathbf{1}_{A_e} \ \Big| \ \bigvee_{f \in \partial e}\mathcal{B}_f \Bigr) \ \Big|^2\Bigr)\end{align}$

と評価できるが、正則化補題より

$\displaystyle \mathcal{E}_{A_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f'\Bigr)-\mathcal{E}_{A_e}\Bigl(\bigvee_{f \in \partial e}\mathcal{B}_f\Bigr) \leq \frac{1}{F(M_j)^2}$

が成り立つので、エネルギーギャップ公式と合わせて

$\displaystyle \sum_{\substack{\{A_f\}_{f \subsetneq e}, \ A_f \in \mathrm{Atom}(\mathcal{B}_f) \\ \text{② 不成立}}}\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \subsetneq e}\mathbf{1}_{A_f}\Bigr) \leq \frac{1}{F(M_j)}$

が得られ証明が完了する。 Q.E.D.

定理 (カウンティング補題) 正則化補題の記号・仮定・帰結および定義の設定を考える。 $\displaystyle \bigcap_{e \in \mathcal{H}}A_e$ はgoodであると仮定する。 $F\colon \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ が $\#J$ に依存して十分成長速度の速い関数であれば、

$\displaystyle \mathbb{E}\Bigl(\prod_{e \in \mathcal{H}}\mathbf{1}_{A_e}\Bigr) = \left(1+o_{M_d \to \infty; \#J}(1)\right)\prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) + O_{\#J, M_0}\left(\frac{1}{F(M_0)}\right)$

が成り立つ。

$\bigcap_{f \in \partial e}A_f=\emptyset$ のときは $\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr)=1$ とする。カウンティング補題の証明は後回しにして、ハイパーグラフ除去補題の証明を先に完了させる。

定理 (ハイパーグラフ除去補題、再掲) $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系とする。ハイパーエッジ $e \in H$ 毎に $E_e \in \mathcal{A}_e$ であって、 $0 < \delta < 1$ に対して

$\displaystyle \mathbb{E}\Bigl(\prod_{e \in H}\mathbf{1}_{E_e}\Bigr) \leq \delta$

が成り立つようなものをとる。このとき、各 $e \in H$ に対して或る $E_e' \in \mathcal{A}_e$ が存在して

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset,\quad \mathbb{E}\Bigl(\mathbf{1}_{E_e \setminus E_e'}\Bigr) = o_{\delta \to 0; \#J}(1)$

が成り立つ。更に、 $e' \subset J, \ \#e' < d$ に対して部分 $\sigma$ 加法族 $\mathcal{B}_{e'} \subset \mathcal{A}_{e'}$ が存在して、 $\mathrm{cpx}(\mathcal{B}_{e'}) = O_{\delta, \#J}(1)$ かつ任意の $e \in H$ に対して

$\displaystyle E_e' \in \bigvee_{e' \subsetneq e}\mathcal{B}_{e'}$

が成り立つ。

カウンティング補題 $\Longrightarrow$ ハイパーグラフ除去補題の証明. ハイパーグラフ除去補題の設定を考える(「このとき、」の直前まで)。 $0 \leq j \leq d$ に対して $H_j$ を $H_d:=H$ , $H_j:=\partial H_{j+1} \ (0 \leq j < d)$ で定める。 $\displaystyle \mathcal{H}:=\bigcup_{0 \leq j \leq d}H_j$ とする。各 $e \in H_d$ に対して、 $\mathcal{B}_e:= \mathcal{B}(E_e) \subset \mathcal{A}_e$ とする( $E_e$ が生成する $V_J$ 上の $\sigma$ 加法族)。 $\mathrm{cpx}(\mathcal{B}_e) \leq 1$ である。

$M_d \geq 1$ は $\delta, \#J$ に依存して後で決まる整数とする( $\mathrm{cpx}(\mathcal{B}_e) \leq M_d$ は成立している)。また、 $F\colon \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ は正則化補題および後の議論で要求されるだけ十分成長速度の速い、 $\#J$ のみに依存して定まる関数とする。

以上の設定で正則化補題を適用することによって存在する $M_0, M_1, \dots, M_{d-1}$ および $(\mathcal{B}_f, \mathcal{B}_f') \ ({}^{\forall}f \in H_j \ (0 \leq j < d) )$ をとる。この $\mathcal{B}_f$ 達が除去補題が後半に主張する $\sigma$ 加法族となる(証明はこれから)。次の不等式を思い出しておく。

$M_d \leq F(M_d) \leq M_{d-1} \leq F(M_{d-1}) \leq \cdots \leq M_0 \leq F(M_0) \leq O_{\#J, M_d, F}(1)$

後の $M_d, F$ の選択によって、 $\mathrm{cpx}(\mathcal{B}_f) \leq M_j = O_{\#J, M_d, F}(1) = O_{\delta, \#J}(1)$ が約束されている。

各 $e \in H_d$ に対して、 $E_e'$ を

$\displaystyle E_e' := V_J \setminus \Bigl( B_{e, E_e} \cup \bigcup_{f \subsetneq e}\bigcup_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}(A_f \cap B_{f, A_f})\Bigr)$

と定義する。定義より、 $\displaystyle E_e' \in \bigvee_{f \subsetneq e}\mathcal{B}_f \subset \mathcal{A}_e$ がわかる。

$\displaystyle E_e\setminus E_e' = E_e \cap \Bigl(B_{e, E_e} \cup \bigcup_{f \subsetneq e}\bigcup_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}(A_f \cap B_{f, A_f})\Bigr)$

なので、補題より

$\begin{align} \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) &\leq \mathbb{E}(\mathbf{1}_{E_e}\mathbf{1}_{B_{e, E_e}})+\sum_{f \subsetneq e}\sum_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}\mathbb{E}(\mathbf{1}_{A_f}\mathbf{1}_{B_{f, A_f}}) \\ &\leq O\left(\frac{1}{\log F(M_d)}\right) + \sum_{0 \leq j < d}\sum_{f \in H_j}\sum_{A_f \in \mathrm{Atom}(\mathcal{B}_f)}O\left(\frac{1}{\log F(M_j)}\right)\end{align}$

と評価できる。各 $0 \leq j < d, f \in H_j$ に対して $\#\mathrm{Atom}(\mathcal{B}_f)\leq 2^{\mathrm{cpx}(\mathcal{B}_f)} \leq 2^{M_j}$ なので、

$\displaystyle \mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) \leq \max_{0 \leq j \leq d}O_{M_j, \#J}\left(\frac{1}{\log F(M_j)}\right)$

が得られるが、 $M_j$ 達の中で $M_d$ が最小であることから、 $F$ が $\#J$ に依存して十分成長速度が速ければ

$\mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) =o_{M_d \to \infty; \#J}(1)$

が成り立つことがわかる。後でわかるように $\delta \to 0$ であれば $M_d \to 0$ となるように $M_d$ は選択されるため、

$\mathbb{E}(\mathbf{1}_{E_e\setminus E_e'}) =o_{\delta \to \infty; \#J}(1)$

が示されたことになる。後は示すべきことは $\displaystyle \bigcap_{e \in H_d}E_e' = \emptyset$ のみである。そこで、 $\displaystyle \bigcap_{e \in H_d}E_e' \neq \emptyset$ と仮定して、 $\displaystyle \bigcap_{e \in H_d}E_e'$ に含まれるアトムを一つとる。 $\displaystyle \bigcap_{e \in H_d}E_e' \in \bigvee_{f \in \mathcal{H}\setminus H_d}\mathcal{B}_f$ なので、それは $\displaystyle \bigcap_{f \in \mathcal{H}\setminus H_d}A_f$ という形をしている( $A_f \in \mathrm{Atom}(\mathcal{B}_f)$ )。この $A_f$ 達を固定した上で、 $e \in H_d$ に対しては $A_e:=E_e$ とする。このとき、 $\displaystyle \bigcap_{e \in \mathcal{H}}A_e$ はgoodではない。

理由: goodであったと仮定すると、カウンティング補題より $F$ が $\#J$ に依存して十分成長速度が速ければ

$\displaystyle \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr) = \left(1+o_{M_d \to \infty; \#J}(1)\right)\prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) + O_{\#J, M_0}\left(\frac{1}{F(M_0)}\right)$

が成り立つ。goodの定義の①より $0 \leq j \leq d$ および $e \in H_j$ に対して

$\displaystyle \mathbb{E}\Bigr(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) = \frac{\mathbb{E}\Bigl(\mathbf{1}_{A_e}\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr)}{\mathbb{E}\Bigl(\prod_{f \in \partial e}\mathbf{1}_{A_f}\Bigr)} \geq \frac{1}{\log F(M_j)}$

が成り立つので、 $F$ が $\#J$ に依存して十分成長速度が速ければ

$\displaystyle \prod_{e \in \mathcal{H}}\mathbb{E}\Bigl(\mathbf{1}_{A_e} \ \Big| \ \bigcap_{f \in \partial e}A_f\Bigr) \geq \frac{1}{(\log F(M_0) )^{\#\mathcal{H}}} \geq \frac{1}{\sqrt{F(M_0)}}$

と評価できる。 $O_{\#J, M_0}$ の定数を $c(\#J, M_0)$ とすれば、 $F$ が $\#J$ に依存して十分成長速度が速く、 $M_d$ が $\#J$ に依存して十分大きければ

$\displaystyle\mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr)\geq \frac{1}{2\sqrt{F(M_0)}}-\frac{c(\#J, M_0)}{F(M_0)} \geq \frac{1}{3\sqrt{F(M_0)}}$

を得る。 $F$ はこの時点で決定されている。 $F(M_0)=O_{\#J, M_d, F}(1) = O_{\#J, M_d}(1)$ なので、 $M_d \geq {}^{\exists}N(\#J)$ であれば、或る $C(\#J, M_d) > 0$ が存在して

$\displaystyle\mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr)\geq C(\#J, M_d)$

が成り立つことがわかった。整数 $M_d \geq N(\#J)$ に対する関数 $C(\#J, M_d) (< 1)$ は狭義単調減少かつ $\displaystyle \lim_{M_d \to \infty}C(\#J, M_d) = 0$ であると仮定してよい。 $\delta$ に対する $M_d$ の選択は、 $M_d \geq N(\#J)$ かつ

$\displaystyle C(\#J, M_d) > \delta \geq C(\#J, M_d+1)$

を満たすものと定める。 $\delta$ が( $\#J$ に依存して)大きいとこのような $M_d$ は決まらないが、目標に $\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e \setminus E_e'}\right) = o_{\delta \to 0; \#J}(1)$ という漸近挙動がある以上、そのような $\delta$ については $E_e':=\emptyset, M_d=1$ と考えて問題ない。そうして、

$\displaystyle C(\#J, M_d) \leq \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in \mathcal{H}}A_e}\Bigr) \leq \mathbb{E}\Bigl(\mathbf{1}_{\bigcap_{e \in H_d}E_e} \Bigr) \leq \delta$