משפט רמזי

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

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

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

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

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

1- בהכרח קיים r כזה לכל m ו- l

2- סימטריה: (R(m,l) = R(l,m

-3 R(m,2) =m R(m,1) =1

,