הצגת המקור של הדף "קומבינטוריקה קיצונית"

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

[[משפט רמזי]] עוסק במבנים המוכרחים להופיע ב[[גרף שלם]] שהקשתות שלו צבועות בשני צבעים, נאמר אדום וכחול. המשפט קובע שלכל <math>\ n</math>, אם הגרף שצובעים [[גדול מספיק]] (כפונקציה של <math>\ n</math>), לא ניתן להימנע מיצירת תת-גרף שלם בגודל <math>\ n</math> שכל הקשתות שלו צבועות באותו צבע. מהמשפט נובע, למשל, שיש מספר גדול ביותר של משתתפים במסיבה, כך שבין כל חמישה מהם, יש שניים המכירים זה את זה, ושניים שאינם מכירים זה את זה; דהיינו אם מספר המשתתפים גדול מאותו מספר אז בהכרח יש חמישייה שאחת משתי הטענות נכונה לגביה:
*כל חברי החמישייה מכירים זה את זה.
* אף אחד מהחמישייה לא מכיר מישהו אחר בחמישייה.
ערכו המדויק של המספר הזה אינו ידוע.

{{קישור שפה|2=Erdős–Ko–Rado theorem|3=משפט ארדש-קו-רדו}} קובע שאם מרכיבים ועדות בנות <math>k\leq \frac{n}{2}</math> חברים בכנסת שיש בה <math>\ n</math> חברים, כך שלכל שתי ועדות יש חבר משותף, מספר הוועדות השונות בהרכבן הוא לכל היותר <math>\ \binom{n-1}{k-1}</math>. דוגמה קיצונית המקימת את החסם מתקבלת מקביעת חבר אחד החבר בכל הוועדות וצירופו לאוסף כל הוועדות האפשרויות של <math>\ k-1</math> חברים בכנסת שיש בה <math>\ n-1</math> חברים. אפשר לשאול גם מהו המספר המקסימלי אם נדרש שלכל שתי ועדות יהיו לפחות r חברים משותפים (בעיית ארדש-קו-רדו), או אם נדרש שבכל שתי ועדות יהיו בדיוק r חברים משותפים (בעיית ארדש-de Bruijn). ומה המספר הגדול ביותר של ועדות בגודל k, אם אסור שיהיו שלוש ועדות שבכל שתיים מהן אותם חברים משותפים? (זו בעיית ארדש-רדו).

[[קובץ:Turan 13-4.svg|שמאל|ממוזער|200px|גרף טורן - ה[[גרף (תורת הגרפים)|גרף]] עם 13 [[צומת (תורת הגרפים)|צמתים]] ומספר מקסימלי של [[קשת (תורת הגרפים)|קשתות]] שאינו מכיל [[גרף שלם|קליקה]] בגודל 5]]

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

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

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

==ראו גם==
*[[תורת רמזי]]
*[[למת הרגולריות של סמרדי]]
[[קטגוריה:קומבינטוריקה קיצונית|*]]
[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:פאול ארדש]]
[[קטגוריה:בעיות פתוחות במתמטיקה בדידה]]