משפט רמזי

בקומבינטוריקה, **משפט רמזי** (באנגלית: **Ramsey's theorem**) עוסק במבנים המוכרחים להופיע בגרף שלם שהקשתות שלו צבועות בשני צבעים, נאמר אדום וכחול. המשפט קובע שלכל n, אם הגרף שצובעים גדול מספיק, לא ניתן להימנע מיצירת תת-גרף שלם בגודל n שכל הקשתות שלו צבועות בצבע אחיד. את המשפט הוכיח פרנק רמזי, ובעקבותיו פותח תחום שלם בשם תורת רמזי.

## משפט רמזי האינסופי
**משפט**. לכל צביעה של הגרף האינסופי השלם \ G בשני צבעים, קיים תת-גרף אינסופי שלם \ G' \subseteq G אשר כל קשתותיו צבועות באותו הצבע.

ניתן להכליל את המשפט לכל מספר סופי של צבעים.

### הוכחה
ההוכחה תתבצע על ידי בניית סדרה של קודקודים. נסמן את שני הצבעים באדום וכחול. 

נתחיל בקודקוד שרירותי \ v_0. בהכרח קיימים לו אינסוף שכנים המחוברים בקשת אדומה, או אינסוף שכנים המחוברים בקשת כחולה. נוכל להניח שקבוצת השכנים האדומים, שאותה נסמן ב-\ V_0, היא אינסופית. כך אפשר להניח, באינדוקציה, שבחרנו קודקוד \ v_i וקבוצה אינסופית \ V_i, שכל קודקודיה מחוברים בקשת אדומה לכל אחד מן הקודקודים \ v_0,\dots,v_{i}. כעת יש שתי אפשרויות: אם קיים \ v_{i+1}\in V_i לו אינסוף שכנים אדומים ב-\ V_i, נבחר אותו ונסמן ב-\ V_{i+1} \subseteq V_i את קבוצת הקודקודים המחוברים ל-\ v_{i+1} בקשת אדומה. אם התהליך ממשיך, נקבל באינסופו של דבר סדרה של קודקודים, אשר כל אחד מהם קשור לכל האחרים באמצעות קשת אדומה, היינו תת-גרף אשר כל הקשתות שלו אדומות. אחרת, התהליך נעצר בקבוצה אינסופית \ V_k, אשר לכל אחד מן הקודקודים שלה יש מספר אינסופי של שכנים כחולים ורק מספר סופי של שכנים אדומים. לכן, אם נחזור על התהליך עבור הקשתות הכחולות בקבוצה \ V_k, התהליך לא יעצר ונקבל קבוצה אין סופית של קודקודים שכל שניים ממנה מחוברים בקשת כחולה.

ניתן להכליל את הטענה גם עבור \ k>2 צבעים, באמצעות טיעון אינדוקטיבי, על ידי התבוננות בקשתות בעלות צבע מסוים, וקשתות ב- \ k-1 הצבעים הנותרים.

### הכללות

**[[משפט ארדש-רדו]]**: יהי \ \kappa מונה אינסופי. בכל צביעה ב-\ \kappa צבעים (או פחות מזה) של הגרף השלם שעוצמת קבוצת הקודקודים שלו גדולה מ-\ 2^{\kappa}, יש תת-גרף מונוכרומטי שעוצמתו גדולה מ-\ \kappa. למשל, בכל צביעה של הגרף השלם שעוצמת קבוצת הקודקודים שלו גדולה מ-\ 2^{\aleph_0}, יש תת-גרף מונוכרומטי שאינו בן מניה.

## משפט רמזי הסופי
**מספר רמזי** \ R_{n,m} הוא הגודל הקטן ביותר של גרף שלם שקשתותיו צבועות בשני צבעים, נאמר אדום וכחול, המבטיח שהגרף יכיל תת-גרף שלם בן n קודקודים שכולו אדום, או תת-גרף שלם בן m קודקודים שכולו כחול. העובדה שמספרים אלה קיימים היא משפט רמזי. ההוכחה, באינדוקציה, מראה שלמעשה \ R_{n,m} \leq R_{n-1,m}+R_{n,m-1}, ומכיוון ש- \ R_{2,n} = R_{n,2} = n, מתקיים \ R_{n,m} \leq\binom{n+m-2}{n-1} . הערכים המדויקים של מספרי רמזי \ R_{n,n} אינם ידועים עבור \ n\geq 5. ידועים החסמים \ (n+1) \cdot 2^{(n+1)/2} \leq R_{n+1,n+1} \leq \binom{2n}{n} \approx \frac{1}{\sqrt{\pi n}} 4^n. ב-2020 הצליח Ashwin Sah, בעזרת שיטות של קוואזי-אקראיות, להכפיל את החסם העליון בגורם של \ e^{-c (\log n)^2} כאשר c קבוע https://arxiv.org/pdf/2005.09251.pdf. ב-2023 הושג, לראשונה מאז 1935, שיפור אקספוננציאלי של החסם העליון: \ R_{n,n}  https://arxiv.org/abs/2303.09521.

את ההגדרה לעיל אפשר להרחיב למספר סופי כלשהו של צבעים, ולגרפים כלשהם במקום תת-הגרפים השלמים.

ניסוח מהופך של המשפט קובע שבכל צביעה בשני צבעים של הגרף השלם על n קודקודים, יש תת-גרף חד-צבעי בן d קודקודים, כאשר \ d= 2\log_2(\frac{e^2}{8}\frac{n}{\log_2(n)})+o(1) \approx 2\log_2(n); תוצאה זו היא הטובה ביותר האפשרית.

### הוכחת המשפט
ההוכחה תעשה באינדוקציה על \ m,n

ברור ש-\ R_{1,m}=R_{n,1}=1 לכל n,m, משום שקודקוד בודד הוא גרף שלם בגודל 1 (וכל אפס הקשתות שלו אדומות וגם כחולות). 

עבור \ n,m>1 נראה כי \ R_{n,m}\leq R_{n-1,m}+R_{n,m-1}. 

נניח נתון גרף מלא \ G בגודל \ R_{n-1,m}+R_{n,m-1} שקשתותיו צבועות בכחול ואדום. נבחר ממנו צומת v ונסמן ב B את כל הצמתים שיש מהם קשת כחולה ל v ונסמן ב A את כל הצמתים שיש מהם קשת אדומה ל v.
על ידי סימון זה מקבלים ש \ R_{n-1,m}+R_{n,m-1}=1+|A|+|B|. לא ייתכן שגם \ R_{n-1,m}>|A| וגם \ R_{n,m-1}>|B| - נניח תחילה ש R_{n-1,m}\leq|A|.

אם בגרף הנפרש על ידי צומתי \ A יש קליקה בגודל \ n-1 שכל הקשתות בה צבועות בצבע אדום, אז יחד עם הצומת \ v מקבלים קליקה בגרף \ G בגודל \ n שכל קשתותיה אדומות. אחרת, מהנחת האינדוקציה מקבלים שבגרף הנפרש על ידי צומתי \ A ישנה קליקה בגודל \ m שכל קשתותיה כחולות.

בצורה דומה, אם \ R_{n,m-1}\leq|B| אז או שבגרף הנפרש על ידי \ B יש קליקה בגודל \ n שכל קשתותיה צבועות באדום, או שיש קליקה בגודל \ m-1 שכל קשתותיה צבועות בצבע כחול, ואז יחד עם \ v מקבלים קליקה ב \ G בגודל \ m שכל קשתותיה צבועות בצבע כחול.

סה"כ מקבלים שב \ G ישנה קליקה אדומה בגודל \ n או קליקה כחולה בגודל \ m.

## ראו גם
* משפט טורן

## לקריאה נוספת

## קישורים חיצוניים

* 
* משפט רמזי, באתר לא מדויק 

קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה
רמזי
קטגוריה:הוכחות
רמזי
קטגוריה:תורת רמזי