- 970 名前：１３２人目の素数さん mailto:sage [2011/10/18(火) 09:09:01.48 ]
- >>956 もう見てないかな。ラムゼーの定理が気になったので調べてみたよ。
・R(4, 4)=18 の証明
www.cut-the-knot.org/arithmetic/combinatorics/Ramsey44.shtml
以下、証明に必要な知識
・R(4, 3)=9
www.cut-the-knot.org/arithmetic/combinatorics/Ramsey43.shtml
・R(m, n) ≤ R(m-1, n) + R(m, n-1)
・R(m, n) ≤ R(m-1, n) + R(m, n-1) -1 (右辺第1,第2項が偶数の時)
www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml#inequality1
あと一応 R(3, 3)=6
en.wikipedia.org/wiki/Ramsey%27s_theorem
「Example: R(3,3)=6」に２通りの証明。やや言葉足らず気味。
グラフ理論の知識が殆どない俺でも順を追って読んだら理解できたよ。英語も簡単な単語しか使われてないし。
あとグラフへの注釈間違えとか微妙な箇所があるけど簡単に補えると思う。
|
 |
