משפט רמזי

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

מספר רמזי $\ 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$; החסמים הכלליים הטובים ביותר הם $\ 2^{n/2} \leq R_{n,n} \leq \binom{2n-2}{n-1} \approx \frac{1}{\sqrt{\pi(n-1)}} 4^{n-1}$.

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

הוכחת המשפט

ההוכחה תעשה באינדוקציה על $\ m,n$

אם $\ m=1$ ו $\ n\in\mathbb{N}$ כלשהו, אז עבור גרף בגודל 1, יהיה גרף מלא בגודל 1 שכל קשתותיו כחולות, באופן ריק. באופן דומה עבור $\ n=1$ ולכן $\ R_{1,m}=R_{n,1}=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

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