משפט רמזי

משפט רמזי

משפט רמזי (Ramsey's theorem) הוא אחד המשפטים המרכזיים בקומבינטוריקה, והוא קובע שבכל צביעה של גרף שלם גדול מספיק בשני צבעים, קיים בהכרח תת-גרף שלם מונוכרומטי בגודל נתון. את המשפט הוכיח פרנק רמזי (Frank Ramsey), והוא הוליד את תחום תורת רמזי העוסק במבנים הכרחיים כאלה. בגרסה האינסופית, כל צביעה של הגרף האינסופי השלם בשני צבעים (או כל מספר סופי של צבעים) מכילה תת-גרף אינסופי מונוכרומטי, והכללה חשובה שלו היא משפט ארדש-רדו (Erdős–Rado) העוסק במונים אינסופיים. בגרסה הסופית, מספר רמזי (R_{n,m}) מוגדר כגודל הקטן ביותר של גרף שלם המבטיח תת-גרף אדום בן (n) קודקודים או כחול בן (m) קודקודים, אך ערכיו המדויקים של (R_{n,n}) אינם ידועים עבור (n \ge 5). במשך שנים היו ידועים רק חסמים כלליים, אך בשנת 2020 שיפר אשווין סאה (Ashwin Sah) את החסם העליון, ובשנת 2023 הושג לראשונה מאז 1935 שיפור אקספוננציאלי, כאשר הוכח כי (R_{n,n} < (3.993)^n). בניסוח מהופך, כל צביעה של גרף שלם על (n) קודקודים מבטיחה תת-גרף מונוכרומטי בגודל של כ-(2\log_2(n)), מה שממחיש את הצמיחה הלוגריתמית של המבנים ההכרחיים הללו.