משפט רמזי

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

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

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

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

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

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

=== הכללות ===

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

== משפט רמזי הסופי ==
מספר רמזי <math>\ R_{n,m}</math> הוא הגודל הקטן ביותר של גרף שלם שקשתותיו צבועות בשני צבעים, נאמר אדום וכחול, המבטיח שהגרף יכיל תת-גרף שלם בן n קודקודים שכולו אדום, או תת-גרף שלם בן m קודקודים שכולו כחול. העובדה שמספרים אלה קיימים היא משפט רמזי. ההוכחה, באינדוקציה, מראה שלמעשה <math>\ R_{n,m} \leq R_{n-1,m}+R_{n,m-1}</math>, ומכיוון ש- <math>\ R_{2,n} = R_{n,2} = n</math>, מתקיים <math>\ R_{n,m} \leq\binom{n+m-2}{n-1} </math>. הערכים המדויקים של מספרי רמזי <math>\ R_{n,n}</math> אינם ידועים עבור <math>\ n\geq 5</math>. ידועים החסמים <math>\ (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</math>. ב-2020 הצליח Ashwin Sah, בעזרת שיטות של קוואזי-אקראיות, להכפיל את החסם העליון בגורם של <math>\ e^{-c (\log n)^2}</math> כאשר c קבוע [https://arxiv.org/pdf/2005.09251.pdf]. ב-2023 הושג, לראשונה מאז 1935, שיפור אקספוננציאלי של החסם העליון: <math>\ R_{n,n} < (3.993)^n</math> [https://arxiv.org/abs/2303.09521].

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

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

=== הוכחת המשפט ===
ההוכחה תעשה באינדוקציה על <math>\ m,n</math>

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

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

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

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

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

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

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

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

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

* 
* [https://gadial.net/2011/08/03/ramsey_theorem/ משפט רמזי], באתר לא מדויק 

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