نظرية رامزي

لنفترض أن حواف رسم بياني كامل بستة رؤوس ملونة بالأحمر والأزرق. اختر رأسًا، v . هناك خمس حواف متصلة بـ v ، وبالتالي (بحسب مبدأ التوزيع ) يجب أن تكون ثلاث منها على الأقل بنفس اللون. دون فقدان للعمومية، يمكننا افتراض أن ثلاثًا على الأقل من هذه الحواف، التي تربط الرأس v بالرؤوس r و s و t ، زرقاء. (وإلا، نبدل الأحمر والأزرق فيما يلي). إذا كانت أي من الحواف ( rs ) أو ( rt ) أو ( st ) زرقاء أيضًا، فسنحصل على مثلث أزرق بالكامل. وإذا لم تكن كذلك، فإن هذه الحواف الثلاث ستكون حمراء، وسنحصل على مثلث أحمر بالكامل. بما أن هذه الحجة تنطبق على أي تلوين، فإن أي K _{6 يحتوي على} K ₃ أحادي اللون ، وبالتالي R (3, 3) ≤ 6. يُطلق على النسخة الشائعة من هذه النظرية اسم نظرية الأصدقاء والغرباء .

يُمكن استخدام برهان بديل يعتمد على العدّ المزدوج . ويتم ذلك كالتالي: احسب عدد الثلاثيات المرتبة من الرؤوس x و y و z بحيث يكون الضلع ( xy ) أحمر والضلع ( yz ) أزرق. أولًا، أي رأس مُعطى سيكون في منتصف إحدى الثلاثيات التالية: 0 × 5 = 0 (جميع الأضلاع الخارجة من الرأس لها نفس اللون)، أو 1 × 4 = 4 (أربعة أضلاع لها نفس اللون، وضلع واحد بلون مختلف)، أو 2 × 3 = 6 (ثلاثة أضلاع لها نفس اللون، وضلعان بلون مختلف). وبالتالي، يوجد على الأكثر 6 × 6 = 36 ثلاثية من هذا النوع. ثانيًا، بالنسبة لأي مثلث غير أحادي اللون ( xyz ) ، يوجد ثلاثيتان فقط من هذا النوع. وبالتالي، يوجد على الأكثر 18 مثلثًا غير أحادي اللون. إذن، يوجد على الأقل مثلثان من أصل 20 مثلثًا في _K6 أحاديا اللون.

على النقيض، من الممكن تلوين K ₅ بلونين دون إنشاء أي K ₃ أحادي اللون ، مما يدل على أن R (3, 3) > 5. يظهر التلوين الفريد ^{[ b ]} على اليمين. وبالتالي، R (3, 3) = 6 .

كانت مهمة إثبات أن R (3, 3) ≤ 6 إحدى مسائل مسابقة ويليام لويل بوتنام الرياضية في عام 1953، وكذلك في أولمبياد الرياضيات المجري في عام 1947.

اللونان الوحيدان اللذان يحتويان على 3 ألوان من K ₁₆ بدون لون أحادي K ₃ ، حتى التماثل وتبديل الألوان: التلوين غير الملتوي (يسار) والتلوين الملتوي (يمين).

عدد رامزي متعدد الألوان هو عدد رامزي يستخدم 3 ألوان أو أكثر. يوجد (باستثناء التناظرات) عددان فقط من أعداد رامزي متعددة الألوان غير التافهة التي تُعرف قيمتها الدقيقة، وهما R (3, 3, 3) = 17 و R (3, 3, 4) = 30. ^{[ 1 ]}

لنفترض أن لدينا تلوينًا لحواف رسم بياني كامل باستخدام ثلاثة ألوان: الأحمر والأخضر والأزرق. ولنفترض أيضًا أن هذا التلوين لا يحتوي على مثلثات أحادية اللون. لنختر رأسًا v . لننظر إلى مجموعة الرؤوس التي لها حافة حمراء متصلة بالرأس v . تُسمى هذه المجموعة الجوار الأحمر للرأس v . لا يمكن أن يحتوي الجوار الأحمر للرأس v على أي حواف حمراء، وإلا سيتكون مثلث أحمر من طرفي تلك الحافة الحمراء والرأس v . بالتالي، فإن تلوين الحواف الناتج في الجوار الأحمر للرأس v يحتوي على حواف ملونة بلونين فقط، وهما الأخضر والأزرق. بما أن R (3, 3) = 6 ، فإن الجوار الأحمر للرأس v يمكن أن يحتوي على 5 رؤوس على الأكثر. وبالمثل، فإن الجوارين الأخضر والأزرق للرأس v يمكن أن يحتوي كل منهما على 5 رؤوس على الأكثر. بما أن كل رأس، باستثناء الرأس v نفسه، يقع في إحدى الجوارات الحمراء أو الخضراء أو الزرقاء للرأس v ، فإن الرسم البياني الكامل يمكن أن يحتوي على 16 رأسًا على الأكثر (1 + 5 + 5 + 5). وبالتالي، فإن R (3, 3, 3) ≤ 17 .

لإثبات أن R (3, 3, 3) = 17 ، يكفي رسم تلوين للحواف على الرسم البياني الكامل ذي 16 رأسًا باستخدام 3 ألوان، بحيث يتجنب المثلثات أحادية اللون. يتضح وجود نوعين فقط من هذا التلوين على K16 _، وهما التلوين غير الملتوي والتلوين الملتوي. يظهر كلا التلوينين في الأشكال على اليمين، حيث يظهر التلوين غير الملتوي على اليسار، والتلوين الملتوي على اليمين.

إذا اخترنا أي لون من ألوان التلوين غير الملتوية أو الملتوية على K ₁₆ ، ونظرنا في الرسم البياني الذي تكون حوافه هي تلك الحواف التي لها اللون المحدد، فسنحصل على الرسم البياني Clebsch .

من المعروف أن هناك لونين فقط للحواف بثلاثة ألوان على K ₁₅ يتجنبان المثلثات أحادية اللون، والتي يمكن إنشاؤها عن طريق حذف أي رأس من التلوينات غير الملتوية والملتوية على K ₁₆ ، على التوالي.

ومن المعروف أيضًا أن هناك 115 لونًا للحواف بثلاثة ألوان على K ₁₄ تتجنب المثلثات أحادية اللون، بشرط أن نعتبر ألوان الحواف التي تختلف بتبديل الألوان متطابقة.

من المهم إيجاد متتالية أعداد رامزي متعددة الألوان R(3,3,...,3) ، حيث يوجد n عددًا من الأعداد 3. المتتالية معروفة حاليًا حتى n = 3 فقط ، مع حدود غير دقيقة نسبيًا للقيم عند n = 4 : 51 ≤ a (4) ≤ 62. ( المتتالية A003323 في OEIS )

يمكن إثبات نظرية حالة اللونين بالاستقراء على 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) رأسًا، حيث تكون حوافها ملونة بلونين. اختر رأسًا v من الرسم البياني، وقسّم الرؤوس المتبقية إلى مجموعتين M و N ، بحيث يكون لكل رأس w ، ينتمي w إلى M إذا كانت الحافة ( vw ) زرقاء، وينتمي w إلى N إذا كانت الحافة ( vw ) حمراء. ولأن الرسم البياني يحتوي على${\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 حمراء _، فإن المخطط الأصلي يكون كذلك، وبذلك نكون قد انتهينا. أما في الحالة الأخرى، فإن _للمخطط M قيمة K زرقاء _، وبالتالي...${\displaystyle M\cup \{v\}}$يمتلك اللون الأزرق K _r وفقًا لتعريف M. الحالة الأخيرة مماثلة. وبالتالي، فإن الادعاء صحيح، وقد أكملنا البرهان للونين.

في هذه الحالة ذات اللونين، إذا كان 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 رأسًا. إذا كانت 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 زوجيًا و p – 1 فرديًا، فيمكن تقوية المتباينة الأولى، لذا إما${\displaystyle |M|\geq p}$أو${\displaystyle |N|\geq q.}$ يفترض${\displaystyle |M|\geq p=R(r-1,s).}$إذن، إما أن يكون للرسم البياني الفرعي M _رأس K أحمر، وبذلك يكتمل البرهان، أو أن يكون له _رأس K أزرق _، والذي يشكل مع الرأس 1 _رأس K أزرق .${\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 − 1 و c هما نفس اللون. وبالتالي، يصبح الرسم البياني الآن ملونًا بـ ( c − 1) . وذلك بسبب تعريف${\displaystyle R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})),}$يحتوي هذا الرسم البياني إما على K _{_n i} أحادي اللون باللون i لبعض 1 ≤ i ≤ c − 2، _أو على K _{_R ( nc − 1 , nc )} ملونًا باللون "الضبابي". في الحالة الأولى، نكون قد انتهينا. أما في الحالة الثانية، فنستعيد وضوحنا ونرى من تعريف R ( nc _{− 1 ,} nc ) أنه يجب أن يكون لدينا إما K _{n  c − 1} أحادي اللون ( c − 1) أو K_nc _أحادي اللون 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 n ( n -1)/2 رسمًا بيانيًا للبحث فيها (عن c لونًا) إذا تم استخدام البحث الشامل. [ 6 ] وبالتالي، فإن تعقيد البحث في جميع الرسوم البيانية الممكنة (باستخدام البحث الشامل ) هو O ( c n ² ) عن c تلوينًا و n عقدة على الأكثر.

من غير المرجح أن يتحسن الوضع مع ظهور الحواسيب الكمومية . إذ أن إحدى أشهر خوارزميات البحث عن مجموعات البيانات غير المهيكلة لا تُظهر سوى تسارع تربيعي ( انظر خوارزمية غروفر ) مقارنةً بالحواسيب التقليدية، مما يجعل وقت الحساب لا يزال أُسّيًا بالنسبة لعدد العُقد. ^{[ 7 ] [ 8 ]}

كما هو موضح أعلاه، R (3, 3) = 6. من السهل إثبات أن R (4, 2) = 4 ، وبشكل أعم، أن R ( s , 2) = s لجميع قيم s : يُعد الرسم البياني المكون من s − 1 عقدة مع جميع الحواف الملونة باللون الأحمر مثالًا مضادًا، ويثبت أن R ( s , 2) ≥ s ؛ من بين تلوينات الرسم البياني المكون من s عقدة، يحتوي التلوين الذي يحتوي على جميع الحواف الملونة باللون الأحمر على رسم بياني فرعي أحمر مكون من s عقدة، بينما تحتوي جميع التلوينات الأخرى على رسم بياني فرعي أزرق مكون من عقدتين (أي زوج من العقد المتصلة بحافة زرقاء).

باستخدام متباينات الاستقراء وقاعدة المصافحة ، يمكن استنتاج أن R (4, 3) ≤ R (4, 2) + R (3, 3) − 1 = 9 ، وبالتالي R (4, 4) ≤ R (4, 3) + R (3, 4) ≤ 18. يوجد رسمان بيانيان فقط من النوع (4, 4, 16) (أي تلوينان لرسم بياني كامل مكون من 16 عقدة بدون رسوم بيانية فرعية كاملة حمراء أو زرقاء مكونة من 4 عقد) من بين 6.4 × 10²² ^{تلوينًا} مختلفًا لرسوم بيانية مكونة من 16 عقدة، ورسم بياني واحد فقط من النوع (4, 4, 17) ( رسم بياني بالي من الرتبة 17) من بين 2.46 × ^10²⁶ تلوينًا. ^{[ 4 ]} وبالتالي، R (4, 4) = 18 .

تم إثبات حقيقة أن R (4, 5) = 25 لأول مرة بواسطة بريندان مكاي وستانيسواف رادزيسوفسكي في عام 1995. ^{[ 9 ]}

القيمة الدقيقة لـ R (5, 5) غير معروفة، على الرغم من أنه من المعروف أنها تقع بين 43 (جيفري إكسو (1989) ^{[ 10 ]} ) و 46 (أنجيلتفيت وماكاي (2024) ^{[ 11 ]} )، شاملة.

في عام ١٩٩٧، استخدم ماكاي ورادزيسوفسكي وإكسو أساليب توليد الرسوم البيانية بمساعدة الحاسوب للتكهن بأن R (5, 5) = 43. تمكنوا من إنشاء ٦٥٦ رسمًا بيانيًا بالضبط (٥، ٥، ٤٢) ، ووصلوا إلى نفس مجموعة الرسوم البيانية عبر مسارات مختلفة. لا يمكن تمديد أي من هذه الرسوم البيانية الـ ٦٥٦ إلى رسم بياني (٥، ٥، ٤٣) . ^{[ ١٢ ]}

في عام 2025، أجرى تامبوريني حسابًا عدديًا استدلاليًا حدد 45 باعتباره "المرشح الأكثر ترجيحًا" لـ R (5, 5 ) . ^{[ 13 ]}

بالنسبة لـ R ( r , s ) حيث r و s > 5 ، لا تتوفر سوى حدود ضعيفة. لم يتم تحسين الحدود الدنيا لـ R (6, 6) و R (8, 8) منذ عامي 1965 و 1972 على التوالي. ^{[ 1 ]}

يُبيّن الجدول أدناه قيم R ( r , s ) حيث r , s ≤ 10. وفي حال عدم معرفة القيمة الدقيقة، يُدرج الجدول أفضل الحدود المعروفة. أما قيم R ( r , s ) حيث r < 3، فتُعطى بالصيغة R (1, s ) = 1 و R (2, s ) = s لجميع قيم s .

يُعدّ المسح الديناميكي 1، المنشور في المجلة الإلكترونية للتوافقية (Electronic Journal of Combinatorics ) بقلم رادزيسوفسكي، مرجعًا أساسيًا في دراسة تطور أبحاث أعداد رامزي ، ويتم تحديثه دوريًا. ^{[ 1 ] [ 14 ]} ما لم يُذكر خلاف ذلك، فإنّ البيانات الواردة في الجدول أدناه مأخوذة من عدد يونيو 2024. (لاحظ وجود تناظر بسيط حول القطر الرئيسي، حيث إنّ R ( r , s ) = R ( s , r ) ).

ومن المثير للاهتمام أيضًا أن إردوش أثبت أن R( P _{_n} , K_{_m} ) = (n − 1)(m − 1) + 1، وذلك لمسار ورسم بياني كامل ذي n و m رأس على التوالي. كما أثبت تشفاتال أيضًا أن R( T _{_n} , K_{_m} ) = (n − 1)(m − 1) + 1، وذلك لشجرة ورسم بياني كامل ذي n و m رأس على التوالي. تُعد هاتان النظريتان أفضل مثالين على صياغة أعداد رامزي لبعض الرسوم البيانية الخاصة.

يمكن تطبيق المتباينة 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، وكان له دورٌ أساسي في تقديمه للطريقة الاحتمالية. ثمة فجوة كبيرة بين هذين الحدين: على سبيل المثال، عندما 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 من قِبل كامبوس وغريفيث وموريس وساهسرابودهي أنها حققت تقدمًا هائلاً باستخدام بنية خوارزمية تعتمد على هيكل بياني يُسمى " كتابًا "، ^{[ 18 ] [ 19 ]} مما يحسن الحد الأعلى لـ

${\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، أظهر باليستر، وبولوباس، وكوامبوس، وغريفيثس، وهيرلي، وموريس، وساهسرابودهي، وتيبا وجود${\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}$[ ^{20 ]​}

تزعم دراسة أولية نُشرت عام 2024 ^{[ 21 ]} من قِبل غوبتا، ندياي، نورين، ووي، تحسناً في${\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 ، ^{[ 22 ]} وتم الحصول على الحد الأدنى في الأصل بواسطة Kim ، ^{[ 23 ]} وتم تحسين الثابت الضمني بشكل مستقل بواسطة Fiz Pontiveros و Griffiths و Morris ، ^{[ 24 ]} و Bohman و Keevash ، ^{[ 25 ]} من خلال تحليل العملية الخالية من المثلث.

بشكل عام، أدت دراسة "العملية الخالية من H " الأكثر عمومية إلى تحديد أفضل الحدود الدنيا التقاربية المعروفة لأعداد رامزي غير القطرية العامة، ^{[ 26 ]} 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}}$قدّم ماثيوس وفيرستريت (2024) ^{[ 27 ] [ 28 ]} حدًا أدنى قدره ${\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}}$[ ^{29 ] [ 30 ]​}

رقم رامزي${\displaystyle R(3,8)}$و${\displaystyle R(3,9)}$تم التحقق رسميًا من أن القيمتين هما 28 و36. ^{[ 31 ]} وقد تحقق هذا التحقق باستخدام مزيج من حل مسائل الإرضاء المنطقي (SAT) وأنظمة الجبر الحاسوبي (CAS). تم إنشاء البرهان تلقائيًا باستخدام منهجية SAT+CAS ، مما يمثل أول برهان قابل للتصديق لـ${\displaystyle R(3,8)=28}$و${\displaystyle R(3,9)=36}$عملية التحقق من${\displaystyle R(3,8)}$و${\displaystyle R(3,9)}$أُجريت عملية التحقق باستخدام إطار عمل SAT+CAS MathCheck، الذي يدمج برنامج حل مسائل SAT مع نظام جبر حاسوبي . وقد تم التحقق من ذلك لـ${\displaystyle R(3,8)=28}$اكتملت العملية في حوالي 8 ساعات من وقت التشغيل الفعلي، مما أنتج حجم إثبات إجمالي قدره 5.8 جيجابايت. التحقق من${\displaystyle R(3,9)=36}$كانت العملية أكثر استهلاكًا للموارد الحاسوبية بشكل ملحوظ، إذ استغرقت 26 ساعة من وقت التشغيل الفعلي وأنتجت 289 جيجابايت من بيانات الإثبات. وقد تم التحقق من صحة هذه النتائج بشكل مستقل باستخدام نسخة معدلة من مدقق إثبات DRAT-trim . ^{[ 31 ]}

رقم رامزي${\displaystyle R(4,5)}$تم التحقق رسميًا من أن القيمة تساوي 25. ^{[ 32 ]} جمع البرهان الأصلي، الذي طوره ماكاي ورادزيسوفسكي عام 1995، بين حجج رياضية متقدمة وخطوات حسابية، واستخدم تطبيقات مستقلة متعددة لتقليل احتمالية حدوث أخطاء برمجية. أُجري البرهان الرسمي باستخدام برنامج إثبات النظريات التفاعلي HOL4 ، مما حدّ من احتمالية حدوث أخطاء في نواة HOL4. بدلًا من التحقق المباشر من الخوارزميات الأصلية، استخدم المؤلفان واجهة HOL4 مع برنامج MiniSat SAT لحل مسائل SAT لإثبات نظريات الربط الرئيسية رسميًا.

ليكن H مخططًا بيانيًا على n رأسًا. عندئذٍ، يوجد مخطط بياني G بحيث يحتوي أي تلوين لحواف G باستخدام لونين على نسخة مستحثة أحادية اللون من H (أي مخطط فرعي مستحث من G بحيث يكون متماثلًا مع H وحوافه أحادية اللون). أصغر عدد ممكن من رؤوس G هو عدد رامزي المستحث r _ind ( H ) .

أحيانًا، ننظر أيضًا في النسخة غير المتناظرة من المسألة. نُعرّف r _ind ( X , Y ) بأنه أصغر عدد ممكن من رؤوس الرسم البياني G بحيث يحتوي كل تلوين لحواف G باستخدام اللون الأحمر أو الأزرق فقط على رسم بياني فرعي مستحث باللون الأحمر من X أو رسم بياني فرعي مستحث باللون الأزرق من Y.

على غرار نظرية رامزي، يبقى من غير الواضح مسبقًا ما إذا كانت أعداد رامزي المستحثة موجودة لكل رسم بياني H. في أوائل سبعينيات القرن الماضي، أثبت كل من إردوش ، وهاينال وبوسا ، وديوبر، ورودل ، بشكل مستقل، صحة ذلك. ^{[ 33 ] [ 34 ] [ 35 ]} مع ذلك، أعطت البراهين الأصلية حدودًا سيئة للغاية (مثل أبراج الاثنين ) لأعداد رامزي المستحثة. ومن المثير للاهتمام التساؤل عما إذا كان بالإمكان تحقيق حدود أفضل. في عام 1974، افترض بول إردوش وجود ثابت c بحيث يحقق كل رسم بياني H على k رأس الشرط r _ind ( H ) ≤ 2 ^ck . ^{[ 36 ]} إذا كان هذا الافتراض صحيحًا، فسيكون مثاليًا حتى الثابت c لأن الرسم البياني الكامل يحقق حدًا أدنى من هذا الشكل (في الواقع، هو نفسه عدد رامزي). ومع ذلك، لا يزال هذا التخمين مفتوحاً حتى الآن.

في عام 1984، ادعى إردوش وهاينال أنهما أثبتا الحد ^{[ 37 ].}

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

مع ذلك، كان ذلك لا يزال بعيدًا عن الحد الأسي الذي افترضه إردوش. ولم يتحقق اختراق كبير إلا في عام 1998 على يد كوهاياكاوا وبروميل ورودل، الذين أثبتوا أول حد شبه أسي لـ r _ind ( H ) ≤ 2 ^{ck (log k ) 2} لثابت ما c . تمثلت طريقتهم في دراسة رسم بياني عشوائي مناسب مُنشأ على مستويات إسقاطية، وإثبات أنه يمتلك الخصائص المطلوبة باحتمالية غير صفرية. وقد استُخدمت فكرة استخدام الرسوم البيانية العشوائية على المستويات الإسقاطية سابقًا في دراسة ^خصائص رامزي فيما يتعلق بتلوين الرؤوس ومسألة رامزي المُستحثة على الرسوم البيانية ذات الدرجة المحدودة H. ^{[ 38} ]

ظلّ حدّ كوهاياكاوا وبروميل ورودل أفضل حدّ عام لعقد من الزمان. في عام 2008، قدّم فوكس وسوداكوف بناءً صريحًا لأعداد رامزي المُستحثّة بنفس الحدّ. ^{[ 39 ]} في الواقع، أثبتا أن كل رسم بياني G من النوع ( n , d , λ) ذي قيمة λ صغيرة وقيمة d مناسبة ، يحتوي على نسخة أحادية اللون مُستحثّة لأي رسم بياني ذي k رأسًا، بأي تلوين لحواف G بلونين. على وجه الخصوص، بالنسبة لثابت c ما ، يكون رسم بالي البياني ذو n ≥ 2ck ^{log 2 k رأسًا} بحيث تحتوي جميع تلوينات حوافه بلونين على نسخة أحادية اللون مُستحثّة لكل رسم بياني ذي k رأسًا .

في عام 2010، تمكن كونلون ، فوكس، وسوداكوف من تحسين الحد الأعلى إلى r _ind ( H ) ≤ 2 ^{ck log k} ، والذي لا يزال أفضل حد أعلى حالي لأعداد رامزي المستحثة العامة. ^{[ 40 ]} على غرار العمل السابق في عام 2008، أظهروا أن كل رسم بياني G من النوع ( n , d , λ) ذي قيمة λ صغيرة وكثافة حواف 1/2 يحتوي على نسخة أحادية اللون مستحثة من كل رسم بياني ذي k رأس بأي تلوين للحواف بلونين. حاليًا، لا تزال فرضية إردوش بأن r _ind ( H ) ≤ 2 ^ck مفتوحة، وهي إحدى المشكلات المهمة في نظرية الرسوم البيانية المتطرفة .

فيما يخص الحدود الدنيا، لا يُعرف الكثير بشكل عام باستثناء حقيقة أن أعداد رامزي المستحثة يجب أن تكون على الأقل أعداد رامزي المقابلة. وقد تم الحصول على بعض الحدود الدنيا لبعض الحالات الخاصة (انظر الحالات الخاصة).

قد يكون حساب عدد رامزي صعبًا للغاية في بعض الأحيان. في الواقع، المتباينات

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

تم إثباتها بواسطة إردوس في عام 1947. ^{[ 41 ]}

بينما تكون الحدود العامة لأعداد رامزي المستحثة أسية بالنسبة لحجم الرسم البياني، فإن السلوك يختلف اختلافًا كبيرًا في فئات خاصة من الرسوم البيانية (وخاصة الرسوم البيانية المتفرقة). العديد من هذه الفئات لها أعداد رامزي مستحثة متعددة الحدود بالنسبة لعدد الرؤوس.

إذا كانت H عبارة عن دورة أو مسار أو نجمة على k رأس، فمن المعروف أن r _ind ( H ) خطي في k . ^{[ 39 ]}

إذا كانت H شجرة ذات k رأسًا، فمن المعروف أن r _ind ( H ) = O ( k ² log ² k ) . ^{[ 42 ]} ومن المعروف أيضًا أن r _ind ( H ) دالة فائقة الخطية (أي r _ind ( H ) = ω( k ) ). تجدر الإشارة إلى أن هذا يتناقض مع أعداد رامزي المعتادة، حيث تنص تخمينات بور-إردوش (التي تم إثباتها الآن) على أن r ( H ) دالة خطية (لأن الأشجار منحلة من الدرجة 1 ).

بالنسبة للرسوم البيانية H ذات عدد رؤوس k ودرجة محدودة Δ ، تم افتراض أن r _ind ( H ) ≤ cn ^{d (Δ)} ، حيث d ثابت يعتمد فقط على Δ . وقد أثبت لوتشاك ورودل هذه النتيجة لأول مرة عام 1996، حيث تنمو d (Δ) كسلسلة من اثنينات بارتفاع O (Δ ² ) . ^{[ 43 ]} ومنذ ذلك الحين، تم الحصول على حدود أكثر منطقية لـ d (Δ) . في عام 2013، أظهر كونلون وفوكس وتشاو، باستخدام مبرهنة العد للرسوم البيانية شبه العشوائية المتفرقة، أن r _ind ( H ) ≤ cn ^2Δ+8 ، حيث يكون الأس في أفضل حالاته حتى عوامل ثابتة. ^{[ 44 ]}

على غرار أرقام رامزي، يمكننا تعميم مفهوم أرقام رامزي المستحثة ليشمل الرسوم البيانية الفائقة والإعدادات متعددة الألوان.

ثمة نتيجة أخرى، تُعرف أيضاً باسم نظرية رامزي ، تنطبق على الرسوم البيانية اللانهائية. وفي سياق مناقشة الرسوم البيانية المحدودة، تُسمى غالباً "نظرية رامزي اللانهائية". ولأنّ الحدس الذي توفره التمثيلات التصويرية للرسم البياني يتضاءل عند الانتقال من الرسوم البيانية المحدودة إلى اللانهائية، فإنّ النظريات في هذا المجال تُصاغ عادةً بمصطلحات نظرية المجموعات . ^{[ 47 ]}

نظرية. ليكن${\displaystyle X}$لتكن مجموعة لانهائية ، ولَوِّن عناصرها${\displaystyle [X]^{n}}$(المجموعات الفرعية من${\displaystyle X}$من الحجم${\displaystyle n}$) في${\displaystyle c}$ألوان مختلفة. إذن، توجد مجموعة جزئية لانهائية.${\displaystyle M}$ل${\displaystyle X}$بحيث يكون الحجم${\displaystyle n}$مجموعات فرعية من${\displaystyle M}$جميعها لها نفس اللون.

البرهان : يُبرهن على ذلك بالاستقراء على n ، وهو عدد المجموعات الجزئية. بالنسبة لـ n = 1 ، فإن العبارة تُكافئ القول بأنه إذا قُسِّمت مجموعة لانهائية إلى عدد محدود من المجموعات، فإن إحداها ستكون لانهائية. وهذا واضح. بافتراض صحة النظرية لـ n ≤ r ، نُثبتها لـ n = r + 1. لنفترض أن لدينا تلوينًا من الرتبة c للمجموعات الجزئية المكونة من ( r + 1) عنصرًا من X ، ولتكن a₀ عنصرًا من X ، ولتكن Y = X \ { a₀ }. نستنتج بعد ذلك تلوينًا من الرتبة c للمجموعات الجزئية المكونة _من r عنصرًا من Y ، وذلك بإضافة a₀ إلى كل مجموعة جزئية مكونة من r عنصرًا (للحصول على مجموعة جزئية _{مكونة من} ( r + 1) عنصرًا من X ). بحسب فرضية الاستقراء، _توجد مجموعة جزئية لانهائية Y₁ من Y بحيث تكون كل مجموعة جزئية مكونة من r _{عنصرًا من} Y₁ ملونة بنفس اللون في التلوين المُستنتج. وبالتالي _، يوجد عنصر a₀ ومجموعة جزئية لانهائية Y₁ بحيث تكون جميع _{المجموعات} الجزئية المكونة من (r + 1) عنصرًا من _{X، والتي تتألف من a₀} و r عنصرًا من _{Y₁، لها نفس اللون. وبنفس الحجة، يوجد عنصر a₁} في Y₁ ومجموعة جزئية لانهائية Y₂ _من Y₁ لها نفس الخصائص . بالاستقراء ، _نحصل على متتالية { a₀ _, a₁ _, a₂ , …} بحيث يعتمد لون كل _مجموعة جزئية مكونة _من ( r + 1) _{عنصرًا (} ai₁ , a₂ , _… , aₖ _{( r + 1)} ) ، حيث i₁ < _i₂ < … < iₖ ( r + 1)، على _قيمة i₁ فقط _.علاوة على ذلك، توجد قيم لا نهائية لـ i ( n ) بحيث يكون هذا اللون هو نفسه. خذ هذه القيم لـ _{i ( n )} للحصول على المجموعة أحادية اللون المطلوبة.

تنص نظرية إردوش-دوشنيك-ميلر ، وهي شكل أقوى ولكن غير متوازن من نظرية رامزي للرسوم البيانية، على أن كل رسم بياني لانهائي يحتوي إما على مجموعة مستقلة لانهائية قابلة للعد ، أو على زمرة لانهائية لها نفس عدد عناصر الرسم البياني الأصلي. ^{[ 48 ]}

يمكن تعميم هذه النظرية لتشمل المخططات الفائقة . المخطط الفائق من الرتبة m هو مخطط تكون "حوافه" عبارة عن مجموعات من m رأسًا - في المخطط العادي، الحافة عبارة عن مجموعة من 2 رأسًا. ينص نص نظرية رامزي الكاملة للمخططات الفائقة على أنه لأي عددين صحيحين m و c ، وأي عددين صحيحين n _{= 1} ، ...، n_{_c} ، يوجد عدد صحيح R ( n _₁ , ..., n_{_c} ; m) بحيث إذا لُوِّنت الحواف الفائقة لمخطط فائق كامل من الرتبة m من R ( n _₁ , ..., n_{_c} ; m ) بـ c لونًا مختلفًا، فإنه بالنسبة لبعض i بين 1 و c ، يجب أن يحتوي المخطط الفائق على مخطط فائق فرعي كامل من الرتبة m من _ni تكون جميع حوافه الفائقة باللون i . عادةً ما تُثبت هذه النظرية بالاستقراء على m ، وهو ما يُعرف بـ "خاصية الفائقية" للمخطط. الحالة الأساسية للإثبات هي m = 2 ، وهي بالضبط النظرية المذكورة أعلاه.

عندما m = 3، نعرف القيمة الدقيقة لأحد أعداد رامزي غير التافهة، وهي R (4, 4; 3) = 13. وقد أثبت هذه الحقيقة بريندان مكاي وستانيسواف رادزيسوفسكي عام 1991. ^{[ 50 ]} بالإضافة إلى ذلك، لدينا: R (4, 5; 3) ≥ 35 ، ^{[ 51 ]} وR (4, 6; 3) ≥ 63 و R (5, 5; 3) ≥ 88. ^{[ 51 ]}

من الممكن أيضًا تعريف أعداد رامزي للرسوم البيانية الموجهة ؛ وقد قدمها كل من ب. إردوش ول . موزر ( 1964 ) . ليكن R ( n ) أصغر عدد Q بحيث يحتوي أي رسم بياني كامل ذو أقواس موجهة أحادية (يسمى أيضًا "بطولة") و≥ Q عقدة على بطولة فرعية غير دورية (تسمى أيضًا "متعدية") مكونة من n عقدة. 

هذا هو نظير الرسم البياني الموجه لما سُمّي (أعلاه) R ( n , n ; 2) ، وهو أصغر عدد Z بحيث يحتوي أي تلوين ثنائي لحواف رسم بياني كامل غير موجه ذي ≥ Z عقدة، على رسم بياني كامل أحادي اللون ذي n عقدة. (النظير الموجه للونَي القوسين الممكنين هو اتجاهَي القوسين ، ونظير "أحادي اللون" هو "جميع أسهم القوس تشير إلى نفس الاتجاه"؛ أي "غير دوري").

لدينا 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. ^{[ 52 ] [ 53 ]}

من منظور حساب التقسيم، يمكن صياغة نظرية رامزي على النحو التالي:${\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}}$وقد عزز جاستن تي. مور هذه النتيجة أكثر. ومن الجانب الإيجابي، فإن كاردينال رامزي هو كاردينال كبير.${\displaystyle \kappa }$مُعرَّفة بشكل بديهي لتحقيق الصيغة ذات الصلة:${\displaystyle \kappa \rightarrow (\kappa )_{2}^{<\omega }}$لا يمكن إثبات وجود كاردينالات رامزي في ZFC.