نظریه رمزی
نظریه رمزی بررسی میکند که چگونه بینظمی کامل غیرممکن است: هر ساختار به اندازه کافی بزرگی باید شامل یک زیرساختار بسیار سازمانیافته باشد.
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) با وجود تلاشهای فراوان ناشناخته باقی ماندهاند.