משפט רמזי

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

בקומבינטוריקה, משפט רמזיאנגלית: 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

אם \ 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
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.