نظرية رامزي
تدرس نظرية رامزي كيف يستحيل وجود الفوضى الكاملة: يجب أن يحتوي أي هيكل كبير بما فيه الكفاية على بنية فرعية عالية التنظيم.
Definition
فرع من فروع التوافقيات يسأل عن مدى كبر الهيكل لضمان أن أي تقسيم أو تلوين له ينتج عنه بنية فرعية أحادية اللون أو محددة بطريقة أخرى.
Scope
يغطي هذا المجال مبرهنة رامزي للرسوم البيانية والرسوم البيانية الفائقة وأعداد رامزي الكمية الخاصة بها، ونتائج التقسيم للأعداد الصحيحة مثل مبرهنات شور وفان دير فاردن وهيلز-جويت، ونظرية رامزي الهيكلية المجردة لمجموعات المعلمات. وهي تجسد المبدأ التوافقي المتطرف الذي ينص على أن الأنظمة الكبيرة بما فيه الكفاية لا يمكنها تجنب النظام.
Sub-topics
Core questions
- ما مدى كبر الهيكل الذي يجب أن يكون عليه لفرض بنية فرعية مرتبة لا يمكن تجنبها؟
- ما هي العتبات الدقيقة أو التقريبية، أي أعداد رامزي، لهذه الضمانات؟
- كيف تضمن مبرهنات التقسيم للأعداد الصحيحة أنماطًا حسابية؟
- ما هي العائلات المجردة من الهياكل التي تحقق خاصية رامزي؟
Key concepts
- مبرهنة رامزي
- أعداد رامزي
- البنى الفرعية أحادية اللون
- مبرهنة فان دير فاردن
- مبرهنة شور
- مبرهنة هيلز-جويت
Clinical relevance
تُفيد ضمانات رامزي للبنية التي لا يمكن تجنبها في حجج الحد الأدنى في علوم الحاسوب النظرية، وتحليل الشبكات الكبيرة، ونظرية الأعداد التجميعية، بينما تدفع الفجوة بين الحدود المعروفة المنهج الاحتمالي.
History
تم الاعتراف بمبرهنة فرانك رامزي لعام 1930 حول التقسيمات، والتي أُثبتت في الأصل لسؤال في المنطق، من قبل إردوس وسزيكيريس كبذرة لنظرية واسعة النطاق للبنية التي لا يمكن تجنبها والتي نمت خلال القرن العشرين.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- ما هو شعار نظرية رامزي؟
- الفوضى الكاملة مستحيلة: أي نظام كبير بما فيه الكفاية، مهما كان ترتيبه، يجب أن يحتوي على جزء منظم كبير.
- لماذا يصعب حساب أعداد رامزي؟
- يزداد عدد التلوينات التي يجب التحقق منها بشكل فلكي، وحتى أعداد رامزي الصغيرة مثل R(5,5) لا تزال مجهولة على الرغم من الجهود المكثفة.