مبرهنة رامزي
من ويكيبيديا، الموسوعة encyclopedia
في التوافقيات، تنص مبرهنة رامزي على أنه بأي تلوين لأضلاع رسم بياني كامل كبير بما فيه الكفاية ، يوجد رسم بياني فرعي كامل أحادي اللون.[1][2][3] للونين ، تنص مبرهنة رامزي على أنه لكل زوج من الأعداد الصحيحة الموجبة (r ،s) ، يوجد على الأقل عدد صحيح موجب (R(r ،s ، حيث أنه لأي رسم بياني كامل على (R(r ،s رؤوس ، ملونة أضلاعة بالأحمر أو الأزرق ، إما يوجد رسم بياني فرعي كامل على r رؤوس أضلاعة ملونة بالأزرق، أو رسم بياني فرعي كامل على s رؤوس أضلاعه ملونة بالأحمر. هنا (R(r ،s تعبر عن عدد صحيح الذي يعتمد على كل من r و s. ومن المفهوم تمثيل أصغر عدد صحيح الذي تنطبق عليه المبرهنة.
مبرهنة رامزي هي نتيجة تأساسية في التوافقيات. النسخة الأولى من هذه المبرهنة أثبتت على يد الرياضي الانجيزي فرانك رامزي. بدأت هذه المبرهنة نظرية التوافقيات ، التي يطلق عليها حاليا نظرية رامزي، التي تبحث الانتظام وسط الفوضى: شروط عامة لوجود مبنى فرعي مع خصائص منتظمة. في هذه الحالة هي مسألة وجود مجموعة فرعية أحادية اللون، والتي هي مجموعة فرعية من أضلاع متصلة ملونة بلون واحد فقط.
إضافة لهذه المبرهنة ينطبق على عدد محدود من الألوان ، بدلا من لونين. بصورة أدق، تنص المبرهنة على أنه لكل عدد معطى من الألوان c، ولكل أعداد صحيحة معطاه n1 ،... ،nc ، يوجد عدد ، (R(n1 ،... ، nc ، حيث أنه إذا تم تلوين أضلاع رسم بياني كامل على (R(n1 ،... ، nc رؤوس بـ c ألوان مختلفة ، يوجد i بين 1 و c ، حيث يجب أن يشمل الرسم البياني الكامل على ni رؤوس الذي ملونة جميع أضلاعه بالون i. (بالحالة الخاصة أعلاه c == 2 و n1 = r و n2 == s).[4]