نظرية رمزي

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

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

أمثلة[عدل]

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

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

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

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

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

مراجع[عدل]

  • Landman، B. M. & Robertson، A. (2004)، Ramsey Theory on the Integers، Student Mathematical Library 24، Providence, RI: AMS، ISBN 0821831992 .
  • Ramsey، F. P. (1930)، "On a Problem of Formal Logic"، Proceedings London Mathematical Society، s2-30 (1): 264–286، doi:10.1112/plms/s2-30.1.264 .
  • Erdös، P. & Szekeres، G. (1935)، "A combinatorial problem in geometry"، Compositio Math. 2: 463–470 .
  • Boolos، G.؛ Burgess، J. P.؛ Jeffrey، R. (2007)، Computability and Logic (الطبعة 5th)، Cambridge: Cambridge University Press، ISBN 9780521877527 .