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