משפט רמזי

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

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

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

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

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

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

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

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

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

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

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

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

מספר רמזי הוא הגודל הקטן ביותר של גרף שלם שקשתותיו צבועות בשני צבעים, נאמר אדום וכחול, המבטיח שהגרף יכיל תת-גרף שלם בן n קודקודים שכולו אדום, או תת-גרף שלם בן m קודקודים שכולו כחול. העובדה שמספרים אלה קיימים היא משפט רמזי. ההוכחה, באינדוקציה, מראה שלמעשה , ומכיוון ש- , מתקיים . הערכים המדויקים של מספרי רמזי אינם ידועים עבור ; החסמים הכלליים הטובים ביותר הם .

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

ניסוח מהופך של המשפט קובע שבכל צביעה בשני צבעים של הגרף השלם על n קודקודים, יש תת-גרף חד-צבעי בן d קודקודים, כאשר ; תוצאה זו היא הטובה ביותר האפשרית.

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

ההוכחה תעשה באינדוקציה על

ברור ש- לכל n,m, משום שקודקוד בודד הוא גרף שלם בגודל 1 (וכל אפס הקשתות שלו אדומות וגם כחולות).

עבור נראה כי .

נניח נתון גרף מלא בגודל שקשתותיו צבועות בכחול ואדום. נבחר ממנו צומת v ונסמן ב B את כל הצמתים שיש מהם קשת כחולה ל v ונסמן ב A את כל הצמתים שיש מהם קשת אדומה ל v. על ידי סימון זה מקבלים ש . לא ייתכן שגם וגם - נניח תחילה ש .

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

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

סה"כ מקבלים שב ישנה קליקה אדומה בגודל או קליקה כחולה בגודל .

ראו גם[עריכת קוד מקור | עריכה]

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

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

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

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