مبرهنة رامزي

في التوافقيات, مبرهنة رمزي تنص على أنه بأي تلوين لأضلاع رسم بياني كامل كبير بما فيه الكفاية, يوجد رسم بياني فرعي كامل أحادي اللون. للونين, تنص مبرهنة رمزي على أنه لكل زوج من الأعداد الصحيحة الموجبة (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).

مثال: R(3,3) = 6

تلوين بلونين لـ K₅ (رسم بياني كامل على 5 رؤوس) بدون K₃ أحادي اللون

في المثال التالي, الصيغة (R(3,3 توفر حلا للسؤال الذي يسأل ما هو العدد الأدنى من الرؤوس على شكل بياني أن يحوي, لضمان إما:

(1) على الأقل 3 رؤوس في الشكل البياني متصلة أو

(2) على الأقل 3 رؤوس في الشكل البياني غير متصلة.

لاحظ أنه نظرا لطبيعة المسألة المتناظرة, (R(r,s تؤدي إلى نفس جواب (R(s,r. لا يظهر هذا جليا في مثال (R(3,3, لان قيم r و s متساوية.

لنفترض أن أضلاع الشكل البياني الكامل على 6 رؤوس ملونة بالأزرق والأحمر. نختار رأس v. يوجد 5 أضلاع خارجة من v (لأنه هناك 5 رؤوس غير v, حيث يتصلون مع v كل رأس بضلع) ولذلك حسب مبدأ برج الحمام على الأقل 3 من الأضلاع هم من لون واحد. بدون فقدان العمومية نفترض أن 3 أضلاع منهم, المتصلة مع الرؤوس r, s و t هي ملونة بالأزرق (إذا لم تكن كذلك, نبدل الأحمر بالأزرق.) يوجد حالتين:

• إذا كانت أحد الأضلاع التالية (r, s), (r, t), (s, t) ملونة بالأزرق, وبالتالي يوجد مثلث أزرق (شكل بياني كامل على 3 رؤوس).
• إن لم يكن ذلك, إذن جميع الأضلاع (r, s), (r, t), (s, t) ملونة بالأحمر, وبالتالي يوجد مثلث أحمر.

لأن هذا البرهان يعمل على أي تلوين, أي K6 (رسم بياني كامل على 6 رؤوس) يحتوي على K3 أحادي اللون, وبالتالي R(3,3) ≤ 6. وعلى العكس, يتضح من الصورة أنه بالإمكان رسم K5 بدون أن يحتوي على K3 أزرق أو K3 أحمر. ولذلك R(3,3) > 5. إذن R(3,3) = 6.