نظرية رامزي وأعداد رامزي

تضمن نظرية رامزي أن أي رسم بياني كامل كبير بما فيه الكفاية ومُلوَّن بلونين يحتوي على زمرة أحادية اللون (monochromatic clique)، وتحدد أعداد رامزي مدى الكبر الكافي.

Definition

عدد رامزي R(s,t) هو أصغر عدد صحيح n بحيث أن كل تلوين أحمر-أزرق لحواف الرسم البياني الكامل على n رأس يحتوي على زمرة حمراء على s رأس أو زمرة زرقاء على t رأس.

Scope

يغطي هذا الموضوع الشكل البياني لنظرية رامزي، وتعريف أعداد رامزي R(s,t)، والحالات الصغيرة الكلاسيكية مثل R(3,3)=6، والحد الأعلى لإردوش-سيكيريس (Erdos-Szekeres) والحد الأدنى الاحتمالي لإردوش، والتوسع ليشمل أعداد رامزي متعددة الألوان والرسم البياني الفائق (hypergraph). إنه القلب الكمي لنظرية رامزي.

Core questions

• ما هو الحجم الذي يجب أن يكون عليه الرسم البياني الكامل لفرض زمرة أحادية اللون بحجم معين؟
• ما هي القيم الدقيقة والحدود المعروفة لأعداد رامزي؟
• كيف تعطي الحجج الاحتمالية حدودًا دنيا لأعداد رامزي؟
• كيف تعمم النظرية لتشمل عدة ألوان والرسم البياني الفائق؟

Key concepts

• نظرية رامزي للرسوم البيانية
• عدد رامزي R(s,t)
• الزمر أحادية اللون
• حد إردوش-سيكيريس
• الحدود الدنيا الاحتمالية
• أعداد رامزي متعددة الألوان والرسم البياني الفائق

Key theories

الحد الأعلى لإردوش-سيكيريس

أعداد رامزي محدودة ومقيدة بأن R(s,t) لا تتجاوز المعامل الثنائي لـ s+t-2 اختر s-1، وهو حد يعتمد على التكرار ويثبت نظرية رامزي بتقديرات صريحة.

الحد الأدنى الاحتمالي لإردوش

من خلال حساب الزمر أحادية اللون المتوقعة في تلوين عشوائي، أظهر إردوش في عام 1947 أن عدد رامزي القطري R(s,s) ينمو بشكل أسي على الأقل، وهو تطبيق تأسيسي للطريقة الاحتمالية.

Clinical relevance

أصبحت الطريقة الاحتمالية التي قُدِّمت من خلال الحدود الدنيا لأعداد رامزي أداة مركزية في علم التوافقيات وعلوم الحاسوب النظرية، وتدعم ضمانات من نوع رامزي الحدود الدنيا في الاتصالات وهياكل البيانات.

History

أعاد إردوش وسيكيريس اكتشاف نظرية رامزي وكمّياها في عام 1935 أثناء دراستهما للمضلعات المحدبة؛ وأطلقت حدود إردوش الدنيا للتلوين العشوائي عام 1947 الطريقة الاحتمالية.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

لماذا R(3,3) يساوي ستة؟

من بين أي ستة أشخاص، هناك ثلاثة يعرفون بعضهم البعض أو ثلاثة غرباء عن بعضهم البعض، بينما يمكن ترتيب خمسة أشخاص لتجنب كليهما، لذا فإن ستة هو الحد الدقيق.

هل أعداد رامزي الدقيقة معروفة؟

عدد قليل فقط معروف بدقة؛ حتى R(5,5) لا يزال غير محدد، والمعرفة الحالية تضيقه فقط إلى نطاق، لأن مساحة البحث تنمو بسرعة كبيرة بحيث لا يمكن حسمها بالحساب.