نظرية رامزي

نظرية رامزي ، نسبةً إلى عالم الرياضيات والفيلسوف البريطاني فرانك ب. رامزي ، هي فرع من فروع الرياضيات يُعرف باسم التوافقية ، ويركز على ظهور النظام في بنية فرعية معينة، مع الأخذ في الاعتبار بنية ذات حجم معروف. وتطرح مسائل نظرية رامزي عادةً سؤالاً على النحو التالي: "ما هو حجم البنية اللازمة لضمان تحقق خاصية معينة؟" ^{[ 1 ]}

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

على سبيل المثال، لنفترض وجود رسم بياني كامل من الرتبة n ؛ أي أن له n رأسًا، وكل رأس متصل بكل رأس آخر بواسطة ضلع. يُسمى الرسم البياني الكامل من الرتبة 3 مثلثًا. الآن، لوّن كل ضلع إما بالأحمر أو الأزرق. ما هو الحد الأدنى لقيمة n لضمان وجود مثلث أزرق أو مثلث أحمر؟ اتضح أن الإجابة هي 6. راجع مقالة نظرية رامزي للاطلاع على برهان دقيق .

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

هذه أيضًا حالة خاصة من نظرية رامزي، التي تنص على أنه لأي عدد صحيح معطى _c ، وأي أعداد صحيحة معطاة _n₁ , ..., nₙc _، يوجد عدد R ( n₁ , ..., nₙc ) بحيث إذا لُوِّنت حواف رسم بياني كامل من الرتبة R ( _{n₁ ,} ..., nₙc ) بـ c لونًا مختلفًا، فإنه بالنسبة لبعض i بين 1 و _c ، يجب أن يحتوي على رسم بياني فرعي كامل من الرتبة nᵢ تكون حوافه جميعها باللون i . في الحالة الخاصة المذكورة أعلاه _، c = 2 و n₁ = _{n₂ = 3} .

من أهم نظريات رامزي ما يلي:

• نظرية فان دير فاردن : لأي عددين معطيين c و n ، يوجد عدد V ، بحيث إذا تم تلوين V أعداد متتالية بـ c ألوان مختلفة، فإنه يجب أن يحتوي على متتابعة حسابية طولها n عناصرها كلها من نفس اللون.
• تنص نظرية هيلز-جويت على أنه لأي عددين معطيين n و c ، يوجد عدد H بحيث إذا لُوِّنت خلايا مكعب ذي أبعاد H (n × n × n × ... × n ) بـ c لونًا، فلا بد من وجود صف أو عمود واحد، وهكذا، بطول n، تكون جميع خلاياه من نفس اللون. أي أن لعبة إكس-أو متعددة اللاعبين (n -in-a-row) لا يمكن أن تنتهي بالتعادل، مهما كان حجم n ، ومهما كان عدد اللاعبين، إذا كانت اللوحة ذات أبعاد كافية. وتستلزم نظرية هيلز-جويت نظرية فان دير فاردن.

تُشابه نظرية شور نظرية فان دير فاردن ، حيث تنص على أنه لأي عدد c مُعطى، يوجد عدد N بحيث إذا لُوِّنت الأعداد من 1 إلى N بـ c لونًا مختلفًا، فلا بد من وجود زوج من الأعداد الصحيحة x و y بحيث يكون x و y و x + y جميعها بنفس اللون. توجد العديد من التعميمات لهذه النظرية، بما في ذلك نظرية رادو ، ونظرية رادو-فولكمان-ساندرز ، ونظرية هندمان ، ونظرية ميليكن-تايلور . يُعد كتاب غراهام، روتشيلد، سبنسر، وسوليموسي مرجعًا كلاسيكيًا لهذه النتائج وغيرها الكثير في نظرية رامزي، وقد تم تحديثه وتوسيعه في عام 2015 ليصدر في أول طبعة جديدة له منذ 25 عامًا. ^{[ 2 ]}

تتسم نتائج نظرية رامزي عادةً بسمتين أساسيتين. أولاً، هي نتائج غير بنائية : فقد تُظهر وجود بنية ما، لكنها لا تُقدم أي آلية لإيجاد هذه البنية (باستثناء البحث الشامل ). على سبيل المثال، مبدأ خانة الحمام هو من هذا النوع. ثانياً، بينما تُشير نتائج نظرية رامزي إلى أن الكائنات الكبيرة بما يكفي يجب أن تحتوي بالضرورة على بنية معينة، فإن إثبات هذه النتائج غالباً ما يتطلب أن تكون هذه الكائنات ضخمة للغاية - فالحدود التي تنمو أُسّياً ، أو حتى بسرعة دالة أكرمان، ليست نادرة. في بعض الحالات النادرة، تتحسن الحدود العليا والسفلى، ولكن ليس بشكل عام. في كثير من الحالات، تكون هذه الحدود ناتجة عن عملية الإثبات، وليس من المعروف ما إذا كان من الممكن تحسينها بشكل كبير. في حالات أخرى، من المعروف أن أي حد يجب أن يكون ضخماً للغاية، وأحياناً أكبر من أي دالة تكرارية أولية ؛ انظر إلى نظرية باريس-هارينغتون كمثال. يُعدّ عدد غراهام ، أحد أكبر الأعداد التي استُخدمت في البراهين الرياضية الجادة، حدًا أعلى لمسألةٍ تتعلق بنظرية رامزي. ومن الأمثلة الكبيرة الأخرى مسألة الثلاثيات الفيثاغورية البوليانية . ^{[ 3 ]}

تُصنّف النظريات في نظرية رامزي عمومًا إلى نوعين رئيسيين. تنصّ العديد من هذه النظريات، المستوحاة من نظرية رامزي نفسها، على أنه في كل تجزئة لكائن مُهيكل كبير، تحتوي إحدى الفئات بالضرورة على كائن مُهيكل خاص بها، دون تحديد هذه الفئة. في حالات أخرى، يكمن سبب ظهور نتيجة من نوع رامزي في أن أكبر فئة تجزئة تحتوي دائمًا على البنية الفرعية المطلوبة. تُسمى نتائج هذا النوع الأخير إما بنتائج الكثافة أو نتائج توران ، نسبةً إلى نظرية توران . ومن الأمثلة البارزة على ذلك نظرية سزيميريدي ، التي تُعدّ تعزيزًا لنظرية فان دير فاردن، ونسخة الكثافة من نظرية هيلز-جويت. ^{[ 4 ]}

• نظرية رامزي الإرجودية
• نظرية الرسم البياني المتطرفة
• نظرية غودستين
• بارتل ليندرت فان دير وايردن
• نظرية التناقض
• تخمين عباد الشمس

• لاندمان، بي إم وروبرتسون، أ. (2004)، نظرية رامزي على الأعداد الصحيحة ، مكتبة الطلاب الرياضية، المجلد  24، بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات، ISBN 0-8218-3199-2.
• رامزي، إف بي (1930)، "حول مشكلة في المنطق الصوري"، وقائع الجمعية الرياضية في لندن ، s2-30 (1): 264– 286، doi : 10.1112/plms/s2-30.1.264(خلف جدار دفع).
• إردوس, بول ; Szekeres، George (2008) [1935]، “مشكلة اندماجية في الهندسة” , Compositio Mathematica ، المجلد.  2، الصفحات من 463 إلى 470، دوى : 10.1007/978-0-8176-4842-8_3 ، ISBN  978-0-8176-4841-1، Zbl 0012.27010 .
• بولوس، جي.؛ بورغيس، جيه بي؛ جيفري، آر. (2007)، الحوسبة والمنطق (الطبعة الخامسة  )، كامبريدج: مطبعة جامعة كامبريدج، ISBN 978-0-521-87752-7.
• ماثيو كاتز ويان رايمان، مقدمة في نظرية رامزي: الدوال السريعة، واللانهاية، وما وراء الرياضيات، مكتبة الطلاب الرياضية، المجلد 87، 2018، 207 صفحة، رقم ISBN 978-1-4704-4290-3