ラムゼーの定理

組合せ論において、グラフ理論的形式の 1 つであるラムゼーの定理は、十分に大きな完全グラフの任意の辺ラベル付け(色付き)で単色クリークが見つかると述べています。2 色 (たとえば、青と赤) に対する定理を証明するために、rとs を任意の2 つの正の整数とします。^[a]ラムゼーの定理は、R ( r、s )頂点上の完全グラフのすべての青赤辺着色に、r頂点上の青クリークまたは s 頂点上の赤クリークが含まれる最小の正の整数 R ( r、s )が存在すると述べています。(ここで、R ( r、s ) はrとsの両方に依存する整数を表します。)

ラムゼーの定理は、組合せ論における基礎的な結果です。この結果の最初のバージョンは、フランク・ラムゼーによって証明されました。これにより、現在ラムゼー理論と呼ばれている組合せ理論が始まりました。この理論は、無秩序の中にある規則性、つまり規則的な特性を持つ部分構造が存在するための一般的な条件を求めています。この応用では、単色部分集合、つまり1 色だけの接続されたエッジの 部分集合の存在が問題となります。

この定理の拡張は、 2 色だけでなく、任意の有限数の色に適用されます。より正確には、定理は、任意の色の数cと任意の整数n ₁、…、n _cに対して、 R ( n ₁、…、n _c )という数が存在し、R ( n ₁、…、n _c )の完全グラフの辺がc 種類の異なる色で着色されている場合、1 とcの間のあるiに対して、辺がすべて色iであるn _i次完全サブグラフが必ず含まれる、というものです。上記の特殊なケースでは、c = 2 (およびn ₁ = rおよびn ₂ = s ) です。

6 頂点の完全グラフの辺が赤と青で色付けされているとします。頂点v を選びます。 vに接続する辺は 5 つあるため、 (鳩の巣原理によ​​り) そのうち少なくとも 3 つは同じ色でなければなりません。一般性を失うことなく、頂点vと頂点r、s、t を接続する辺のうち少なくとも 3 つは青であると想定できます。 (そうでない場合は、以下で赤と青を入れ替えます。) 辺( rs )、( rt )、( st )のいずれ かが青である場合、完全に青い三角形になります。そうでない場合、これら 3 つの辺はすべて赤であり、完全に赤い三角形になります。この議論は任意の色付けに当てはまるため、任意のK ₆には単色のK _{3 が}含まれ、したがってR (3, 3) ≤ 6 となります。この定理の一般的なバージョンは、友人と他人の定理と呼ばれています。

別の証明は、を二重に数えることによって機能します。それは次のようになります。辺( xy )が赤で、辺( yz )が青である頂点x、y、zの順序付き 3 つ組の数を数えます。まず、任意の頂点は、0 × 5 = 0 (頂点からのすべての辺が同じ色)、1 × 4 = 4 (4 つが同じ色で、1 つが別の色)、または2 × 3 = 6 (3 つが同じ色で、2 つが別の色) のいずれかのそのような 3 つ組の中央になります。したがって、そのような 3 つ組は最大で6 × 6 = 36個あります。次に、任意の非単色三角形( xyz )について、そのような 3 つ組が正確に 2 つ存在します。したがって、非単色三角形は最大で 18 個あります。したがって、 K ₆の 20 個の三角形のうち少なくとも 2 個は単色です。

逆に、単色のK ₃を作成せずにK _{5 を}2 色にすることは可能であり、R (3, 3) > 5であることがわかります。 唯一の^[b]色付けは右側に示されています。 したがって、R (3, 3) = 6 です。

R (3, 3) ≤ 6を証明するという課題は、 1953 年のウィリアム・ローウェル・パトナム数学コンテスト、および 1947 年のハンガリー数学オリンピック の問題の 1 つでした。

多色ラムゼー数とは、3色以上の色を使ったラムゼー数である。正確な値が分かっている非自明な多色ラムゼー数は（対称性を除いて）R (3, 3, 3) = 17とR (3, 3, 4) = 30 の2つだけである。^[1]

完全なグラフの辺の色付けを、赤、緑、青の 3 色で行っているとします。さらに、辺の色付けには単色の三角形がないものとします。頂点v を選択します。頂点vへの赤い辺を持つ頂点の集合を考えます。これはvの赤い近傍と呼ばれます。 vの赤い近傍には赤い辺を含めることはできません。そうしないと、赤い辺と頂点vの 2 つの端点からなる赤い三角形ができてしまいます。したがって、 vの赤い近傍の誘導辺の色付けには、緑と青の 2 色のみで色付けされた辺があります。R (3, 3) = 6なので、 vの赤い近傍には最大で 5つの頂点を含めることができます。同様に、vの緑と青の近傍には、それぞれ最大で 5 つの頂点を含めることができます。v自体を除くすべての頂点はvの赤、緑、青のいずれかの近傍にあるため、完全グラフ全体は最大で1 + 5 + 5 + 5 = 16 個の頂点を持つことができます。したがって、 R (3, 3, 3) ≤ 17 となります。

R (3, 3, 3) = 17 であることを確認するには、単色三角形を回避する 3 色で 16 頂点の完全グラフの辺の色付けを描くだけで十分です。K ₁₆には、いわゆるねじれのない色付けとねじれた色付けの 2 つの色付けがあることがわかります。 両方の色付けが右側の図に示されており、左側がねじれのない色付け、右側がねじれた色付けです。

K ₁₆上のねじれていない色またはねじれた色のいずれかの任意の色を選択し、指定された色を持つエッジとまったく同じエッジを持つグラフを考慮すると、クレプシュ グラフが得られます。

K ₁₅上には単色三角形を回避する 3 色の辺彩色がちょうど 2 つ存在することが分かっており、これらはそれぞれK ₁₆上のねじれていない彩色とねじれた彩色から任意の頂点を削除することによって構築できます。

また、色の順列によって異なるエッジカラーリングを同じと見なすと、 K ₁₄上に単色三角形を回避する 3 色によるエッジカラーリングが正確に 115 個あることもわかっています。

2色の場合の定理は、r + sに関する帰納法で証明できます。^{[2]定義から、すべての}nに対して、R ( n、 2) = R (2、n ) = n であることがわかります。これで帰納法が始まります。R ( r、s )が存在することを証明するには、その明示的な境界を見つけます。帰納的仮説により、R ( r − 1、s )とR ( r、s − 1)が存在します。

補題1. ${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1).}$

証明。R ( r − 1, s ) + R ( r , s − 1 )頂点上に辺が 2 色で塗られた完全グラフを考えます。グラフから頂点v を選び、残りの頂点を 2 つの集合 MとNに分割します。このとき、すべての頂点wについて、辺( vw )が青であればw はMに含まれ、辺( vw )が赤であればw はNに含まれます。グラフには頂点があるため、次のいずれかが成り立ちます。前者の場合、M に赤の K _{s が}あれば、元のグラフにも赤のK sがあり、これで完了です。そうでない場合、M には青のK _{r − 1}があり、Mの定義により青のK _rがあります。後者の場合も同様です。したがって、主張は真であり、2 色の証明が完了しました。 ${\displaystyle R(r-1,s)+R(r,s-1)=|M|+|N|+1}$${\displaystyle |M|\geq R(r-1,s)}$${\displaystyle |N|\geq R(r,s-1).}$${\displaystyle M\cup \{v\}}$

この2色の場合、R ( r − 1, s )とR ( r , s − 1 )が両方とも偶数であれば、誘導不等式は次のように強化される: ^[3]

${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)-1.}$

証明。p = R ( r − 1, s )およびq = R ( r , s − 1)が両方とも偶数であると仮定します。t = p + q − 1 とし、 t個の頂点を持つ2 色のグラフを考えます。d i が青いサブグラフの i 番目の頂点の次数である場合、_ハンドシェイクの補題により、は偶数です。t が奇数である場合、偶数のd _{i が}存在する必要があります。一般性を失うことなく、 d ₁が偶数であり、MとN がそれぞれ青いサブグラフと赤いサブグラフの頂点 1 に接続する頂点であると仮定します。このとき、との両方が偶数です。鳩の巣原理によ​​り、または が偶数でp – 1が奇数なので、最初の不等式を強化できるため、または のいずれかであると 仮定します。この場合、 Mサブグラフに赤いK _sがあり、証明は完了します。または、青いK _{r – 1}があり、頂点 1 と一緒に青いK _{r を}作成します。この場合も同様に扱われます。 ${\displaystyle \textstyle \sum _{i=1}^{t}d_{i}}$${\displaystyle |M|=d_{1}}$${\displaystyle |N|=t-1-d_{1}}$${\displaystyle |M|\geq p-1,}$${\displaystyle |N|\geq q.}$${\displaystyle |M|}$${\displaystyle |M|\geq p}$${\displaystyle |N|\geq q.}$${\displaystyle |M|\geq p=R(r-1,s).}$${\displaystyle |N|\geq q=R(r,s-1)}$

補題2. c > 2ならば、${\displaystyle R(n_{1},\dots ,n_{c})\leq R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})).}$

証明。頂点の完全なグラフを考え、その辺をc色で色付けします。次に「色盲になって」、 c − 1 と c が同じ色であると仮定します。こうすると、グラフは( c − 1)色になります。このようなグラフの定義により、1 ≤ i ≤ c − 2に対して色iで単色に色付けされたK _{n i}か、 「ぼやけた色」で色付けされたK _{R ( n c − 1 , n c )}のいずれかが含まれます。前者の場合はこれで完了です。後者の場合は、再び視力を取り戻し、R ( n _{c − 1} , n _c )の定義から、 ( c − 1)単色K _{n c − 1}かc単色K _{n c}のいずれかが必要であることがわかります。どちらの場合でも証明は完全です。 ${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c}))}$${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})),}$

補題 1 は、任意のR ( r , s )が有限であることを意味します。補題 2 の不等式の右辺は、 c色のラムゼー数を、より少ない色のラムゼー数で表しています。したがって、任意のR ( n ₁ , …, n _c )は、任意の色数に対して有限です。これは定理を証明しています。

ラムゼーの定理（および 2 色以上への拡張）の数R ( r , s )は、ラムゼー数として知られています。ラムゼー数R ( m , n )は、パーティー問題の解を与えます。パーティー問題は、少なくともm 人がお互いを知っているか、少なくともn 人がお互いを知らないようにするために、招待しなければならないゲストの最小数R ( m , n )を尋ねます。グラフ理論の用語では、ラムゼー数は、順序vのすべての無向単純グラフが順序 m のクリーク、または順序 n の独立集合を含むような頂点の最小数v = R ( m , n ) です。ラムゼーの定理は、すべての m および nに対してそのような数が存在することを述べています。

対称性により、 R ( m , n ) = R ( n , m )は真です。 R ( r , s )の上限は定理の証明から抽出でき、他の議論は下限を与えます。(最初の指数下限は、確率的方法を使用してポール・エルデシュによって得られました。) ただし、最も厳しい下限と最も厳しい上限の間には大きなギャップがあります。R ( r , s )の正確な値がわかっているrとs の数も非常に少ないです。

R ( r , s )の下限L を計算するには、通常、青いK _rサブグラフと赤いK _sサブグラフがないグラフK _{L −1}の青/赤の色分けを示す必要があります。このような反例はラムゼーグラフと呼ばれます。ブレンダン・マッケイは既知のラムゼーグラフのリストを管理しています。^[4]上限を確立するのはかなり難しいことがよくあります。反例が存在しないことを確認するためにすべての可能な色を確認するか、反例が存在しないことを数学的に証明する必要があります。

エルデシュは、我々よりもはるかに強力なエイリアンの勢力が地球に降り立ち、R (5, 5)の値を要求し、さもなければ地球を破壊すると想像するように求めている。その場合、我々はすべてのコンピュータとすべての数学者を集めてその値を見つけ出そうとすべきだと彼は主張する。しかし、その代わりに彼らがR (6, 6)を要求したとしよう。その場合、我々はエイリアンを破壊しようとすべきだと彼は信じている。^[5]

— ジョエル・スペンサー

高度なコンピュータプログラムでは、すべての色を個別に調べてすべてを除去する必要はありません。しかし、これは非常に難しい計算タスクであり、既存のソフトウェアでは小さなサイズでしか処理できません。各完全グラフK _nには、⁠1/2⁠ n ( n − 1)個のエッジがあるので、ブルートフォースを使用すると、合計でc ^{n ( n -1)/2 個のグラフ（} c色の場合）を検索することになります^{。 [6]したがって、}ブルートフォースを使用してすべての可能なグラフを検索する複雑さは、 c色の色と最大でn 個のノードに対してO ( c ^{n 2} )です。

量子コンピュータの登場によって状況が改善する可能性は低い。非構造化データセットの最もよく知られた検索アルゴリズムの1つは、古典的なコンピュータに比べて2乗の高速化しか示さない（グローバーのアルゴリズムを参照）ため、計算時間は依然としてノード数に対して指数関数的である。 ^{[7] [8]}

上で述べたように、R (3, 3) = 6 です。 R (4, 2) = 4 であること、そしてより一般的には、すべてのsに対してR ( s , 2) = s であることが簡単に証明できます。 s − 1個のノード上のグラフですべての辺が赤色になっているものは反例となり、R ( s , 2) ≥ sであることを証明します。 s個のノード上のグラフの色分けのうち、すべての辺が赤色になっている色分けにはsノードの赤い部分グラフが含まれ、他のすべての色分けには 2 ノードの青い部分グラフ (つまり、青い辺で接続されたノードのペア) が含まれます。

帰納不等式と握手補題を用いると、 R (4, 3) ≤ R (4, 2) + R (3, 3) − 1 = 9であり、したがってR (4, 4) ≤ R (4, 3) + R (3, 4) ≤ 18 であることがわかります。 16 ノードグラフの 6.4 × 10 22 種類の 2 色塗りのうち、 (4, 4, 16)グラフ (つまり、4 ノードの赤または青の完全サブグラフがない 16 ノード上の完全グラフの 2 色塗り) は²つだけであり、2.46 × 10 26 種類の色塗りのうち、(4, 4, 17) グラフ (順序 17 の Paley グラフ) は 1 つだけです。[ ⁴ ] (したがって、 R ⁽ 4 , 4) = 18 です。

R (4,5)=25という事実は、1995年にブレンダン・マッケイとスタニスワフ・ラジショフスキによって初めて確立されました。 ^[9]

R (5, 5)の正確な値は不明ですが、43 (Geoffrey Exoo (1989) ^[10] )から46 (Angeltveit and McKay (2024) ^[11] )の範囲にあることが分かっています。

1997年、マッケイ、ラジショフスキー、エクソはコンピュータ支援グラフ生成法を用いて、R (5, 5) = 43と推測した。彼らは、異なる経路を経て同じグラフセットに到達し、正確に656個の(5, 5, 42)グラフを構築することができた。656個のグラフのどれも(5, 5, 43)グラフに拡張することはできない。^[12]

r , s > 5のR ( r , s )については弱い境界値しか利用できない。R (6, 6)とR (8, 8)の下限値はそれぞれ1965年と1972年以来改善されていない。^[1]

r、s ≤ 10 の場合のR ( r、s )は、下の表に示されています。正確な値が不明な場合は、表に既知の最良の境界が示されています。r< 3の場合のR ( r、s )は、 sのすべての値に対して、 R (1、s ) = 1およびR (2、s ) = sで与えられます。

ラムゼー数研究の発展に関する標準的な調査は、スタニスワフ・ラジショフスキによるElectronic Journal of CombinatoricsのDynamic Survey 1であり、定期的に更新されています。^{[1] [13]特に引用がない限り、以下の表の項目は 2024 年 6 月版から引用されています。(} R ( r、s ) = R ( s、r ) であるため、対角線を挟んで自明な対称性があることに注意してください。)

不等式R ( r , s ) ≤ R ( r − 1, s ) + R ( r , s − 1)は、次のことを証明するために帰納的に適用することができる。

${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}.}$

特に、エルデシュとセケレスによるこの結果は、 r = sのとき、

${\displaystyle R(s,s)\leq (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.}$

指数関数的な下限、

${\displaystyle R(s,s)\geq (1+o(1)){\frac {s}{{\sqrt {2}}e}}2^{s/2},}$

は 1947 年にエルデシュによって与えられ、確率的手法の導入に役立った。これら 2 つの境界の間には大きな隔たりがある。たとえば、s = 10の場合、101 ≤ R (10, 10) ≤ 48,620 となる。しかし、どちらの境界の指数的成長係数も長い間改善されず、下限については依然として√ 2のままである。指数的下限を生成する明示的な構成は知られていない。対角ラムゼー数の最もよく知られている下限と上限は、

${\displaystyle [1+o(1)]{\frac {{\sqrt {2}}s}{e}}2^{\frac {s}{2}}\leq R(s,s)\leq s^{-(c\log s)/(\log \log s)}4^{s},}$

それぞれスペンサーとコンロンによるものである。カンポス、グリフィス、モリス、サハスラブッデによる2023年のプレプリントでは、「ブック」と呼ばれるグラフ構造に依存するアルゴリズム構築を使用して指数関数的な進歩を遂げたと主張している^{[17] [18]}上限を

${\displaystyle R(s,s)\leq (4-\varepsilon )^{s}{\text{ and }}R(s,t)\leq e^{-\delta t+o(s)}{\binom {s+t}{t}}.}$

およびでは、特にこれらのパラメータを最適化できると考えられます。 ${\displaystyle \varepsilon =2^{-7}}$${\displaystyle \delta =50^{-1}}$${\displaystyle \varepsilon }$

非対角ラムゼー数R (3, t )は、次の順序であることが知られている⁠² t/ログt⁠ ; これは、 n頂点の三角形のないグラフにおける最小の独立数は

${\displaystyle \Theta \left({\sqrt {n\log n}}\right).}$

R (3, t )の上限はAjtai、Komlós、Szemerédiによって与えられている^[19]。下限はKimによって最初に得られ^{[20] 。}また、暗黙の定数は Fiz Pontiveros、 Griffiths 、Morris、^[21]およびBohmanとKeevash、^[22]によって、三角形のない過程を解析することで独立に改良された。さらに、より一般的な「Hのない過程」を研究することで、一般的な非対角ラムゼー数の最もよく知られている漸近的下限が設定されており^[23] R ( s、t )

${\displaystyle c'_{s}{\frac {t^{\frac {s+1}{2}}}{(\log t)^{{\frac {s+1}{2}}-{\frac {1}{s-2}}}}}\leq R(s,t)\leq c_{s}{\frac {t^{s-1}}{(\log t)^{s-2}}}.}$

の境界は となる が、2023年のプレプリント^{[24] [25]}では下限が に改善され、 下限が の形であるという証明に250ドルを提示したエルデシュの疑問が解決された。^{[26] [27]}${\displaystyle s=4}$${\displaystyle c'_{s}t^{\frac {5}{2}}(\log t)^{-2}\leq R(4,t)\leq c_{s}t^{3}(\log t)^{-2}}$${\displaystyle c'_{s}t^{3}(\log t)^{-4}}$${\displaystyle c'_{s}t^{3}(\log t)^{-d}}$

ラムゼーの定理には、あまり知られていないが興味深い、誘導部分グラフに対する類似物がある。大まかに言えば、単色部分グラフを見つける代わりに、単色誘導部分グラフを見つけることが求められる。この変形では、完全グラフに焦点を限定するだけではもはや十分ではない。完全部分グラフの存在は誘導部分グラフの存在を意味しないからである。次のセクションの定理の定性的な記述は、1970年代にエルデシュ、ハイナルとポサ、デューバーとレードルによって初めて独立に証明された。 ^{[28] [29] [30]}それ以来、誘導ラムゼー数の良い境界を得るための研究が盛んに行われてきた。

H をn頂点のグラフとします。すると、 2 色を使用してGの辺を着色すると、Hの単色誘導コピー(つまり、 Hと同型で辺が単色であるGの誘導サブグラフ) が含まれるようなグラフGが存在します。G の頂点の最小数は、誘導ラムゼー数r _ind ( H )です。

場合によっては、問題の非対称バージョンも検討します。r _ind ( X , Y )を、グラフGの辺を赤または青のみで着色すると、Xの赤誘導サブグラフまたはYの青誘導サブグラフが含まれるようなグラフGの頂点の最小数として定義します。

ラムゼーの定理と同様に、誘導ラムゼー数があらゆるグラフHに対して存在するかどうかは事前には不明である。1970年代初頭、エルデシュ、ハイナルとポサ、デューバーとレードルが独立にこれが事実であることを証明した。^{[28] [29] [30]}しかし、元の証明は誘導ラムゼー数に対してひどい境界（例えば、2の塔）を与えた。よりよい境界が達成できるかどうかを問うことは興味深い。1974年に、ポール・エルデシュは、 k頂点上のあらゆるグラフH がr _ind ( H ) ≤ 2 ^ckを満たすような定数c が存在すると予想した。^[31]この予想が正しい場合、完全グラフはこの形式の下限値（実際、ラムゼー数と同じ）を達成するため、定数cまで最適となる。しかし、この予想は今のところ未解決である。

1984年、エルデシュとハイナルは、限界を証明したと主張した^[32]

${\displaystyle r_{\text{ind}}(H)\leq 2^{2^{k^{1+o(1)}}}.}$

しかし、それはまだエルデシュが推測した指数的境界からは程遠いものでした。1998年に小早川、プレメル、レードルが大きな進歩を遂げ、定数cに対してr _ind ( H ) ≤ 2 ^{ck (log k ) 2}のほぼ指数的境界を初めて証明しました。彼らのアプローチは、射影平面上に構築された適切なランダムグラフを検討し、それが非ゼロの確率で望ましい特性を持つことを示すというものでした。射影平面上のランダムグラフを使用するというアイデアは、頂点彩色に関するラムゼー特性や、制限された次数グラフH上の誘導ラムゼー問題の研究にも以前に使用されていました。^[33]

小早川、プロメル、およびレードルの境界は、10 年間にわたって一般的な境界として最も優れていました。2008 年に、フォックスとスダコフは、同じ境界を持つ誘導ラムゼー数の明示的な構成を提供しました。^[34]実際、彼らは、小さなλと適切なd を持つすべての( n、d、λ)グラフ Gには、2 色のGの辺の任意の彩色におけるk頂点上の任意のグラフの誘導単色コピーが含まれることを示しました。特に、ある定数cに対して、n ≥ 2 ^{ck log 2 k}頂点上のペイリーグラフでは、2 色の辺彩色のすべてに、すべてのk頂点グラフの誘導単色コピーが含まれます。

2010年に、コンロン、フォックス、スダコフは、一般誘導ラムゼイ数の現在の最良の上限であるr _ind ( H ) ≤ 2 ^{ck log k}への上限を改善しました。 ^[35] 2008年の以前の研究と同様に、彼らは、小さなλとエッジ密度1 ⁄ 2のすべての( n、d、λ)グラフ Gには、2色の任意のエッジカラーリングにおけるk頂点上のすべてのグラフの誘導された単色コピーが含まれていることを示しました。現在、 r _ind ( H ) ≤ 2 ^ckというエルデシュの予想は未解決のままであり、極限グラフ理論における重要な問題の1つです。

下限については、誘導されたラムゼー数が少なくとも対応するラムゼー数でなければならないという事実を除いて、一般的にはあまり知られていません。いくつかの下限は、いくつかの特殊なケースで得られています (特殊なケースを参照)。

誘導されたラムゼー数の一般的な境界はグラフのサイズに対して指数関数的ですが、グラフの特殊なクラス（特にスパースなもの）では動作が大きく異なります。これらのクラスの多くは、頂点の数に対して多項式的な誘導されたラムゼー数を持っています。

Hがk頂点上のサイクル、パス、またはスターである場合、 r _ind ( H )はkに関して線形であることが知られています。^[34]

Hがk頂点の木である場合、 r _ind ( H ) = O ( k ² log ² k )であることが知られています。^[36]また、r _ind ( H )は超線型（つまり、 r _ind ( H ) = ω( k )）であることも知られています。これは、通常のラムゼー数とは対照的であることに注意する必要があります。通常のラムゼー数では、バー・エルデシュ予想（現在証明済み）により、 r ( H ) は線型であることが示されています（木は1-退化しているため）。

頂点数がkで次数がΔに制限されたグラフHについて、 r _ind ( H ) ≤ cn ^{d (Δ)}が成り立つと予想された。この場合、 d はΔのみに依存する定数である。この結果は、 Łuczak と Rödl によって 1996 年に初めて証明され、d (Δ)は2 の塔のように成長し、高さはO (Δ ² )となる。^{[37]それ以来、} d (Δ)のより合理的な境界が得られている。2013 年に、 Conlon、 Fox、 Zhao は、スパース擬似ランダムグラフの計数補題を使用して、 r _ind ( H ) ≤ cn ^2Δ+8が成り立つことを示しました。ここで、指数は定数因数まで可能な限り最適です。^[38]

ラムゼー数と同様に、誘導ラムゼー数の概念をハイパーグラフやマルチカラー設定に一般化できます。

誘導されたラムゼーの定理を多色設定に一般化することもできます。グラフH ₁、H ₂、…、H _rについて、r _ind ( H ₁、H ₂、…、H _r )を、 Gの辺をr色に着色すると、すべての辺がi番目の色で着色される、H _iと同型の誘導サブグラフが含まれるようなグラフGの頂点の最小数として定義します( 1 ≤ i ≤ r )。 r _ind ( H ; q ) := r _ind ( H、H、…、H ) ( Hのq 個のコピー)とします。

2色の場合の境界を反復的に適用することで、高さ約log qの2つの塔に近いr _ind ( H ; q )の境界を導くことができる。現在知られている最良の境界はFoxとSudakovによるもので、 r _ind ( H ; q ) ≤ 2 ^{ck 3}を達成する。ここでkはHの頂点数、cはqのみに依存する定数である。^[39]

誘導ラムゼー数の定義をd 一様ハイパーグラフに拡張するには、単に文中の単語graph をhypergraphに変更します。さらに、前のサブセクションと同じ方法で誘導ラムゼー数の多色バージョンを定義できます。

H をk頂点のd均一ハイパーグラフとする。タワー関数t _r ( x )をt ₁ ( x ) = xおよびi ≥ 1に対してt _{i +1} ( x ) = 2 ^{t _i ( x )}として定義する。ハイパーグラフコンテナ法を使用して、 Conlon、 Dellamonica、 La Fleur、 Rödl、 Schacht は、d ≥ 3、q ≥ 2に対して、r _ind ( H ; q ) ≤ t _d ( ck )が成り立ち、c はdとqのみに依存することを示すことができた。特に、この結果は、 d = 3の場合の通常のラムゼー数の最もよく知られている境界を反映している。^[40]

ラムゼーの定理とも呼ばれるさらなる結果は、無限グラフに適用されます。有限グラフも議論されている文脈では、これはしばしば「無限ラムゼー定理」と呼ばれます。グラフの図式的表現によって提供される直感は、有限グラフから無限グラフに移行すると減少するため、この分野の定理は通常、集合論の用語で表現されます。^[41]

定理。をある無限集合とし、 （サイズの の部分集合）の要素を異なる色で塗ります。すると、の無限部分集合が存在し、 のサイズの部分集合はすべて同じ色になります。${\displaystyle X}$${\displaystyle [X]^{n}}$${\displaystyle X}$${\displaystyle n}$${\displaystyle c}$${\displaystyle M}$${\displaystyle X}$${\displaystyle n}$${\displaystyle M}$

証明: 証明は、部分集合のサイズnについての帰納法によって行われます。 n = 1の場合、このステートメントは、無限集合を有限個の集合に分割すると、そのうちの 1 つは無限であると言うことに相当します。これは明らかです。定理がn ≤ rに対して真であると仮定すると、 n = r + 1に対して証明します。Xの( r + 1)要素部分集合のc色付けが与えられ、a ₀をXの要素とし、Y = X \ { a ₀ } とします。次に、各r要素部分集合にa _{0 を}追加するだけで( Xの( r + 1)要素部分集合を取得するため) 、 Yのr要素部分集合のc色付けを誘導します。帰納法の仮説により、Yの無限部分集合Y ₁が存在し、Y ₁のすべてのr元部分集合は、誘導着色で同じ色に着色されます。したがって、要素a ₀と無限部分集合Y ₁が存在し、 Xのすべての( r + 1)元部分集合 ( Y _1のa ₀元とr元からなる)が同じ色になります。同じ議論により、Y ₁には要素a _{1があり、同じ特性を持つ}Y ₁の無限部分集合Y _{2 が}あります。帰納的に、シーケンス{ a ₀、a ₁、a ₂、 …}を取得し、各( r + 1)元部分集合( a _{i (1)}、a i ₍ 2 ₎、 …、a _{i ( r} + 1 ₎ )の色は、i ( 1)の値のみに依存します。さらに、この色が同じになるようなi ( n )の値は無限にあります。これらのa _{i ( n )}を取得して、目的の単色セットを取得します。

グラフに対するラムゼーの定理のより強力だが不均衡な無限形式であるエルデシュ・ドゥシュニク・ミラーの定理は、すべての無限グラフには可算無限独立集合、または元のグラフと同じ濃度の無限クリークのいずれかが含まれると述べています。^[42]

無限バージョンから有限ラムゼー定理を背理法によって演繹することは可能です。有限ラムゼー定理が偽であると仮定します。すると、整数c、n、Tが存在し、すべての整数kに対して、サイズTの単色セットのない[ k ] ^{( n )}のc -彩色が存在することになります。C _{k は}、サイズTの単色セットのない[ k ] ^{( n )}のc -彩色を表すも​​のとします。

任意のkについて、 C _{k +1}の彩色の[ k ] ^{( n )}への制限( k + 1を含むすべての集合の色を無視) は、 C _kの彩色です。⁠ ⁠ を${\displaystyle C_{k}^{1}}$C _{k +1}の彩色の制限であるC _kの彩色として定義します。C _{k +1}は空でないため、⁠ ⁠も空ではありません。 ${\displaystyle C_{k}^{1}}$

同様に、 ⁠ ⁠${\displaystyle C_{k+1}^{1}}$における任意の色付けの制限は⁠ ⁠${\displaystyle C_{k}^{1}}$に含まれるため、 ⁠ ⁠ を${\displaystyle C_{k}^{2}}$そのような制限すべての集合、つまり空でない集合として定義できます。これを続けて、すべての整数m、kに対して⁠ ⁠ を${\displaystyle C_{k}^{m}}$定義します。

さて、任意の整数kに対して、

${\displaystyle C_{k}\supseteq C_{k}^{1}\supseteq C_{k}^{2}\supseteq \cdots }$

そして各集合は空ではない。さらに、C _kは有限であり、

${\displaystyle |C_{k}|\leq c^{\frac {k!}{n!(k-n)!}}}$

これらすべての集合の共通部分は空ではないので、

${\displaystyle D_{k}=C_{k}\cap C_{k}^{1}\cap C_{k}^{2}\cap \cdots }$

すると、 D _kのすべての着色は、D _{k +1}の着色の制限になります。したがって、 D _kの着色をD _{k +1}の着色に非制限化し、これを続けると、サイズTの単色セットのないの着色が構築されます。これは無限ラムゼー定理に矛盾します。 ${\displaystyle \mathbb {N} ^{(n)}}$

適切な位相的観点をとれば、この議論は標準的なコンパクト性議論となり、定理の無限バージョンは有限バージョンを意味することを示す。^[43]

この定理はハイパーグラフにも拡張できます。mハイパーグラフとは、その「辺」がm頂点の集合であるグラフです。通常のグラフでは、辺は 2 頂点の集合です。ハイパーグラフに対するラムゼーの定理の完全な記述は、任意の整数mとc、および任意の整数n ₁、…、n _cに対して、整数R ( n ₁、…、n _c ; m)が存在し、順序R ( n ₁、…、n _c ; m )の完全mハイパーグラフのハイパー辺がc つの異なる色で色付けされている場合、 1 とcの間のあるiに対して、ハイパーグラフには、ハイパー辺がすべて色iである順序n _iの完全サブmハイパーグラフが必ず含まれている、というものです。この定理は通常、グラフの「ハイパー性」であるmに関する帰納法によって証明されます。証明の基本ケースはm = 2であり、これはまさに上記の定理です。

m = 3の場合、1つの非自明なラムゼー数の正確な値はR (4, 4; 3) = 13 であることが分かっています。この事実は、1991年にブレンダン・マッケイとスタニスワフ・ラジショフスキによって確立されました。 ^[44]さらに、R (4, 5; 3) ≥ 35、^[45] R (4, 6; 3) ≥ 63、R (5, 5; 3) ≥ 88 が成り立ちます。^[45]

有向グラフのラムゼー数を定義することもできます。これはP. エルデシュと L. モーザー (1964)によって導入されました。R ( n ) を、単方向アーク (「トーナメント」とも呼ばれます) と≥ Qノードを持つ任意の完全グラフに非巡回 (「推移的」とも呼ばれます) nノード サブトーナメントが含まれる最小の数Qとします。

これは、（上記で） R (n, n;2) と呼ばれているものの有向グラフ版です。R ( n , n ;2) は、Z個以上のノードを持つ完全無向グラフの辺の任意の 2 色塗りに、n 個のノード上の単色完全グラフが含まれる最小の数Zです。（2 つの可能な弧の色の有向版は弧の2 つの方向であり、「単色」の類似は「すべての弧の矢印が同じ方向を指す」、つまり「非巡回」です。）

R (0) = 0、R (1) = 1、R (2) = 2、R (3) = 4、R ( 4) = 8、R (5) = 14、R (6) = 28、34 ≤ R (7) ≤ 47となる。[ ^{46] [47]}

分割計算の観点で、ラムゼーの定理は、すべての有限なnとkに対して と述べることができます。Wacław Sierpiński は、 を示して、ラムゼーの定理が サイズのグラフには拡張されないことを示しました。特に、連続体仮説はを意味します。Stevo Todorčević は、実際にZFCでは、であることを示しました。これはよりもはるかに強い命題です。 Justin T. Moore はこの結果をさらに強化しました。 肯定的な面では、ラムゼー基数、は、関連する式を満たすように公理的に定義された大きな基数です。 ラムゼー基数の存在は ZFC では証明できません。 ${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$${\displaystyle \aleph _{1}}$${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$${\displaystyle \kappa }$${\displaystyle \kappa \rightarrow (\kappa )_{2}^{<\omega }}$