مبرهنة رامزي

في التوافقيات، تنص مبرهنة رامزي على أنه بأي تلوين لأضلاع رسم بياني كامل كبير بما فيه الكفاية ، يوجد رسم بياني فرعي كامل أحادي اللون.2.6 Ramsey Theory from Mathematics Illuminated  للونين ، تنص مبرهنة رامزي على أنه لكل زوج من الأعداد الصحيحة الموجبة (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 
إطار|تلوين K5 (رسم بياني كامل على 5 رؤوس) بلونين بدون K3 أحادي اللون

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

لنفترض أن أضلاع الشكل البياني الكامل على 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.

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

 إثبات المبرهنة 
نقوم بإثبات حالة اللونين ، بالاستقراء على r + s.
من الواضح من التعريف بأنة لكل n ، R(n ، 1) == R(1 ، n) == 1. هذا يشكل أساس الاستقراء.
نثبت بأن (R(r ، s موجود عن طريق إيجاد حد واضح له. بفرضية الاستقراء (R(r − 1 ، s و(R(r ، s − 1 موجودان.

إدعاء: :(R(r ، s) ≤ R(r − 1 ، s) + R(r ، s − 1
أنظر إلى رسم بياني كامل بـ (R(r − 1 ، s) + R(r ، s − 1 رؤوس. اختر رأس من الرسم ، وقسم باقي الرؤوس إلى مجموعتين M وN ، بحيث لكل رأس w ، w في M إذا كان الضلع (v ، w) أزرق ، وw في N إذا كان الضلع (v ، w) أحمر.

ولأن في الرسم R(r - 1 ، s) + R(r ، s - 1) = |M| + |N| + 1 أضلاع ، إذن إما (M| ≥ R(r − 1 ، s| أو (N| ≥ R(r ، s − 1|.

في الحالة الأولى إذا في M رسم بياني Ks أحمر ، أيضا هو يوجد في الرسم الأصلي وانتهينا. وإلا في M رسم بياني Kr−1 أزرق. إذن يوجد  أزرق حسب تعريف M.
الحالة الثانية متطابقة.

إذن الادعاء صحيح ، ونكون أثبتنا للونين. إثبات الحالة العامة لـ c ألوان يكون الإثبات بالاستقراء مجددا على عدد الألوان c.

 أعداد رامزي 
الأعداد (R(r ،s في مبرهنة رامزي (والإضافات لأكثر من لونين) تعرف بأعداد رامزي. حتى هذه اللحظة قيم(R(n ،n لكل n ≥ 5 غير معروفة.

تظهر بالجدول أدناه أعداد رامزي لكل r ،s بين 1 و 10:

 r ،s 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 9 14 18 23 28 36 40–43 4 1 4 9 18 25 35–41 49–61 56–84 73–115 92–149 5 1 5 14 25 43–49 58–87 80–143 101–216 126–316 144–442 6 1 6 18 35–41 58–87 102–165 113–298 132–495 169–780 179–1171 7 1 7 23 49–61 80–143 113–298 205–540 217–1031 241–1713 289–2826 8 1 8 28 56–84 101–216 132–495 217–1031 282–1870 317–3583 331-6090 9 1 9 36 73–115 126–316 169–780 241–1713 317–3583 565–6588 581–12677 10 1 10 40–43 92–149 144–442 179–1171 289–2826 331-6090 581–12677 798–23556

 انظر أيضاً 
 نظرية رامزي
 رسم بياني كامل

 مراجع 

 وصلات خارجية 
 إثبات أن R(3 ،6) = 18

تصنيف:نظرية رامزي
تصنيف:رياضيات متقطعة
تصنيف:مبرهنات في نظرية البيان
تصنيف:مقالات تحوي براهين