Folkmanの定理(Folkman's theorem)とは、正の整数 $k,r$ に対し十分大きな $n$ があって、$\{1,\dots,n\}$ をどう $r$ 色に塗っても、$k$ 元集合 $A$ で、$A$ の空でない部分集合の元の和がすべて $n$ 以下で同じ色になるものがとれる、という有限の Ramsey 型の定理である。Folkman グラフやグラフの塗り分けの Folkman 数とは別の対象である。定理は van der Waerden の定理と鳩の巣原理から示せ、$k=2$ は $x\ne y$ を要求する Schur の定理、無限版は Hindman の定理にあたる。2 色で $k=2$ の最小の $n$ は 9 で、2 色の場合の最小の $n$ は $k$ について少なくとも 2 重指数的に増える。
前提知識: van der Waerdenの定理, 鳩の巣原理, Schurの定理(和のない集合)
Folkmanの定理(Folkman's theorem)は、色の数 $r$ と個数 $k$ を決めると十分大きな $n$ があって、$\{1,2,\dots,n\}$ をどう $r$ 色に塗っても、$k$ 個の相異なる正の整数で、それらから選んだ空でない部分集合の元の和がすべて $n$ 以下で同じ色になるものがとれる、という有限の Ramsey 型の定理である。グラフ理論の Folkman グラフ(頂点数 20 の、辺推移的だが頂点推移的でない正則グラフ)や、グラフの辺や頂点の塗り分けについての Folkman 数(指定した完全グラフを含まないのに、どう塗り分けても単色の完全グラフを含むグラフの頂点数の最小値)とは別の対象である。ただし、この記事の定理に現れる最小の $n$ も Folkman 数と呼ばれることがある(BENTW17 p. 2)。
この定理は Folkman、Rado、Sanders がそれぞれ独立に得た(帰属は BENTW17 p. 1 による)。$k=2$ の場合は $x,y,x+y$($x\ne y$)が同じ色になることで、Schurの定理(和のない集合) を $x\ne y$ を要求する形に強めたものである。無限個の数についての形が Hindmanの定理 である。この記事では、van der Waerdenの定理 だけを使う有限の証明をすべて展開し、Hindman の定理から有限の形が従うことも示す。最後に、最小の $n$ の大きさについて知られていることと、小さな場合の値を述べる。
以下、$[n]:=\{1,2,\dots,n\}$ とし、$[n]$ を $r$ 色に塗るとは写像 $c\colon[n]\to\{1,\dots,r\}$ を与えることとする。
正の整数の有限集合 $A$ に対し、$A$ の空でない部分集合 $B$ の元の和全体を
$$
S(A):=\Bigl\{\sum_{x\in B}x\ \Bigm|\ \emptyset\ne B\subseteq A\Bigr\}
$$
と書く。$A$ の元は相異なり、和をとる $B$ の元も相異なる。
正の整数 $k,r$ に対し、次をみたす正の整数 $n$ が存在する:$[n]$ をどう $r$ 色に塗っても、$k$ 元集合 $A\subseteq[n]$ で、$S(A)\subseteq[n]$ かつ $S(A)$ が単色であるものがある。
このような $n$ の最小値を $F(k,r)$ と書く。主張は BENTW17 p. 1 の形に合わせた。$[n]$ を塗ったとき $n$ を超える和には色がないので、$S(A)\subseteq[n]$ を要求する。証明は次節の prf-folkman-main で与える。
$F(k,r)$ は $k$ についても $r$ についても単調に(広い意味で)増える。$r$ については、$r$ 色の塗り分けは $r+1$ 色の塗り分けでもあるからである。$k$ については、$k$ 元の $A$ がとれれば、その $k-1$ 元の部分集合 $A'$ についても $S(A')\subseteq S(A)$ は単色である。
$k=1$ では $A=\{1\}$ がとれるので $F(1,r)=1$ である。$k=2$ では $A=\{x,y\}$($x\ne y$)について $S(A)=\{x,y,x+y\}$ なので、主張は「$x\ne y$ で $x,y,x+y\le n$ が同じ色」という Schur 型の主張になる。$k$ が大きくなると、単色でなければならない和の個数は最大 $2^k-1$ 個に増える。
van der Waerdenの定理 によれば、正の整数 $r,\ell$ に対し、$[N]$ をどう $r$ 色に塗っても単色の長さ $\ell$ の等差数列 $a,a+d,\dots,a+(\ell-1)d$($a\ge1$、公差 $d\ge1$)がとれるような $N$ がある。その最小値を $W(r,\ell)$ と書く。
証明の要点は、まず「和の色が、使った数のうち最も大きいものだけで決まる」数の列を作り、そのあと鳩の巣原理で色をそろえることである。
正の整数 $r,M$ に対し、正の整数 $N=N(r,M)$ があって次が成り立つ:$[N]$ をどう $r$ 色に塗っても、正の整数 $x_1,\dots,x_M$ で
条件 1 から、$F\ne F'$ なら $\sum_{i\in F}x_i\ne\sum_{i\in F'}x_i$ である($F$ と $F'$ の対称差の最小の添字 $j$ をとり、それが $F$ に入っているとすると、$x_j$ がそれより後ろのすべての $x_i$ の和より大きいので、$F$ の側の和が大きい)。条件 3 の「$\min F$」は、$x_i$ が減少列なので「$F$ に対応する数のうち最大のもの」である。
$M$ についての帰納法による。$M=1$ では $N=1$、$x_1=1$ とすればよい(条件 1 と 3 は自明)。
$M\ge2$ とし、$L:=N(r,M-1)$、$N:=W(r,2L+1)$ とおく。$[N]$ の $r$ 色の塗り分け $c$ を与える。van der Waerden の定理により、単色の等差数列 $a,a+d,\dots,a+2Ld$($a\ge1$、$d\ge1$、$a+2Ld\le N$)がとれる。その色を $\delta$ とする。とくに $dL< a+2Ld\le N$ なので、$t\in[L]$ について $dt\in[N]$ であり、$[L]$ の $r$ 色の塗り分け $c'(t):=c(dt)$ が定まる。
帰納法の仮定を $c'$ に使い、添字を 1 つずらして $y_2,\dots,y_M$ をとる。すなわち、$y_j>\sum_{i>j}y_i$($2\le j\le M$)、$\sum_{i\ge2}y_i\le L$ で、空でない $G\subseteq\{2,\dots,M\}$ について $\sum_{i\in G}y_i$ の $c'$ による色が $\min G$ だけで決まる。
$x_1:=a+Ld$、$x_i:=dy_i$($i\ge2$)とおき、3 つの条件を確かめる。
$M:=r(k-1)+1$、$n:=N(r,M)$ とおき、$[n]$ の $r$ 色の塗り分けに lem-folkman-chain を使って $x_1,\dots,x_M$ をとる。$\chi(j)$ を、$\min F=j$ となる $F$ についての $\sum_{i\in F}x_i$ の色(条件 3 によりこれは $F$ によらず、たとえば $x_j$ の色に等しい)とする。
$M=r(k-1)+1$ 個の添字が $r$ 色に分かれるので、鳩の巣原理 により $k$ 個の添字 $j_1< \dots< j_k$ で $\chi$ の値が等しいものがある。その共通の値を $\gamma$ とし、$A:=\{x_{j_1},\dots,x_{j_k}\}$ とおく。条件 1 から $x_i$ は相異なるので $|A|=k$ である。
空でない $B\subseteq A$ は、空でない $F\subseteq\{j_1,\dots,j_k\}$ と $B=\{x_i\mid i\in F\}$ で対応する。$\min F$ はいずれかの $j_l$ なので、$\sum_{x\in B}x=\sum_{i\in F}x_i$ の色は $\chi(\min F)=\gamma$ である。また和はどれも $x_1+\dots+x_M\le n$ 以下なので $S(A)\subseteq[n]$ である。よって $S(A)$ は色 $\gamma$ の単色の部分集合である。$\square$
証明から $F(k,r)\le N(r,r(k-1)+1)$ である。帰納の各段が van der Waerden 数を 1 回使うので、この上界は van der Waerden 数を $r(k-1)$ 回入れ子にしたもので、非常に大きい。
| 段 | 使う道具 | 得るもの |
|---|---|---|
| $M=1$ | なし | $x_1=1$ |
| $M-1\to M$ | 長さ $2L+1$ の単色の等差数列と、公差 $d$ 倍による塗り直し | $x_1=a+Ld$、$x_i=dy_i$ |
| 最後 | 鳩の巣原理($M=r(k-1)+1$) | 同じ色の $k$ 個の添字 |
$r=2$、$M=2$ とする。$N(2,1)=1$ なので $L=1$ で、長さ $2L+1=3$ の等差数列を使う。$[9]$ をどう 2 色に塗っても単色の 3 項の等差数列があり($W(2,3)=9$。$2^9$ 通りの塗り分けを調べれば確かめられる)、$N(2,2)=9$ ととれる。
$[9]$ を奇数と偶数で 2 色に塗ると、たとえば $1,3,5$($a=1$、$d=2$)が単色の等差数列である。$x_1:=a+Ld=3$、$[1]$ の塗り直し $c'(1)=c(2)$ に対して $y_2:=1$、$x_2:=dy_2=2$ となる。$x_1$ を含む和 $3$ と $3+2=5$ はどちらも奇数で等差数列の項であり、$x_2$ だけの和 $2$ は偶数である。和の色は $\min F$ だけで決まり、$x_1=3>2=x_2$、$x_1+x_2=5\le9$ である。
この証明の形は、最初の数 $x_1$ を単色の等差数列の中央の項にとり、残りの数を公差の倍数として作ることで、「$x_1$ を含む和」をすべて等差数列の中に閉じこめるところにある。等差数列の長さを $2L+1$ にするのは、$x_1$ をほかの数の和より大きくして和をすべて相異なるようにするためで、和の色だけなら長さ $L+1$ で足りる($x_1:=a$ とすればよいが、このとき $x_1$ が $x_i$ のどれかと等しくなりうる)。
Hindmanの定理 は、$\mathbb N=\{1,2,\dots\}$ をどう有限個の色に塗っても、無限集合 $H$ で $H$ の相異なる有限個の元の和がすべて同じ色になるものがある、という主張である。そこから $H$ の小さい方から $k$ 個をとれば、ある $n$ について $S(A)\subseteq[n]$ が単色になる。ただし Folkman の定理は、$n$ が塗り分けによらず $k,r$ だけで決まることを主張している。この一様性は、塗り分けの列から部分列をとるコンパクト性の議論で得られる。
Hindmanの定理 を認めると、thm-folkman-main が従う。
$k,r$ について主張が成り立たないとする。すると各 $n$ について、$[n]$ の $r$ 色の塗り分け $c_n$ で、$S(A)\subseteq[n]$ が単色になる $k$ 元集合 $A\subseteq[n]$ がないものがある。$c_n(1)$ の値は $r$ 通りなので、無限個の $n$ で $c_n(1)$ が等しい。その中の無限個の $n$ で $c_n(2)$ も等しい。これを続けて($c_n(m)$ が定義される $n\ge m$ の中から選んで)入れ子の無限集合 $I_1\supseteq I_2\supseteq\cdots$、$I_m\subseteq\{m,m+1,\dots\}$ をとり、$c(m):=$($n\in I_m$ についての $c_n(m)$ の共通の値)と定めると、$c$ は $\mathbb N$ の $r$ 色の塗り分けで、各 $m$ について、$n\in I_m$ なら $c_n$ と $c$ は $[m]$ の上で一致する。
Hindman の定理により、無限集合 $H$ で和がすべて同じ色のものがある。$H$ の小さい方から $k$ 個をとって $A$ とし、$m:=\sum_{x\in A}x$ とおく。$S(A)\subseteq[m]$ である。$n\in I_m$ を $n\ge m$ となるようにとると、$c_n$ は $[m]$ の上で $c$ と一致するので、$A\subseteq[n]$、$S(A)\subseteq[n]$ は $c_n$ について単色であり、$c_n$ のとり方に反する。$\square$
逆に、Folkman の定理を各 $k$ ごとに使っても、一つの無限集合 $H$ は得られない。各 $k$ で得られる $A$ が互いに無関係でよく、$k$ 元の $A$ を $k+1$ 元に延ばせる保証がないからである。Hindman の定理の証明には、超フィルターの空間の冪等元などの、本質的に無限の道具が使われる。
$k=2$、$r=2$ では $F(2,2)=9$ である。$n=8$ では、$[8]$ を
$$
\{1,2,4,8\},\qquad\{3,5,6,7\}
$$
の 2 色に塗ると、どちらの組にも相異なる $x,y$ で $x+y$ が同じ組に入るものがない。一方 $[9]$ のどの 2 色の塗り分けにも、$x\ne y$ で $x,y,x+y\le9$ が同じ色のものがある。これは $2^9$ 通りの塗り分けをすべて調べる有限の計算で確かめられる(上の塗り分けは、1 の色を固定したとき $[8]$ で条件をみたす唯一のものでもある)。最初の組では $4+4=8$ が同じ組に入っており、和をとる元が相異なることが効いている。
2 色の場合 $F(k):=F(k,2)$ について、Erdős と Spencer は一様な無作為な塗り分けを使い、ある定数 $c>0$ について $F(k)\ge2^{ck^2/\log k}$ を示した(帰属は BENTW17 p. 2)。BENTW17 の Theorem 1.1(p. 2)は、これを
$$
F(k)\ge2^{2^{k-1}/k}\qquad(k\ge1)
$$
に改良した。証明(p. 3)は、奇数だけを無作為に 2 色に塗り、残りは「$2x$ の色は $x$ の色と違う」という規則で決める塗り分けを使う。この塗り分けで $S(A)$ が単色になるには和がすべて相異なる必要があることが、次の命題である。
$[n]$ の塗り分け $c$ が、$2x\le n$ となるすべての $x$ について $c(2x)\ne c(x)$ をみたすとする。$k$ 元集合 $A$ について $S(A)\subseteq[n]$ が単色なら、$A$ の $2^k-1$ 個の空でない部分集合の和はすべて相異なる。
相異なる空でない $B_1,B_2\subseteq A$ で和が等しいものがあるとする。$B_1\subsetneq B_2$ なら和は $B_2\setminus B_1$ の元の分だけ大きいので、どちらも他方を含まない。$B_1':=B_1\setminus B_2$、$B_2':=B_2\setminus B_1$ は空でなく、互いに素で、和は等しい(共通部分の寄与を両方から引いた)。その和を $s$ とすると $s\in S(A)$ かつ $B_1'\cup B_2'$ の和 $2s\in S(A)\subseteq[n]$ であり、$c(2s)\ne c(s)$ なので $S(A)$ は単色でない。$\square$
BENTW17 p. 4 は、上界の側で最良に知られているものが塔の形($2^{2^{\cdot^{\cdot^{\cdot}}}}$ の形)の増え方であることを述べている。下界と上界の間には大きな開きが残っている。
$k=2$ の主張は、$[n]$ を $r$ 色に塗ると $x\ne y$ で $x,y,x+y$ が同じ色のものがある、というものである。Schurの定理(和のない集合) は $x=y$ を許す形で、その場合は $x,x,2x$ の 2 数が同じ色であればよい。ex-folkman-small の塗り分けでは $4$ と $8$ が同じ色なので、$x=y$ を許すと $n=8$ でも単色の組がある。
上の $\{1,2,4,8\}$、$\{3,5,6,7\}$ の塗り分けは $F(2,2)>8$ を示す。もっと小さい $n=4$ では、$\{1,4\}$、$\{2,3\}$ の塗り分けで、どちらの組でも 2 数の和 $5$ が $[4]$ の外にあり、単色の $S(A)$($|A|=2$)がない。
次の表の各行は、仮定を 1 つだけ外すと結論が成り立たなくなる例である。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 色の数 $r$ を $n$ によらず固定する(thm-folkman-main) | $[n]$ の各数を相異なる色に塗る($r=n$) | どの $n$ でも、2 元以上の $A$ では $A$ の 2 元の色が違い、$S(A)$ は単色にならない |
| $n$ が十分大きい(thm-folkman-main) | $k=r=2$、$n=8$ で $\{1,2,4,8\}$ と $\{3,5,6,7\}$ | 2 元集合 $A$ で $S(A)\subseteq[8]$ が単色のものがない |
| 和をとる元が相異なる(def-folkman-sums) | $c(x)$ を $x$ の素因数分解での 2 の指数の偶奇とする | 同じ元を 2 回足すことを許すと和の集合は $x$ と $2x$ を含むが、2 の指数が 1 ずれるので色が違い、どの $n\ge2$ でも 1 元の $A$ ですら単色にならない |
| 単色にする集合が色の組の 1 つであること(大きさの条件だけにする) | $[n]$ の奇数全体(約半分) | 相異なる奇数の和は偶数なので、2 元の $A$ で $S(A)$ が奇数だけからなるものはない |
2 行目は、$F(2,2)=9$ のうち $F(2,2)>8$ の側である。3 行目の塗り分けは prop-folkman-doubling の条件をみたす塗り分けの例でもあり、BENTW17 の下界の構成はこの規則を奇数の上の無作為な塗り分けと組み合わせている。4 行目は、Folkman の定理が「大きな集合はどれも $S(A)$ を含む」という密度の主張ではないことを示す。奇数と偶数の 2 色の塗り分けでは、$S(A)$ は偶数の組の中にとれる(たとえば $A=\{2,4,8,\dots,2^k\}$、$n\ge2^{k+1}-2$)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する