משפט רמזי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

משפט רמזי האינסופי[עריכת קוד מקור | עריכה]

נתבונן בגרף אינסופי שלם \ G, אשר קשתותיו צבועות בשני צבעים - כחול ואדום.

לגרף זה קיים תת-גרף שלם אינסופי \ G' \subseteq G, אשר כל קשתותיו צבועות באותו הצבע. (אדום או כחול)

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

הוכחה[עריכת קוד מקור | עריכה]

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

נתחיל בקודקוד שרירותי \ v_0 כלשהו. בהכרח קיימים לו אינסוף שכנים המחוברים בקשת אדומה, או אינסוף שכנים המחוברים בקשת כחולה. נוכל להניח בלי הגבלת הכלליות שקיימים לו אינסוף שכנים אדומים. נסמן שכנים אלה ב-\ V_0. אם קיים \ v_1\in V_0 לו אינסוף שכנים אדומים, נצרף אותו לסדרה, ונמשיך את התהליך עבור \ V_1\subseteq V_0 - קבוצת שכניו האדומים של \ v_1, השייכים ל-\ V_0. אם נוכל לחזור על צעד זה לעד, נקבל סדרה של קודקודים, אשר כל אחד מהם קשור לכל האחרים באמצעות קשת אדומה, כרצוי.

אם התהליך ייעצר, משמעות הדבר שמצאנו קבוצה \ V_k אינסופית, אשר לכל אחד מקודקודיה יש מספר אינסופי של שכנים כחולים ורק מספר סופי של שכנים אדומים. לכן אם נחזור על התהליך עבור הקשתות הכחולות בקבוצה \ V_k, התהליך לא יעצר ונקבל קבוצה אין סופית של קודקודים שכל שניים ממנה מחוברים בקשת כחולה.

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

משפט רמזי הסופי[עריכת קוד מקור | עריכה]

מספר רמזי \ 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}.

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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