קומבינטוריקה קיצונית

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

משפט רמזי עוסק במבנים המוכרחים להופיע בגרף שלם שהקשתות שלו צבועות בשני צבעים, נאמר אדום וכחול. המשפט קובע שלכל ${\displaystyle \ n}$, אם הגרף שצובעים גדול מספיק (כפונקציה של ${\displaystyle \ n}$), לא ניתן להימנע מיצירת תת-גרף שלם בגודל ${\displaystyle \ n}$ שכל הקשתות שלו צבועות באותו צבע. מהמשפט נובע, למשל, שיש מספר גדול ביותר של משתתפים במסיבה, כך שבין כל חמישה מהם, יש שניים המכירים זה את זה, ושניים שאינם מכירים זה את זה; דהיינו אם מספר המשתתפים גדול מאותו מספר אז בהכרח יש חמישייה שאחת משתי הטענות נכונה לגביה:

• כל חברי החמישייה מכירים זה את זה.
• אף אחד מהחמישייה לא מכיר מישהו אחר בחמישייה.

ערכו המדויק של המספר הזה אינו ידוע.

משפט ארדש-קו-רדו (אנ') קובע שאם מרכיבים ועדות בנות ${\displaystyle k\leq {\frac {n}{2}}}$ חברים בכנסת שיש בה ${\displaystyle \ n}$ חברים, כך שלכל שתי ועדות יש חבר משותף, מספר הוועדות השונות בהרכבן הוא לכל היותר ${\displaystyle \ {\binom {n-1}{k-1}}}$. דוגמה קיצונית המקימת את החסם מתקבלת מקביעת חבר אחד החבר בכל הוועדות וצירופו לאוסף כל הוועדות האפשרויות של ${\displaystyle \ k-1}$ חברים בכנסת שיש בה ${\displaystyle \ n-1}$ חברים. אפשר לשאול גם מהו המספר המקסימלי אם נדרש שלכל שתי ועדות יהיו לפחות r חברים משותפים (בעיית ארדש-קו-רדו), או אם נדרש שבכל שתי ועדות יהיו בדיוק r חברים משותפים (בעיית ארדש-de Bruijn). ומה המספר הגדול ביותר של ועדות בגודל k, אם אסור שיהיו שלוש ועדות שבכל שתיים מהן אותם חברים משותפים? (זו בעיית ארדש-רדו).

גרף טורן - הגרף עם 13 צמתים ומספר מקסימלי של קשתות שאינו מכיל קליקה בגודל 5

משפט טורן עוסק בגרפים: כמה צלעות יכולות להיות בגרף בן n קודקודים, אם אין בו משולשים? ובאופן כללי כמה צלעות יכולות להיות בגרף אם אין לו תת-גרף שהוא קליקה בגודל ${\displaystyle \ r+1}$. לגבי משולשים ידוע כי התשובה היא ${\displaystyle \lfloor n^{2}/4\rfloor }$ ובאופן כללי התשובה היא ${\displaystyle {\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}}$. הגרף הקיצוני (עם מספר הקשתות הגדול ביותר ללא התכונה) מתקבל על ידי חלוקת ${\displaystyle \ n}$ הקדקדים ל${\displaystyle \ r}$ קבוצות שוות וחיבור בקשת של כל שני קודקודים שלא שייכים לאותה קבוצה.

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

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

ראו גם

• תורת רמזי
• למת הרגולריות של סמרדי