תורת רמזי
תורת רמזי היא תחום בקומבינטוריקה העוסק בשאלה כמה גדול צריך להיות מבנה מתמטי כדי להבטיח שתת-מבנה שלו מקיים תכונה מסוימת. הרעיון המרכזי הוא להראות ששום דבר גדול לא יכול להיות "אקראי מידי", ובכל מערכת כאוטית גדולה יש איים של סדר.
התורה פותחה בעיקר במאה ה-20. היא נקראת על שמו של פרנק רמזי שהוכיח את משפט רמזי, אחד המשפטים הראשונים במסגרת התורה. רמזי עצמו הוכיח את המשפט רק כלמה בדרך להוכחת תוצאה בלוגיקה מתמטית.
תוצאה טיפוסית בתורת רמזי תראה כי תכונה מסוימת חייבת להתקיים בתת-מבנה (למשל תת-גרף, מקצוע של היפרקובייה, קבוצה של מספרים טבעיים וכו') שהוא גדול מספיק. על פי רוב ההוכחה תהיה לא קונסטרקטיבית, ולא תבהיר כיצד למצוא תת-מבנה שכזה. בנוסף המבנים המעורבים נוטים להיות גדולים מאוד, והתורה מספקת את הדוגמאות הגדולות ביותר למספרים גדולים שיש להם שימוש (למשל מספר גרהאם).
תוצאות בסיסיות
- משפט רמזי - לכל מספר טבעי n קיים גרף שלם, כך שלא משנה כיצד נצבע את קשתותיו בשני צבעים שונים, תמיד יהיה לו תת-גרף שלם בגודל n שכל צלעותיו צבועות באותו הצבע (את המשפט ניתן להכליל לכל מספר של צבעים שונים).
- משפט ואן דר וארדן - לכל c ו-n קיים מספר N כך שאם N מספרים עוקבים נצבעים ב-c צבעים שונים, קיימת סדרה חשבונית באורך n שכל איבריה באותו הצבע.
- משפט ארדש-סקרש: לכל סדרה בת יותר מ-ab מספרים יש תת-סדרה עולה באורך יותר מ-a או תת-סדרה יורדת באורך יותר מ-b.