ラムゼー理論
ラムゼー理論（ラムゼーりろん、英: Ramsey theory）は、一定の秩序がどのような条件の下で必ず現れるかを研究する数学の一分野である。名前はイギリスの数学者・哲学者であるフランク・ラムゼイ (Frank P. Ramsey) に因んでいる。ラムゼー理論の問題は、典型的には「ある構造がある性質を持つことを保証するには、その構造にはどのくらい元が必要か」という形のものである。
例
ラムゼー理論における典型的な結果では、まず何らかの数学的構造が与えられ、次いでその構造がいくつかの断片へと分割される。その断片の少なくとも1つが所与の興味深い性質を持つためには、元の構造がどれだけ大きければよいのだろうか。この考えは分割の正則性として定義される。
例えば、位数が n の完全グラフを考える。すなわち、そのグラフには n 個の頂点があり、全ての頂点が互いに辺により結ばれている。位数が3の完全グラフは三角形と呼ばれる。今、各辺の色を赤または青とする。赤または青一色の三角形があることを保証するには、n はどれだけ大きければよいか。答えは6である。厳密な証明はラムゼーの定理に書かれている。
この結果は次のようにも表現できる。すなわち、少なくとも6人いれば、その中に、互いに知り合い（それぞれが他の二人を知っている）、もしくは互いに他人（それぞれが他の二人を知らない）であるような3人がいる。詳しくはパーティ問題を参照のこと。
この結果はラムゼーの定理の特別な場合でもある。その定理は、任意の自然数 c と任意の自然数 n1, ..., nc に対し、ある数 R(n1, ..., nc) が存在して、位数 R(n1, ..., nc) の完全グラフの辺が c 種類の色に塗られているならば、1 以上 c 以下のある自然数 i に対して、全ての辺が i 番目の色で塗られている位数 ni の完全部分グラフが必ず含まれるというものである。
結果
ラムゼー理論の鍵となる二つの定理は以下のものである：
- ファン・デル・ヴェルデンの定理： 任意に c と n が与えられたとき、ある自然数 V が存在して、以下の条件を満たす： V 個の連続する自然数が c 色に塗り分けられているならば、どの元も同じ色で塗られている、長さ n の等差数列が含まれている。
- Hales–Jewettの定理： 任意に c と n が与えられたとき、ある自然数 H が存在して、以下の条件を満たす： n×n×...×n の H 次元超立方体のセルを c 色で塗り分けると、ある長さnの行や列などが存在して、それに属する全てのセルが同じ色で塗り分けられている。すなわち、一列に n マスある多人数まるばつは、どれほど n が大きくても、どれほど多人数で遊んだとしても、十分次元の大きい盤面で遊ぶ際、引き分けに終わることがない。Hales–Jewettの定理はファン・デル・ヴェルデンの定理を含む。
ファン・デル・ヴェルデンの定理に似た定理にシューアの定理があり、これは次のような定理である。これは、任意に c が与えられたとき、ある自然数 N が存在して、以下の条件を満たす： 1, 2, ..., N という数が c 色で塗り分けられているならば、x, y, x + y が全て同じ色となるような自然数 x, y の組が存在する。この定理の一般化はRadoの定理、Rado-Folkman-Sandersの定理、Hindmanの定理、Milliken-Taylorの定理など多数ある。これらの定理やその他多くの結果の古典的な参考文献として、Graham, Rothschild and Spencer[1]がある。
ラムゼー理論の結果は二つの主要な特徴がある。第一に、構成的ではないことである。結果は、ある構造が存在することは示しているが、（力まかせ探索を除いて）この構造を見つけるための手段は与えていない。例えば、鳩の巣原理はこの形式に属する。第二に、ラムゼー理論の結果は十分大きな対象がある与えられた構造を必ず持つことを示す一方、この結果の証明にはその大きさが莫大であることがしばしば要求される。その大きさの上界は、指数関数的に、あるいは、アッカーマン関数と同じくらいの速さで増大することさえ珍しくはない。多くの場合このような上界は証明に用いられる人為的なものであり、その上界を十分に改善できるかどうかは知られていない。またある場合にはどのような上界も莫大でなければならず、ときにはどのような原始再帰関数よりさえも大きい。例はParis-Harringtonの定理を参照。グラハム数は、正式な数学の証明において使われた最大の数であり、ラムゼー理論に関する問題の上界である。
ラムゼー理論における定理は一般的に2種類に分けられる。多くの定理は、ラムゼーの定理そのものをモデルとしており、大きな構造を持つ対象の任意の分割において、類の1つが必ず大きな構造を持つ部分対象を持つことを主張するが、それがどの類なのかに関する情報は一切与えない。いくつかの場合において、そのようなラムゼー型の結果が成り立つ理由は、最大の分割類がつねに所望の部分構造を含むからである。この種の結果は、density results, あるいはTuránの定理に因んで、Turán-type result と呼ばれる。代表的な例として、ファン・デル・ヴェルデンの定理をそのように強めたものであるSzemerédiの定理や、Hales-Jewett の定理の density version がある[2]。
関連項目
注釈
- ^ Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory (2nd ed.), New York: John Wiley and Sons, ISBN 0-4715-0046-1.
- ^ Furstenberg, Hillel; Katznelson, Yitzhak (1991), “A density version of the Hales–Jewett theorem”, Journal d'Analyse Mathématique 57 (1): 64–119, doi:10.1007/BF03041066.
参考文献
- Landman, B. M.; Robertson, A. (2004), Ramsey Theory on the Integers, Student Mathematical Library, 24, Providence, RI: AMS, ISBN 0-8218-3199-2.
- Ramsey, F. P. (1930), “On a Problem of Formal Logic”, Proceedings London Mathematical Society s2-30 (1): 264–286, doi:10.1112/plms/s2-30.1.264.
- Erdös, P.; Szekeres, G. (1935), “A combinatorial problem in geometry”, Compositio Mathematica 2: 463–470.
- Boolos, G.; Burgess, J. P.; Jeffrey, R. (2007), Computability and Logic (5th ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-87752-7.