|
ラムゼー理論（ラムゼーりろん、）とは、一定の秩序がどのような条件の下で必ず現れるかを研究する数学の一分野である。名前はイギリスの数学者・哲学者であるフランク・ラムゼイ () に因んでいる。ラムゼー理論の問題は、典型的には「ある構造がある性質を持つことを保証するには、その構造にはどのくらい元が必要か」という形のものである。 ==例== ラムゼー理論における典型的な結果では、まず何らかの数学的構造が与えられ、次いでその構造がいくつかの断片へと分割される。その断片の少なくとも1つが所与の興味深い性質を持つためには、元の構造がどれだけ大きければよいのだろうか。この考えはとして定義される。 例えば、位数が ''n'' の完全グラフを考える。すなわち、そのグラフには ''n'' 個の頂点があり、全ての頂点が互いに辺により結ばれている。位数が3の完全グラフは三角形と呼ばれる。今、各辺の色を赤または青とする。赤または青一色の三角形があることを保証するには、''n'' はどれだけ大きければよいか。答えは6である。厳密な証明はに書かれている。 この結果は次のようにも表現できる。すなわち、少なくとも6人いれば、その中に、互いに知り合い（それぞれが他の二人を知っている）、もしくは互いに他人（それぞれが他の二人を知らない）であるような3人がいる。詳しくはを参照のこと。 この結果はラムゼーの定理の特別な場合でもある。その定理は、任意の自然数 ''c'' と任意の自然数 ''n''1, ..., ''n''''c'' に対し、ある数 ''R''(''n''1, ..., ''n''''c'') が存在して、位数 ''R''(''n''1, ..., ''n''''c'') の完全グラフの辺が ''c'' 種類の色に塗られているならば、1 以上 ''c'' 以下のある自然数 ''i'' に対して、全ての辺が ''i'' 番目の色で塗られている位数 ''ni'' の完全部分グラフが必ず含まれるというものである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ラムゼー理論」の詳細全文を読む スポンサード リンク
|