משפט רמזי

בקומבינטוריקה, משפט רמזי (באנגלית: 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\cdot 2^{n/2}\leq R_{n,n}\leq {\binom {2n-2}{n-1}}\approx {\frac {1}{\sqrt {\pi (n-1)}}}4^{n-1}$.

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

ניסוח מהופך של המשפט קובע שבכל צביעה בשני צבעים של הגרף השלם על 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$.

ראו גם

• משפט טורן

לקריאה נוספת

• R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY, 1990

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

• משפט רמזי, באתר MathWorld (באנגלית)   
• משפט רמזי, באתר לא מדויק

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31186709משפט רמזי