Ramsey数 R(3,3)=6
概要
Ramsey数 R(3,3)=6（Ramsey number $R(3,3)=6$）とは、6 頂点の完全グラフ $K_6$ の辺をどう赤と青の 2 色に塗り分けても 3 辺が同じ色の三角形ができ、5 頂点ではそうとは限らない（五角形の辺を赤、対角線を青に塗ると同じ色の三角形がない）という事実である。「6 人いれば、互いに知り合いの 3 人か、互いに知らない 3 人がいる」とも言える。証明は、1 つの頂点から出る 5 本の辺のうち 3 本が同じ色であることによる。さらに、$K_6$ をどう塗り分けても同じ色の三角形は 2 つ以上あり、これは色の違う 2 辺の組を数えて示せる。3 色に塗る場合は 6 頂点でも同じ色の三角形ができないことがある。
前提知識: 一筆書きとグラフ, 場合の数の数え方の体系
高校での出発点：6 人の中の 3 人
6 人が集まると、その中に「3 人とも互いに知り合い」の 3 人か、「3 人とも互いに知らない」の 3 人が、必ずいる。どの 2 人についても「知り合い」か「知らない」かのどちらかに決まっているとすると、6 人の関係がどうであっても、このどちらかが起こる。5 人では、そうとは限らない。
人を頂点とし、どの 2 人の間にも辺を引いて、知り合いなら赤、知らないなら青に塗ると、これは「辺を 2 色に塗った図の中に、3 辺とも同じ色の三角形があるか」という問題になる。
6 人 $1$〜$6$ で、知り合いの組が
$$
\{1,2\},\ \{1,3\},\ \{1,4\},\ \{2,5\},\ \{2,6\},\ \{3,5\},\ \{4,6\},\ \{5,6\}
$$
の 8 組だけで、ほかの $15-8=7$ 組は互いに知らないとする（6 人から 2 人を選ぶ組は $\binom62=15$ 組）。
人 $2$ の知り合いは $1$、$5$、$6$ の 3 人である。この 3 人の間の組 $\{1,5\}$、$\{1,6\}$、$\{5,6\}$ を見ると、$\{5,6\}$ が知り合いなので、$2$、$5$、$6$ は互いに知り合いの 3 人である（$\{2,5\}$、$\{2,6\}$、$\{5,6\}$ がどれも知り合い）。
人 $2$ が知らない人は $3$、$4$ の 2 人で、$\{3,4\}$ も知らない組なので、$2$、$3$、$4$ は互いに知らない 3 人である（$\{2,3\}$、$\{2,4\}$、$\{3,4\}$ がどれも知らない組）。この例では、両方が見つかる（図 1）。
6 人の関係。赤の実線は知り合い、青の破線は知らない組。太い赤の三角形 2、5、6 と太い青の三角形 2、3、4 が同じ色の三角形
ex-ram-party では人 $2$ から出る 5 本の辺を見て 3 人を見つけた。この見方がいつも使えることを示すのが、この記事の中心である。この記事で答える問いは次の 3 つである。
- 6 人ならいつでも見つかるのはなぜか。5 人ではなぜ足りないか。→ thm-ram-main
- 見つかる 3 人の組は、いくつあるか。→ thm-ram-two
- 人数・色の数・求める人数を変えるとどうなるか。→ ex-ram-cx-three、rem-ram-general
高校の言葉 この記事の言葉 大学の言葉 どの 2 人も線で結んだ図 完全グラフ $K_n$ 完全グラフ 知り合い・知らないで線を塗り分ける 辺の 2 色の塗り分け 辺の 2 彩色 互いに知り合いの 3 人／互いに知らない 3 人 同じ色の三角形 単色の $K_3$ 必ず見つかる最小の人数 $R(3,3)$ Ramsey 数 5 本の線のうち 3 本は同じ色 鳩の巣原理 鳩の巣原理
言葉の準備：完全グラフと 2 色の塗り分け
$n$ 個の頂点をもち、どの 2 頂点もちょうど 1 本の辺で結ばれたグラフを、$n$ 頂点の 完全グラフ といい、$K_n$ と書く。$K_n$ の辺の数は $\binom n2=\dfrac{n(n-1)}2$ である。
$K_n$ の各辺を赤か青のどちらかに塗ることを、2 色の塗り分け という。3 頂点 $x$、$y$、$z$ を結ぶ 3 辺 $xy$、$yz$、$zx$ がすべて同じ色のとき、三角形 $xyz$ を 同じ色の三角形 という（3 辺とも赤なら赤い三角形、3 辺とも青なら青い三角形）。
- $K_3$ の辺は $3$ 本で、塗り分けは $2^3=8$ 通りある。3 辺とも赤か 3 辺とも青の $2$ 通りだけで、同じ色の三角形ができる。
- $K_4$ の辺は $\binom42=6$ 本で、塗り分けは $2^6=64$ 通り、三角形は $\binom43=4$ 個ある。
- $K_6$ の辺は $\binom62=15$ 本で、塗り分けは $2^{15}=32768$ 通り、三角形は $\binom63=20$ 個ある。32768 通りを 1 つずつ調べる代わりに、1 つの証明ですべてを片づけるのが thm-ram-main である。
$K_n$ の 2 色の塗り分けを どう選んでも 同じ色の三角形ができる、という性質をもつ最小の $n$ を $R(3,3)$ と書き、Ramsey 数 $R(3,3)$ という。
$R(3,3)$ が定まるためには、この性質をもつ $n$ が少なくとも 1 つあることを示す必要がある。それも thm-ram-main で示す。
証明の出発点は、次の簡単な数え方である。「5 羽の鳩が 2 つの巣に入ると、どちらかの巣には 3 羽以上いる」という形なので、鳩の巣原理 の 1 つの場合である（一般の形は 鳩の巣原理）。
5 本の辺をそれぞれ赤か青に塗ると、赤の辺が 3 本以上あるか、青の辺が 3 本以上ある。
背理法で示す。赤の辺も青の辺も 2 本以下だとすると、辺は全部で $2+2=4$ 本以下になる。これは辺が 5 本あることに反する。
赤の本数を $r$ とすると、青の本数は $5-r$ である。$(r,5-r)$ は $(0,5)$、$(1,4)$、$(2,3)$、$(3,2)$、$(4,1)$、$(5,0)$ の 6 通りで、どれも一方が $3$ 以上である。一方、4 本の辺なら $(2,2)$ のように、どちらも 3 本未満にできる。
主定理 1：$R(3,3)=6$
- $K_6$ の辺をどう 2 色に塗り分けても、同じ色の三角形ができる。
- $K_5$ の辺には、同じ色の三角形ができない 2 色の塗り分けがある。
したがって $R(3,3)=6$ である。
- の塗り分けは次のとおりである。5 つの頂点 $1,2,3,4,5$ を正五角形の頂点に並べ、五角形の辺（$12$、$23$、$34$、$45$、$51$）を赤に、対角線（$13$、$35$、$52$、$24$、$41$。つながると五芒形になる）を青に塗る（図 2）。番号で言うと、2 頂点 $i$、$j$ の番号の差 $j-i$ を $5$ で割った余りが $1$ か $4$ なら赤、$2$ か $3$ なら青である。
K5 の塗り分け。五角形の辺が赤の実線、対角線が青の破線で、同じ色の三角形がない
K6 の頂点 v から出る 5 本の辺のうち、赤の 3 本の先を x、y、z とする。x、y、z の間の 3 辺の色で場合を分ける
- の証明．$K_6$ の 2 色の塗り分けを 1 つとる。頂点を 1 つ選んで $v$ とする。$v$ からは、残りの 5 頂点へ 5 本の辺が出ている。lem-ram-pigeon より、赤の辺が 3 本以上あるか、青の辺が 3 本以上ある。
赤の辺が 3 本以上ある場合．そのうち 3 本を $vx$、$vy$、$vz$ とする（図 3）。3 頂点 $x$、$y$、$z$ の間の 3 辺 $xy$、$yz$、$zx$ の色を見る。
- どれか 1 本、たとえば $xy$ が赤なら、三角形 $vxy$ の 3 辺 $vx$、$vy$、$xy$ はすべて赤で、赤い三角形である。$yz$ や $zx$ が赤のときも同じく、三角形 $vyz$ や $vzx$ が赤い三角形になる。
- 3 本とも赤でない、つまり 3 本とも青なら、三角形 $xyz$ が青い三角形である。
どちらの場合も同じ色の三角形がある。
青の辺が 3 本以上ある場合．上の議論で赤と青を入れかえると、同じように、青い三角形 $vxy$（などの 1 つ）か赤い三角形 $xyz$ がある。
- の証明．上の塗り分けで、赤の辺だけを見ると、各頂点 $i$ と赤で結ばれているのは、番号の差が $\pm1$ の 2 頂点 $i-1$、$i+1$（番号は $5$ で割った余りで考える）である。赤い三角形 $xyz$ があったとすると、$y$ と $z$ はどちらも $x$ と赤で結ばれているので、$\{y,z\}=\{x-1,x+1\}$ である。ところが $y$ と $z$ の番号の差は $(x+1)-(x-1)=2$ で、$yz$ は青である。これは $yz$ が赤であることに反する。よって赤い三角形はない。
青の辺だけを見ると、各頂点 $i$ と青で結ばれているのは、番号の差が $\pm2$ の 2 頂点 $i-2$、$i+2$ である。青い三角形 $xyz$ があったとすると $\{y,z\}=\{x-2,x+2\}$ で、$y$ と $z$ の番号の差は $4$、$5$ で割った余りが $4$ なので $yz$ は赤である。これは $yz$ が青であることに反する。よって青い三角形もない。
$R(3,3)=6$ であること．$n\ge6$ なら、$K_n$ の塗り分けから 6 つの頂点を選ぶと、その 6 頂点の間の辺は $K_6$ の塗り分けになり、(1) より同じ色の三角形がある。$n=3,4,5$ なら、(2) の塗り分けの 5 頂点から $n$ 個を選び、その間の辺の色をそのまま使うと、同じ色の三角形のない $K_n$ の塗り分けになる（(2) の塗り分けに同じ色の三角形がないので、その一部にもない）。$n=1,2$ では三角形がそもそもない。よって、どう塗り分けても同じ色の三角形ができる最小の $n$ は $6$ である。
$K_5$ の三角形は $\binom53=10$ 個ある。(2) の塗り分けで、各三角形の赤の辺と青の辺の本数を数えると次のとおりで、どれも 2 色が混ざっている。
| 三角形 | 赤 | 青 | 三角形 | 赤 | 青 |
|---|---|---|---|---|---|
| $123$ | $2$ | $1$ | $135$ | $1$ | $2$ |
| $124$ | $1$ | $2$ | $145$ | $2$ | $1$ |
| $125$ | $2$ | $1$ | $234$ | $2$ | $1$ |
| $134$ | $1$ | $2$ | $235$ | $1$ | $2$ |
| $245$ | $1$ | $2$ | $345$ | $2$ | $1$ |
たとえば三角形 $123$ は、辺 $12$（差 $1$、赤）、$23$（差 $1$、赤）、$13$（差 $2$、青）である。
5 人の場合は、5 人が輪になって座り、隣の人とだけ知り合いという関係が (2) の塗り分けにあたる。この 5 人には、互いに知り合いの 3 人も、互いに知らない 3 人もいない。
ex-ram-party の 6 人で、(1) の証明をたどる。$v=1$ とすると、人 $1$ から出る 5 本の辺は、$2$、$3$、$4$ へ赤（知り合い）、$5$、$6$ へ青である。赤が 3 本なので $x=2$、$y=3$、$z=4$ とする。3 辺 $23$、$34$、$24$ はどれも青（知らない組）なので、三角形 $234$ が青い三角形である。
$v=2$ とすると、赤が $1$、$5$、$6$ への 3 本で、3 辺 $15$、$16$、$56$ のうち $56$ が赤なので、三角形 $256$ が赤い三角形である。選ぶ頂点によって、見つかる三角形が違ってよい。
主定理 2：同じ色の三角形は 2 つ以上ある
ex-ram-party では、同じ色の三角形が 2 つ見つかった。実は、$K_6$ をどう塗り分けても、同じ色の三角形は 1 つだけでは終わらない。
$K_6$ の辺をどう 2 色に塗り分けても、同じ色の三角形は 2 つ以上ある。
証明では、三角形を 1 つずつ調べる代わりに、各頂点で「色の違う 2 本の辺の組」を数える。
$K_n$ の 2 色の塗り分けで、頂点 $v$ から出る 2 本の辺 $vx$、$vy$ の色が異なるとき、この 2 本の組を、頂点 $v$ の 色違いの角 という。
- $K_6$ の頂点 $v$ から出る 5 本のうち、赤が $r$ 本、青が $5-r$ 本なら、赤 1 本と青 1 本の組を選ぶので、$v$ の色違いの角は $r(5-r)$ 個である。
$$ \begin{array}{c|cccccc} r & 0 & 1 & 2 & 3 & 4 & 5\\ \hline r(5-r) & 0 & 4 & 6 & 6 & 4 & 0 \end{array} $$
どの $r$ でも $r(5-r)\le6$ である。 - ex-ram-party では、各人の知り合いの人数（赤の辺の本数）は、人 $1$ から順に $3,3,2,2,3,3$ で、色違いの角はどの人でも $6$ 個、全部で $36$ 個である。
段 1（色違いの角の総数は $36$ 以下）．ex-ram-angle (1) より、各頂点の色違いの角は $6$ 個以下である。頂点は 6 個なので、色違いの角は全部で $6\times6=36$ 個以下である。
段 2（色違いの角と三角形）．頂点 $v$ の色違いの角 $\{vx,vy\}$ に、三角形 $vxy$ を対応させる。$K_6$ ではどの 2 頂点も辺で結ばれているので、三角形 $vxy$ はいつもある。逆に、三角形 $xyz$ の中にある角は、頂点 $x$ での $\{xy,xz\}$、頂点 $y$ での $\{yx,yz\}$、頂点 $z$ での $\{zx,zy\}$ の 3 つである。この 3 つのうち色違いの角がいくつあるかを数える。
- 同じ色の三角形では、3 辺が同じ色なので、色違いの角は $0$ 個である。
- 同じ色でない三角形では、3 辺のうち 2 本が同じ色で 1 本だけ違う色である（3 本を 2 色に塗るので、どちらかの色が 2 本以上ある）。違う色の 1 本を $xy$ とすると、頂点 $x$ の角 $\{xy,xz\}$ と頂点 $y$ の角 $\{yx,yz\}$ は色違い、頂点 $z$ の角 $\{zx,zy\}$ は同じ色どうしである。よって色違いの角はちょうど $2$ 個である。
どの色違いの角も、ちょうど 1 つの三角形の中にある。したがって
$$ (\text{色違いの角の総数})=2\times(\text{同じ色でない三角形の個数}) $$
である。
段 3（結論）．段 1・段 2 より、同じ色でない三角形は $\dfrac{36}2=18$ 個以下である。$K_6$ の三角形は $\binom63=20$ 個なので、同じ色の三角形は $20-18=2$ 個以上ある。
段 2 の等式から、同じ色の三角形の個数は、各頂点の赤の辺の本数 $r_1,\dots,r_6$ だけで決まる。
$$
(\text{同じ色の三角形の個数})=20-\frac12\sum_{v=1}^{6}r_v(5-r_v)
$$
ex-ram-party では $20-\dfrac{36}2=2$ で、実際に見つけた 2 つ（三角形 $234$ と $256$）ですべてである。
6 頂点を $\{1,2,3\}$ と $\{4,5,6\}$ に分け、同じ組の中の辺（$12$、$13$、$23$、$45$、$46$、$56$ の 6 本）を赤、組をまたぐ辺（9 本）を青に塗る（図 4）。
赤い三角形は $123$ と $456$ の 2 つである。青い三角形はない。3 頂点のうち 2 つは同じ組に入る（組は 2 つしかないから）ので、その 2 頂点を結ぶ辺は赤だからである。どの頂点でも赤は 2 本、青は 3 本で、色違いの角は $2\times3=6$ 個、全部で $36$ 個なので、式からも $20-18=2$ である。thm-ram-two の「2 つ以上」は「3 つ以上」に強められない。
2 つの組の中の辺を赤の実線、組をまたぐ辺を青の破線で塗った K6。同じ色の三角形は赤い三角形 123 と 456 の 2 つだけ
例と反例
thm-ram-main の条件のうち、どれを変えると何が崩れるかを表にする。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 頂点が 6 個以上 | $K_5$ の五角形と五芒形の塗り分け（thm-ram-main (2)） | 同じ色の三角形ができる |
| 色が 2 色 | 3 色に塗った $K_6$（ex-ram-cx-three） | 同じ色の三角形ができる |
| 赤と青の両方を見る | すべての辺が青の $K_6$（ex-ram-cx-one） | 赤い三角形ができる |
| 求める形が三角形 | ex-ram-sharp の塗り分け（ex-ram-cx-four） | 同じ色の 4 頂点の完全グラフができる |
$K_5$ の五角形と五芒形の塗り分け（赤と青）に、6 つ目の頂点 $6$ を加え、$6$ から出る 5 本の辺を緑に塗る（図 5）。
$6$ を含まない三角形は $K_5$ の三角形なので、ex-ram-pentagon のとおり 2 色が混ざっている。$6$ を含む三角形 $6xy$ は、辺 $6x$、$6y$ が緑で、辺 $xy$ は赤か青なので、同じ色ではない。よって同じ色の三角形はない。thm-ram-main (1) の証明では、「5 本の辺のうち 3 本は同じ色」（lem-ram-pigeon）を使ったが、3 色では 5 本を $2,2,1$ 本に分けられるので、この一歩が成り立たない。
3 色に塗った K6。赤の実線と青の破線は K5 の塗り分けで、中央の頂点 6 から出る辺は緑の点線
6 人が互いに知らない（すべての辺が青）なら、互いに知り合いの 3 人（赤い三角形）はいない。すべての辺が赤なら、互いに知らない 3 人はいない。thm-ram-main は「赤い三角形 か 青い三角形」があると言っていて、どちらの色かは塗り方で決まる。このとき同じ色の三角形は $20$ 個すべてである。
ex-ram-sharp の塗り分けで、4 頂点を選ぶと、そのうち 2 頂点は $\{1,2,3\}$ に、別の 2 頂点は $\{4,5,6\}$ に入るか、一方の組に 3 頂点と他方に 1 頂点が入る。どちらの場合も、組をまたぐ青の辺と同じ組の中の赤の辺が両方含まれるので、4 頂点の間の 6 辺は同じ色にならない。求める形を三角形から 4 頂点の完全グラフに大きくすると、6 頂点では足りない。何頂点あれば足りるかは rem-ram-general で触れる。
大学数学で見る：一般の Ramsey 数
上からの評価
$m,n\ge2$ とする。$K_N$ の辺をどう 2 色に塗り分けても、「赤い $K_m$」（$m$ 頂点で、その間の辺がすべて赤）か「青い $K_n$」ができる、という性質をもつ最小の $N$ を $R(m,n)$ と書く。$R(3,3)$ は $m=n=3$ の場合である。$R(2,n)=n$ である（$K_n$ に赤い辺が 1 本でもあればそれが赤い $K_2$ で、なければ全体が青い $K_n$。すべて青の $K_{n-1}$ にはどちらもない）。同じく $R(m,2)=m$ である。
thm-ram-main (1) の証明は、次の不等式の特別な場合である。
$m,n\ge3$ なら $R(m,n)$ は定まり、
$$
R(m,n)\le R(m-1,n)+R(m,n-1),\qquad R(m,n)\le\binom{m+n-2}{m-1}
$$
である。
要点：1 つの頂点 $v$ から出る辺を赤と青に分け、lem-ram-pigeon と同じ数え方で、赤の先か青の先のどちらかが十分多いことを使う。
詳しい証明を開く
$m+n$ についての帰納法で示す。$R(m-1,n)$ と $R(m,n-1)$ が定まっているとし、$N=R(m-1,n)+R(m,n-1)$ とおく（$m-1=2$ や $n-1=2$ なら rem-ram-general の値を使う）。$K_N$ の 2 色の塗り分けで頂点 $v$ をとり、$v$ と赤で結ばれた頂点の集合を $X$、青で結ばれた頂点の集合を $Y$ とする。$\lvert X\rvert+\lvert Y\rvert=N-1$ である。$\lvert X\rvert\le R(m-1,n)-1$ かつ $\lvert Y\rvert\le R(m,n-1)-1$ だとすると、$\lvert X\rvert+\lvert Y\rvert\le N-2$ となり矛盾する。
$\lvert X\rvert\ge R(m-1,n)$ のとき、$X$ の頂点の間の辺には、赤い $K_{m-1}$ か青い $K_n$ がある。赤い $K_{m-1}$ なら、$v$ を加えると（$v$ から $X$ への辺は赤なので）赤い $K_m$ になる。$\lvert Y\rvert\ge R(m,n-1)$ のときも同じく、赤い $K_m$ か、$v$ を加えた青い $K_n$ がある。よって $R(m,n)\le N$ である。
2 つ目の不等式は、$m+n$ についての帰納法と、二項係数の漸化式 $\binom{m+n-3}{m-2}+\binom{m+n-3}{m-1}=\binom{m+n-2}{m-1}$ から従う。帰納法の出発点は $R(2,n)=n=\binom{n}{1}$、$R(m,2)=m=\binom{m}{m-1}$ である。
- $R(3,3)\le R(2,3)+R(3,2)=3+3=6$ で、$\binom42=6$ でもある。thm-ram-main (1) の証明で、頂点 $v$ から出る 5 本を「赤 3 本以上か青 3 本以上」に分けたのは、この不等式の $5=(3-1)+(3-1)+1$ にあたる。
- $R(3,4)\le R(2,4)+R(3,3)=4+6=10$ で、$\binom52=10$ でもある。つまり「10 人いれば、互いに知り合いの 3 人か、互いに知らない 4 人がいる」（下の演習）。
- $R(4,4)\le R(3,4)+R(4,3)\le10+10=20=\binom63$ である。
実際の値は評価より小さいことが多い。2017 年版の KT17 には、$R(3,3)=6$、$R(4,4)=18$、$43\le R(5,5)\le49$ と書かれていて、同書の時点で $R(5,5)$ の値は分かっていなかった（同書の表 11.3 では $R(3,4)=9$）。
下からの評価と数え上げ
$R(n,n)$ が大きいこと、つまり同じ色の $K_n$ のない塗り分けがあることは、塗り分けを 1 つ作らなくても、数え上げで示せる。
$n\ge3$、$t\ge n$ とする。$\displaystyle\binom tn\cdot2^{\,1-\binom n2}<1$ なら、$K_t$ には同じ色の $K_n$ のない 2 色の塗り分けがあり、$R(n,n)>t$ である。
要点：すべての塗り分けを数え、同じ色の $K_n$ をもつものの数を上から抑えると、全体より少ない。
詳しい証明を開く
$K_t$ の辺は $\binom t2$ 本で、塗り分けは全部で $2^{\binom t2}$ 通りある。$n$ 頂点の組 $W$ を 1 つ決めると、$W$ の間の $\binom n2$ 本がすべて赤かすべて青である塗り分けは、その $\binom n2$ 本の色が 2 通り、ほかの辺の色が自由なので、$2\cdot2^{\binom t2-\binom n2}$ 通りである。$W$ の選び方は $\binom tn$ 通りなので、同じ色の $K_n$ をもつ塗り分けは多くとも $$\binom tn\cdot2\cdot2^{\binom t2-\binom n2}=\binom tn\cdot2^{\,1-\binom n2}\cdot2^{\binom t2}$$ 通りで、仮定よりこれは全体 $2^{\binom t2}$ より少ない。よって同じ色の $K_n$ をもたない塗り分けがある。
$n=4$ では $\binom64\cdot2^{-5}=\dfrac{15}{32}<1$ なので $R(4,4)>6$ である（ex-ram-cx-four で実際に塗り分けを見た）。$t=7$ では $\dfrac{35}{32}>1$ で、この方法では $7$ 以上は言えない。$n=10$ では $t=100$ まで条件が成り立ち、$R(10,10)>100$ が分かる。
prop-ram-lower の数え方は、「でたらめに塗ったときの同じ色の $K_n$ の個数の期待値が $1$ より小さい」と言いかえられる（期待値の線形性と数え上げ）。KT17 の Theorem 11.4 は、この考えを詰めて $R(n,n)\ge\dfrac{n}{e\sqrt2}\,2^{n/2}$ を示している。一方、上からの評価は $\binom{2n-2}{n-1}\le2^{2n-2}=4^{n-1}$ である（$\binom{2n-2}{k}$ を $k=0,1,\dots,2n-2$ について足すと $2^{2n-2}$ になるから）。よって $R(n,n)$ は $\dfrac{n}{e\sqrt2}\,2^{n/2}$ 以上、$4^{n-1}$ 以下である。
演習
$K_6$ の塗り分けで、赤の辺が $16$、$25$、$35$、$36$、$45$、$46$ の 6 本で、ほかはすべて青とする。各頂点の赤の辺の本数を求め、同じ色の三角形の個数を式で求めよ。また、それらの三角形を書き出せ。
解答を開く
赤の辺の本数は、頂点 $1$ から順に $1,1,2,2,3,3$ である。$r(5-r)$ は $4,4,6,6,6,6$ で、合計 $32$ なので、同じ色の三角形は $20-\dfrac{32}2=4$ 個である。4 頂点 $1,2,3,4$ の間の 6 辺（$12,13,14,23,24,34$）には赤がないので、三角形 $123$、$124$、$134$、$234$ はすべて青い三角形で、これで 4 個である。
10 人いれば、互いに知り合いの 3 人か、互いに知らない 4 人がいることを、thm-ram-main を使って示せ。
解答を開く
1 人 $v$ を選ぶと、残りは 9 人である。$v$ の知り合いが 3 人以下で、$v$ が知らない人が 5 人以下なら、合わせて 8 人以下で矛盾する。よって、$v$ の知り合いが 4 人以上いるか、$v$ が知らない人が 6 人以上いる。
知り合いが 4 人以上のとき：その 4 人の中に互いに知り合いの 2 人がいれば、$v$ と合わせて互いに知り合いの 3 人である。いなければ、その 4 人は互いに知らない 4 人である。
知らない人が 6 人以上のとき：その 6 人に thm-ram-main (1) を使うと、互いに知り合いの 3 人か、互いに知らない 3 人がいる。前者なら終わり。後者なら、$v$ を加えると（$v$ はその 3 人を知らないので）互いに知らない 4 人になる。
さらに先へ
- $R(m,n)$ の上からの評価と Ramsey の定理は、大学向けの Ramseyの定理 で扱う。
- 次に読む Erdős–Szekeresの定理（凸多角形） の節「大学数学で見る：Ramsey の定理と未解決の値」では、平面の点の中に凸多角形が必ず現れることを、Ramsey の定理と結びつけて見る。
- KT17 の節 11.1・11.2 と Bog17 の節 1.3.4 は、6 人の中の 3 人の問題から Ramsey 数を導入している。
- 完全グラフ（完全グラフ）の辺の数え方は 場合の数の数え方の体系、上からの評価に出てくる二項係数の漸化式は 二項定理と組合せの恒等式 にある。
関連項目
- 前提: 一筆書きとグラフ, 場合の数の数え方の体系
- 前に読む: 結婚定理とマッチング, 一筆書きとグラフ, 場合の数の数え方の体系
- 次に読む: Erdős–Szekeresの定理（凸多角形）
- 関連（高校数学）: 二項定理と組合せの恒等式, 期待値の線形性と数え上げ, 重み付きグラフの最短経路
- 発展: Ramseyの定理, 完全グラフ, 鳩の巣原理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
