| dbo:abstract
|
- ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 s=2 とするとき、次の結果が得られる。この結果がラムゼーの定理として言及されることも多い。 r, k1, k2, ..., krを2以上の整数とする。このとき、次の性質を満たすRr (k1, k2, ..., kr)が存在する：n≥ R (k1, k2, ..., kr)ならば、n 個の点からなる完全グラフの辺をどの様にr 色に彩色してもあるi に対して、ki個の点からなる色i の完全グラフが存在する。 ラムゼーの定理に類似した定理として、ファン・デル・ヴェルデンの定理など多くの種類の定理が知られている。最近になって、これらの一般化であるHales-Jewettの定理が発見され、これにより、一連の類似した定理は一つの理論として確立した。 (ja)
- ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 s=2 とするとき、次の結果が得られる。この結果がラムゼーの定理として言及されることも多い。 r, k1, k2, ..., krを2以上の整数とする。このとき、次の性質を満たすRr (k1, k2, ..., kr)が存在する：n≥ R (k1, k2, ..., kr)ならば、n 個の点からなる完全グラフの辺をどの様にr 色に彩色してもあるi に対して、ki個の点からなる色i の完全グラフが存在する。 ラムゼーの定理に類似した定理として、ファン・デル・ヴェルデンの定理など多くの種類の定理が知られている。最近になって、これらの一般化であるHales-Jewettの定理が発見され、これにより、一連の類似した定理は一つの理論として確立した。 (ja)
|
| rdfs:comment
|
- ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 (ja)
- ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。 無限ラムゼーの定理r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。有限ラムゼーの定理s , r , k1, k2, ..., kr をki ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C1, C2, ..., Crに類別したとき、あるiが存在して、ki個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類Ciに属するものが存在する。 以下、これを満たす最小のR をRr (s; k1, k2, ..., kr)とおく。 有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。 鳩の巣原理から、s=1のとき、Rr (1; k, k, ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。 (ja)
|
