הצגת המקור של הדף "תורת רמזי"

'''תורת רמזי''' היא תחום ב[[קומבינטוריקה]] העוסק בשאלה כמה גדול צריך להיות [[מבנה מתמטי]] כדי להבטיח שתת-מבנה שלו מקיים תכונה מסוימת. הרעיון המרכזי הוא להראות ששום דבר גדול לא יכול להיות "[[אקראיות|אקראי]] מדי", ובכל מערכת כאוטית גדולה יש איים של סדר.

התורה פותחה בעיקר ב[[המאה ה-20|מאה ה-20]]. היא נקראת על שמו של [[פרנק רמזי]] שהוכיח את [[משפט רמזי]], אחד המשפטים הראשונים במסגרת התורה. רמזי עצמו הוכיח את המשפט רק כ[[למה (מתמטיקה)|למה]] בדרך להוכחת תוצאה ב[[לוגיקה מתמטית]].

תוצאה טיפוסית בתורת רמזי תראה כי תכונה מסוימת חייבת להתקיים בתת-מבנה (למשל [[תת-גרף]], [[מקצוע (גאומטריה)|מקצוע]] של [[היפרקובייה]], קבוצה של [[מספר טבעי|מספרים טבעיים]] וכו') שהוא [[גדול מספיק]]. על פי רוב זו תהיה [[הוכחה לא קונסטרוקטיבית]], ולא תבהיר כיצד למצוא תת-מבנה שכזה. בנוסף המבנים המעורבים נוטים להיות גדולים מאוד, והתורה מספקת את הדוגמאות הגדולות ביותר ל[[מספרים גדולים]] שיש להם שימוש (למשל [[מספר גרהאם]]).

==תוצאות בסיסיות==
* [[משפט רמזי]] - לכל מספר טבעי n קיים [[גרף שלם]], כך שלא משנה כיצד נצבע את קשתותיו בשני צבעים שונים, תמיד יהיה לו תת-גרף שלם בגודל n שכל צלעותיו צבועות באותו הצבע (את המשפט ניתן להכליל לכל מספר טבעי של צבעים שונים).
* [[משפט ואן דר וארדן]]  (לפי [[בארטל לנדרט ואן דר וארדן]], 1927) - לכל c ו-n קיים מספר N כך שאם N מספרים עוקבים נצבעים ב-c צבעים שונים, אז קיימת [[סדרה חשבונית]] באורך n שכל איבריה באותו הצבע.
* [[משפט ארדש-סקרש]]: לכל <math>a,b</math> טבעיים, בכל סדרה באורך <math>\ ab + 1</math> של מספרים ממשיים שונים יש תת־סדרה עולה באורך <math> \ a+1</math> או תת־סדרה יורדת באורך <math> \ b+1</math>.

==ראו גם==
* [[קומבינטוריקה קיצונית]]
* [[בארטל לנדרט ואן דר וארדן]]

==קישורים חיצוניים==
* {{MathWorld}}

[[קטגוריה:תורת רמזי|*]]
[[קטגוריה:קומבינטוריקה קיצונית]]