インテジャーズ

INTEGERS

数、特に整数に関する記事。

セメレディの定理の組合せ論的証明ー2

弱正則化補題 (Frieze, Kannan) \mathbf{V}, \mathbf{W}を有限集合とし、\varepsilon > 0および\mathbf{E} \subset \mathbf{V} \times \mathbf{W}をとる。このとき、A, B=O_{\varepsilon}(1), a \in [A], b \in [B]毎に0 \leq d_{a, b} \leq 1, 分割
\begin{align} \mathbf{V} &= \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A \\ \mathbf{W} &= \mathbf{W}_1 \sqcup \cdots \sqcup \mathbf{W}_B\end{align}
が存在して、任意の\mathbf{F} \subset \mathbf{V}, \mathbf{G} \subset \mathbf{W}に対して
\displaystyle \left| \#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} - \sum_{a \in [A]}\sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\}\right| \leq \varepsilon \#\mathbf{V}\cdot \#\mathbf{W}
が成り立つ。

これは次の記事で証明する。ここでは、後で使う系を導出する。

\mathbf{V}, \mathbf{W}を有限集合とし、\varepsilon > 0およびw \in \mathbf{W}毎に\mathbf{E}_w \subset \mathbf{V}をとる。このとき、A=O_{\varepsilon}(1), a \in [A], w \in \mathbf{W}毎に0 \leq c_{a, w} \leq 1, 分割
\displaystyle \mathbf{V} = \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A
が存在して、任意の\mathbf{F} \subset \mathbf{V}に対して
\displaystyle \left| \#\{\mathbf{F} \cap \mathbf{E}_w\} - \sum_{a \in [A]}c_{a, w}\#\{\mathbf{F}\cap \mathbf{V}_a\}\right| \leq \varepsilon \#\mathbf{V}
が高々\varepsilon \#\mathbf{W}個のw \in \mathbf{W}を除いて成立する。

証明. \mathbf{E}:=\{(v, w) \in \mathbf{V} \times \mathbf{W} \mid v \in \mathbf{E}_w \}とし、\varepsilon \mapsto \varepsilon^2/2として弱正則化補題を適用する。すると、A, B=O_{\varepsilon}(1), a \in [A], b \in [B]毎に0 \leq d_{a, b} \leq 1, 分割

\begin{align} \mathbf{V} &= \mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A \\ \mathbf{W} &= \mathbf{W}_1 \sqcup \cdots \sqcup \mathbf{W}_B\end{align}

が存在して、任意の\mathbf{F} \subset \mathbf{V}, \mathbf{G} \subset \mathbf{W}に対して

\displaystyle \left| \#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} - \sum_{a \in [A]}\sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\}\right| \leq \frac{\varepsilon^2}{2} \#\mathbf{V}\cdot \#\mathbf{W}

が成り立つ。a \in [A], b \in [B], w \in \mathbf{W}_bのとき c_{a, w}:=d_{a, b}と定義する。\mathbf{E}の定義から

\displaystyle \#\{(\mathbf{F}\times \mathbf{G}) \cap \mathbf{E}\} = \sum_{w \in \mathbf{G}}\#\{\mathbf{F} \cap \mathbf{E}_w\}

が成り立ち、a \in [A]に対して

\displaystyle \sum_{b \in [B]}d_{a, b}\#\{\mathbf{F} \cap \mathbf{V}_a\}\cdot \#\{\mathbf{G} \cap \mathbf{W}_b\} = \sum_{w \in \mathbf{G}}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\}

が成り立つので、

\displaystyle \left|\sum_{w \in \mathbf{G}}\left(\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\}\right) \right| \leq \frac{\varepsilon^2}{2}\#\mathbf{V} \cdot \#\mathbf{W}

と書き直すことができる。これを、\mathbf{G}として

\begin{align} \mathbf{G}^{+} &:= \left\{w \in \mathbf{W} \ \left| \ \#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} > 0 \right\}\right. \\ \mathbf{G}^{-} &:= \left\{w \in \mathbf{W} \ \left| \ \#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} < 0 \right\}\right. \end{align}

のそれぞれに適用して足し合わせると

\displaystyle \sum_{w \in \mathbf{W}}\left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon^2\#\mathbf{V} \cdot \#\mathbf{W}

を得る。

\begin{align} &\varepsilon \#\mathbf{V} \cdot \#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \geq \varepsilon \#\mathbf{V}\right\} \right. \\ &= \sum_{w \in \mathbf{W}}\varepsilon\#\mathbf{V} \cdot \mathbf{1}_{\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \geq \varepsilon \#\mathbf{V}\right\} \right.}(w)\\ &\leq \sum_{w \in \mathbf{W}}\left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon^2\#\mathbf{V} \cdot \#\mathbf{W}\end{align}

と不等式評価できるので

\begin{align} &\#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| \leq \varepsilon \#\mathbf{V}\right\} \right. \\ &\geq \#\left\{ w \in \mathbf{W} \ \left| \ \left|\#\{\mathbf{F} \cap \mathbf{E}_w\}-\sum_{a \in [A]}c_{a, w}\#\{\mathbf{F} \cap \mathbf{V}_a\} \right| < \varepsilon \#\mathbf{V}\right\} \right. \geq (1-\varepsilon) \#\mathbf{W}\end{align}


が得られ、これが主張していたことであった。 Q.E.D.

最後の不等式評価はMarkovの不等式およびその証明そのものである。今後は同じ変形は省略する。