קומבינטוריקה קיצונית
קומבינטוריקה קיצונית היא תחום בקומבינטוריקה, העוסק במספר הגדול ביותר או הקטן ביותר שיכול להיות לסידורים של אובייקטים סופיים (כמו קבוצות, גרפים או וקטורים מעל שדה סופי), אם מניחים שהם מקיימים תכונות מסוימות.
משפט רמזי עוסק במבנים המוכרחים להופיע בגרף שלם שהקשתות שלו צבועות בשני צבעים, נאמר אדום וכחול. המשפט קובע שלכל , אם הגרף שצובעים גדול מספיק (כפונקציה של ), לא ניתן להימנע מיצירת תת-גרף שלם בגודל שכל הקשתות שלו צבועות באותו צבע. מהמשפט נובע, למשל, שיש מספר גדול ביותר של משתתפים במסיבה, כך שבין כל חמישה מהם, יש שניים המכירים זה את זה, ושניים שאינם מכירים זה את זה; דהיינו אם מספר המשתתפים גדול מאותו מספר אז בהכרח יש חמישייה שאחת משתי הטענות נכונה לגביה:
- כל חברי החמישייה מכירים זה את זה.
- אף אחד מהחמישייה לא מכיר מישהו אחר בחמישייה.
ערכו המדויק של המספר הזה אינו ידוע.
משפט ארדש-קו-רדו (אנ') קובע שאם מרכיבים ועדות בנות חברים בכנסת שיש בה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} חברים, כך שלכל שתי ועדות יש חבר משותף, מספר הוועדות השונות בהרכבן הוא לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \binom{n-1}{k-1}} . דוגמה קיצונית המקימת את החסם מתקבלת מקביעת חבר אחד החבר בכל הוועדות וצירופו לאוסף כל הוועדות האפשרויות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k-1} חברים בכנסת שיש בה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n-1} חברים. אפשר לשאול גם מהו המספר המקסימלי אם נדרש שלכל שתי ועדות יהיו לפחות r חברים משותפים (בעיית ארדש-קו-רדו), או אם נדרש שבכל שתי ועדות יהיו בדיוק r חברים משותפים (בעיית ארדש-de Bruijn). ומה המספר הגדול ביותר של ועדות בגודל k, אם אסור שיהיו שלוש ועדות שבכל שתיים מהן אותם חברים משותפים? (זו בעיית ארדש-רדו).
משפט טורן עוסק בגרפים: כמה צלעות יכולות להיות בגרף בן n קודקודים, אם אין בו משולשים? ובאופן כללי כמה צלעות יכולות להיות בגרף אם אין לו תת-גרף שהוא קליקה בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r+1} . לגבי משולשים ידוע כי התשובה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor n^2/4 \rfloor} ובאופן כללי התשובה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{r-1}{r}\cdot\frac{n^2}{2} } . הגרף הקיצוני (עם מספר הקשתות הגדול ביותר ללא התכונה) מתקבל על ידי חלוקת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} הקדקדים להפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r} קבוצות שוות וחיבור בקשת של כל שני קודקודים שלא שייכים לאותה קבוצה.
התחום עוסק גם בתכונות של מספרים שלמים. למשל, אפשר להוכיח שמכל קבוצה של מספרים אפשר לסמן לפחות שליש, כך שסכומם של שני מספרים שסומנו הוא מספר שלא סומן.
בעיה אחרת שהציע פול ארדש נוגעת בגאומטריה: אם מסמנים n נקודות במישור, כמה זוגות של נקודות יכולים להיות כך שהמרחק ביניהם הוא בדיוק מטר אחד?
ראו גם
קומבינטוריקה קיצונית37554811Q5422299