ラムゼーの定理

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

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

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

R (3, 3) ≤ 6を証明する問題は、 1953年のウィリアム・ローウェル・パトナム数学コンテストの問題の一つであり、1947年のハンガリー数学オリンピックの問題でもあった。

単色K ₃を含まないK ₁₆の 2 つの 3 色付け(色の同型性と順列まで)：ねじれていない色付け (左) とねじれた色付け (右)。

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

完全グラフの辺彩色が赤、緑、青の3色で行われているとします。さらに、辺彩色には単色の三角形がないとします。頂点vを選択します。頂点vに赤い辺を持つ頂点の集合を考えます。これはvの赤い近傍と呼ばれます。vの赤い近傍には赤い辺は含まれません。もし含まれていたら、その赤い辺の両端点と頂点vからなる赤い三角形ができてしまうからです。したがって、 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 であることを示すには、16 個_の頂点を持つ完全グラフに、単色三角形を避けるように 3 色で辺を彩色すれば十分です。K 16 には、いわゆる非ねじれ彩色とねじれ彩色という、ちょうど 2 つの彩色が存在することがわかります。両方の彩色は右側の図に示されており、左側が非ねじれ彩色、右側がねじれ彩色です。

K ₁₆の非ねじれ彩色またはねじれ彩色のいずれかの色を選択し、指定された色を持つ辺のみで構成されるグラフを考えると、クレブシュグラフが得られます。

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

また、 K ₁₄上で単色三角形を避ける 3 色の辺彩色は正確に 115 通り存在することが知られています。ただし、色の順列によって異なる辺彩色は同じものとみなします。

多色ラムゼイ数R(3,3,...,3)の数列を見つけることは興味深い。ここで、n個の 3 が含まれる。現在、この数列はn = 3までしか知られておらず、 n = 4のような早い値の範囲は比較的緩い。51 ≤ a (4) ≤ 62 である。（OEISの数列A003323）

2色の場合の定理は、r + sに関する帰納法によって証明できます。^{[ 2 ]}定義から、すべてのnに対してR ( n , 2) = R (2, n ) = nであることは明らかです。これが帰納法の開始です。R ( r , s ) の明示的な境界を見つけることによって、 R ( r − 1, s ) と R ( r , s − 1 )が存在することを証明します。帰納法の仮定により、R ( r − 1, s )とR ( r , s − 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に属します。グラフは${\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).}$前者の場合、M に赤いK _sがあれば、元のグラフにも赤い K s があり、これで終わりです。そうでなければ、M には青いK _{r − 1}があり、${\displaystyle M\cup \{v\}}$Mの定義により、青色のK _rを持つ。後者の場合も同様である。したがって、主張は正しく、2 色の場合の証明が完了した。

この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番目の頂点の次数である_場合、握手補題により、${\displaystyle \textstyle \sum _{i=1}^{t}d_{i}}$は偶数です。tが奇数であることから、偶数のd _iが存在するはずです。一般性を失うことなく、d ₁が偶数であり、MとN がそれぞれ青と赤のサブグラフの頂点 1 に接続する頂点であると仮定します。すると両方とも${\displaystyle |M|=d_{1}}$そして${\displaystyle |N|=t-1-d_{1}}$偶数である。鳩の巣原理によ​​り、${\displaystyle |M|\geq p-1,}$または${\displaystyle |N|\geq q.}$以来${\displaystyle |M|}$は偶数でp – 1は奇数なので、最初の不等式は強化できます。${\displaystyle |M|\geq p}$または${\displaystyle |N|\geq q.}$ 仮定する${\displaystyle |M|\geq p=R(r-1,s).}$すると、Mサブグラフには赤いK _sが存在し、証明は完了するか、または青いK _{r – 1}が存在し、それが頂点 1 とともに青いK _{r を}形成する。${\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})).}$

証明。完全グラフを考える。${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c}))}$頂点をc色で塗り、辺を c 色で塗ります。ここで「色覚異常」になり、c − 1とcが同じ色であると仮定します。したがって、グラフは( c − 1)色で塗ります。${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})),}$このようなグラフには、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}のいずれかが存在することがわかります。どちらの場合も証明は完了です。

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

エルデシュは、私たちよりもはるかに強力な異星人が地球に降り立ち、R (5, 5)の値を要求し、さもなければ地球を破壊すると脅迫する場面を想像するように私たちに促します。その場合、私たちはすべてのコンピューターとすべての数学者を動員してその値を求めるべきだと彼は主張します。しかし、代わりに彼らがR (6, 6)を要求したとしましょう。その場合、私たちは異星人を破壊しようと試みるべきだと彼は考えています。^{[ 5 ]}

高度なコンピュータプログラムは、すべての彩色を個別に調べてすべてを排除する必要はありませんが、既存のソフトウェアでは小規模な場合にのみ処理できる非常に困難な計算タスクです。各完全グラフK _{n には}1 / 2 ⁠ n ( n − 1)のエッジがあるため、総当たり検索を使用する場合は、( c色の場合) c ^{n ( n − 1)/2 個}のグラフを検索する必要があります。^{[ 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 つしかなく、 2.46 × 10 ^26種類の色付けのうち、 (4, 4, 17)グラフ (次数 17 のペイリー グラフ)は 1 つしかありません。^{[ 4 ]}したがって、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年、McKay、Radziszowski、Exooは、コンピュータ支援グラフ生成法を用いて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で与えられます。

ラムゼー数研究の発展に関する標準的な概説は、Radziszowski によるElectronic Journal of CombinatoricsのDynamic Survey 1であり、定期的に更新されている。 ^{[ 1 ] [ 13 ]}特に明記されていない限り、以下の表のエントリは 2024 年 6 月版から引用されている。（ R ( r , s ) = R ( s , r ) であるため、対角線に対して自明な対称性があることに注意。）

また、エルデシュは、パスグラフと頂点数がそれぞれ n 個と m 個の完全グラフに対して、 R( P _n , K _m ) = (n − 1).(m − 1) + 1であることを示したことも興味深い。同様に、チャヴァタルは、木グラフと頂点数がそれぞれ n 個と m 個の完全グラフに対して、R( T _n , K _m ) = (n − 1).(m − 1) + 1 であることを示した。これら 2 つの定理は、いくつかの特殊なグラフに対するラムゼー数を定式化した最良の例である。

不等式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}}$。

2024年の別のプレプリントで、Balister、Bollobás、Coampos、Griffiths、Hurley、Morris、Sahasrabudhe、およびTibaは、${\displaystyle \delta >0}$そのため${\displaystyle r}$-カラーラムジー番号${\displaystyle R_{r}(k)}$下から境界が定められている${\displaystyle \left(e^{-\delta }r^{r}\right)^{k}}$、特に

$${\displaystyle R_{r}(k)\leq \left(e^{-2^{-160}r^{-12}}r^{r}\right)^{k}}$$

十分に大きい${\displaystyle k}$[ ^{19 ]​}

Gupta、Ndiaye、Norin、Weiによる2024年のプレプリント^{[ 20 ]では、}${\displaystyle \delta }$に${\displaystyle -0.14e^{-1}\leq 20^{-1}}$、そして対角線ラムジー上限は

${\displaystyle R(s,s)\leq \left(4e^{-0.14e^{-1}}\right)^{s+o(s)}=3.7992...^{s+o(s)}}$

非対角ラムゼイ数R (3, t )については、それらは⁠ t ² / log t ⁠のオーダーであることが知られています。これは、 n頂点の三角形を含まないグラフにおける最小の独立数は次のようになると同等に述べることができます。

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

R (3, t )の上限はAjtai、Komlós ^、およびSzemerédi ^{[ 21 ]}によって与えられ、下限は元々Kim [ ^{22 ]によって得られ、暗黙の定数は}三角形フリーのプロセスを分析することによってFiz Pontiveros、Griffiths およびMorris ^{[ 23 ]}とBohmanおよびKeevash [ ^{24 ]}によって独立に改善されました。

一般に、より一般的な「Hフリープロセス」の研究により、一般的な非対角ラムゼイ数^{[ 25 ]} 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}}}.}$

特に、これは上限値を与える。${\displaystyle R(4,t)\leq c_{s}t^{3}(\log t)^{-2}}$. Mattheus と Verstraete (2024) ^{[ 26 ] [ 27 ]}は、下限値を与えた。 ${\displaystyle R(4,t)\geq c'_{s}t^{3}(\log t)^{-4}}$漸近挙動を決定する${\displaystyle R(4,t)}$対数因子まで、そして下限が形になるという証明に250ドルを提示したエルデシュの問題を解決します${\displaystyle c'_{s}t^{3}(\log t)^{-d}}$[ ^{28 ] [ 29 ]​}

ラムジーの数字${\displaystyle R(3,8)}$そして${\displaystyle R(3,9)}$は正式に28と36であることが検証されている。^{[ 30 ]}この検証は、ブール充足可能性（SAT）ソルビングとコンピュータ代数システム（CAS）の組み合わせを使用して達成された。証明はSAT+CASアプローチを使用して自動的に生成され、最初の認証可能な証明となった。${\displaystyle R(3,8)=28}$そして${\displaystyle R(3,9)=36}$検証プロセス${\displaystyle R(3,8)}$そして${\displaystyle R(3,9)}$SATソルバーとコンピュータ代数システムを統合したSAT+CASフレームワークMathCheckを使用して検証を行った。${\displaystyle R(3,8)=28}$約8時間の実時間で完了し、合計5.8 GiBの証明サイズが生成されました。${\displaystyle R(3,9)=36}$計算負荷が著しく高く、実時間で26時間かかり、289 GiBの証明データを生成した。これらの結果の正しさは、DRAT-trim証明チェッカーの修正版を使用して独立して検証された。^{[ 30 ]}

ラムジーの数字${\displaystyle R(4,5)}$は正式には 25 であることが検証されている。^{[ 31 ]} 1995 年に McKay と Radziszowski によって開発された元の証明は、高レベルの数学的議論と計算手順を組み合わせ、プログラミング エラーの可能性を減らすために複数の独立した実装を使用した。正式な証明はHOL4対話型定理証明器を使用して実行され、エラーの可能性は HOL4 カーネルに限定された。著者らは、元のアルゴリズムを直接検証するのではなく、HOL4 の MiniSat SAT ソルバーへのインターフェースを使用して、キー グルーイング補題を正式に証明した。

H をn個の頂点を持つグラフとする。このとき、2 色を用いてGの辺を彩色すると、Hの単色誘導コピー(すなわち、 Hと同型で辺が単色であるGの誘導部分グラフ) が含まれるようなグラフGが存在する。G の最小頂点数は誘導ラムゼイ数r _ind ( H )である。

時には、問題の非対称バージョンも考慮します。グラフGの辺を赤または青のみで彩色した場合、Xの赤誘導_部分グラフまたはYの青誘導部分グラフが含まれるような、グラフGの最小頂点数をr ind ( X , Y )と定義します。

ラムゼーの定理と同様に、すべてのグラフHに対して誘導ラムゼー数が存在するかどうかは、事前には不明である。1970 年代初頭、エルデシュ、ハジナルとポサ、ドイバー、レードルは、それぞれ独立にこれが正しいことを証明した。^{[ 32 ] [ 33 ] [ 34 ]}しかし、元の証明は誘導ラムゼー数に対してひどい境界 (例えば、2 の塔) を与えた。より良い境界が得られるかどうかを問うことは興味深い。1974 年、ポール・エルデシュは、 k 個の頂点を持つすべてのグラフH がr _ind ( H ) ≤ 2 ^ckを満たすような定数cが存在すると予想した。^{[ 35 ]}この予想が正しい場合、完全グラフはこの形式の下限 (実際にはラムゼー数と同じ) を達成するため、定数cを除いて最適となる。しかし、この推測は現時点ではまだ確定していない。

1984年、エルデシュとハジナルは境界を証明したと主張した^{[ 36 ]}

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

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

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

2010年、Conlon、Fox、Sudakovは境界をr _ind ( H ) ≤ 2 ^{ck log k}に改善することができ、これは一般的な誘導ラムゼイ数の現在の最良の上限のままである。^{[ 39 ]} 2008年の以前の研究と同様に、彼らはλが小さくエッジ密度が1/2であるすべての( n , d ,λ)グラフGには、 2色の任意のエッジ彩色でk個の頂点を持つすべてのグラフの誘導単色コピーが含まれていることを示した。現在、 r _ind ( H ) ≤ 2 ^ckというErdősの予想は未解決のままであり、極値グラフ理論の重要な問題の1つである。

下限値については、誘導ラムゼイ数が対応するラムゼイ数以上でなければならないという事実を除いて、一般にはあまり知られていない。いくつかの特殊なケースについては、下限値が得られている（「特殊なケース」を参照）。

ラムゼイ数を計算するのは非常に難しい場合がある。実際、不等式は

${\displaystyle 2^{n/2}\leq R(K_{n},K_{n})\leq 2^{2n}}$

は 1947 年にエルデシュによって証明されました^{[ 40 ]}

誘導ラムゼイ数の一般的な上限はグラフのサイズに対して指数関数的に増加するが、特殊なグラフクラス（特に疎なグラフ）ではその挙動は大きく異なる。これらのクラスの多くでは、誘導ラムゼイ数は頂点の数に対して多項式的に増加する。

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

Hがk個の頂点を持つ木である場合、r _ind ( H ) = O ( k ² log ² k )であることが知られています。^{[ 41 ]}また、r _ind ( H )は超線形であることも知られています(つまり、 r _ind ( H ) = ω( k ) )。これは、通常のラムゼー数とは対照的であることに注意してください。通常のラムゼー数では、Burr–Erdős 予想(現在は証明済み) により、 r ( H )は線形であることがわかっています(木は 1-退化しているため)。

頂点数kと次数Δが制限されたグラフHに対して、Δのみに依存する定数dに対してr _ind ( H ) ≤ cn ^{d (Δ)}であると予想されていました。この結果は 1996 年に Łuczak と Rödl によって初めて証明され、d (Δ)は高さO (Δ ² )の2 の塔として成長しました。^{[ 42 ]}それ以降、d (Δ)のより妥当な境界が得られました。2013 年に Conlon、Fox、Zhao は、疎な擬似ランダムグラフの計数補題を使用して、r _ind ( H ) ≤ cn ^2Δ+8であることを示しました。ここで指数は定数係数を除いて最良です。^{[ 43 ]}

ラムゼー数と同様に、誘導ラムゼー数の概念をハイパーグラフや多色設定に一般化することができる。

さらに、ラムゼーの定理とも呼ばれる結果が無限グラフにも適用されます。有限グラフも議論されている文脈では、「無限ラムゼーの定理」と呼ばれることがよくあります。グラフの図による表現から得られる直感は、有限グラフから無限グラフに移行すると弱まるため、この分野の定理は通常、集合論の用語で表現されます。^{[ 46 ]}

定理。${\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 _{1が存在し、} Y ₁のすべてのr要素部分集合は、誘導彩色において同じ色に彩色されます。したがって、要素a ₀と無限部分集合Y _{1が存在し、} a ₀とY ₁のr個の要素からなるXのすべての( r + 1)要素部分集合は同じ色になります。同様の議論により、 Y ₁の要素a ₁と、同じ性質を持つY ₁の無限部分集合Y ₂が存在します。帰納的に、i ( ₁₎ < i (2) < _… < _i ( r + 1)を満たす各( r + 1)要素部分集合( a _{i (1)}、a _{i (2)}、 …、a _{i ( r + 1)} )の色はi (1 )の値のみに依存するような数列 { a 0 、 a 1 、 a 2 、 … }を得ます。さらに、この色が同じになるようなi ( n )の値は無限に存在します。これらのi _{( n )を選択して、}目的の単色セットを取得します。

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

この定理はハイパーグラフにも拡張できます。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 年に Brendan McKay と Stanisław Radziszowski によって確立されました。^{[ 49 ]}さらに、次のことがわかっています。R ( 4, 5; 3) ≥ 35、^{[ 50 ]} R (4, 6; 3) ≥ 63およびR (5, 5; 3) ≥ 88。^{[ 50 ]}

有向グラフに対してラムゼー数を定義することも可能であり、これらはP. ErdősとL. Moser ( 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 である。^{[ 51 ] [ 52 ]}

分割計算の観点から言えば、ラムゼーの定理は次のように述べることができる。${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$すべての有限なnとkに対して。ヴァツワフ・シェルピンスキは、ラムゼーの定理はサイズのグラフには適用されないことを示した。${\displaystyle \aleph _{1}}$示すことによって${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$特に、連続体仮説は、${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$ステボ・トドルチェヴィッチは、実際にはZFCでは、${\displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$より強い声明${\displaystyle \aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}}$ジャスティン・T・ムーアはこの結果をさらに強化した。良い点としては、ラムジーカーディナルは大型のカーディナルである。${\displaystyle \kappa }$関連する公式を満たすように公理的に定義されている。${\displaystyle \kappa \rightarrow (\kappa )_{2}^{<\omega }}$ZFCではラムゼイ枢機卿の存在は証明できない。