نظرية رامزي

هذه المقالة هي عبارة عن مقدمة. لمقالة أكثر تفصيلا واختصاصا، راجع مبرهنة رامزي.

نظرية رامزي، سميت نسبة للرياضياتي والفيلسوف البريطاني فرانك رامزي، هي فرع من الرياضيات التي تدرس الظروف التي بموجبها يجب أن يظهر نظام. مسائل في نظرية رامزي عادة تطرح سؤالاً من الشكل: "كم عدد العناصر من بنية ما يجب أن تكون لتضمن لزوم خاصية معينة؟"

أمثلة

تلوين رسم بياني كامل من 5 رؤوس بدون رسم بياني كامل جزئي من 3 رؤوس أحمر أو أزرق

نتيجة نموذجية من نظرية رامزي تبدأ مع بنية رياضية ما، التي من ثم تقسم إلى قطع. ما هو كبر البنية الأصلية من أجل ضمان أن لقطعة واحدة على الأقل خاصية مثيرة للاهتمام؟

على سبيل المثال، تأمل في رسم بياني كامل من ترتيب n; أي أنه، هنالك n رؤوس وكل رأس متصل مع كل الرؤوس الأخرى بضلع. رسم بياني كامل من ترتيب 3 يسمى مثلث. الآن قم بتلوين كل ضلع بالأحمر أو الأزرق. كم يجب أن يكون كبر n لضمان أنه هنالك إما مثلث أزرق أو مثلث أحمر؟ اتضح أن الجواب هو 6. بالصورة على اليمين يظهر أن العدد 5 غير كاف. راجع المقالة حول مبرهنة رامزي للبرهان الدقيق.

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

هي أيضا حالة خاصة من مبرهنة رامزي، والتي تنص على أنه لأي عدد صحيح c معطى، وأعداد صحيحة n₁,...,n_c معطاه. هنالك عدد، (R(n₁,...,n_c، بحيث لو تم تلوين أضلاع الرسم البياني من ترتيب (R(n₁,...,n_c بـ c ألوان مختلفة، إذن هنالك عدد i بين 1 وc، بحيث أن الرسم البياني يجب أن يحتوي على رسم بياني كامل جزئي من ترتيب n_i والتي أضلاعه ملونة باللون i. بالحالة الخاصة c == 2 وn₁ = n₂ == 3.