כותרת: בנייה ומנייה באמצעות השיטה ההסתברותית
תקציר:
שתיים מהשאלות הבסיסיות של המתמטיקאי הטיפוסי הן "האם קיים?" ו"כמה יש?". בהרצאה זו נציג מבוא לשיטה ההסתברותית, שלעתים קרובות מספקת תשובות לשאלות אלה. לאחר הצגת המושגים הבסיסיים נלמד את השיטה דרך דוגמאות:
קיום של גרפים ללא תת-גרף שלם גדול וללא קבוצה בלתי תלויה גדולה:
בהנתן גרף, תת-גרף שלם שלו הינו תת-קבוצה של קודקודים כך שכל הצלעות ביניהם נמצאים בגרף, וקבוצה בלתי תלויה היא תת-קבוצה של הקודקודים ביניהם אין אף צלע.
במאמר שהכניס את השימוש בהסתברות לקומבינטוריקה, פאול ארדש הוכיח שאם בוחרים גרף עם
$2^{k/2}$
קודקודים בהתפלגות אחידה על גרפים אלה, אזי בהסתברות גבוהה לא תהיה לו קבוצה בלתי תלויה או תת-גרף שלם בגודל k.
עד היום לא ידועה בנייה מפורשת של גרפים עם תכונה זו.
מנייה של ריבועים לטיניים:
מטריצה ריבועית מסדר n בה כל שורה ועמודה היא תמורה של המספרים [n] = {1,...n} נקראת ריבוע לטיני. למשל, טבלת החיבור של Z_n (ולמעשה כל חבורה סופית, אם מזהים את איבריה עם [n]) הינה ריבוע לטיני. כמה ריבועים לטיניים יש? שאלה זו נשאלה על ידי אוילר, ונפתרה רק בשנות ה80 של המאה הקודמת. נשתמש בכלים הסתברותיים על מנת לחסום מלמעלה את מספר הריבועים הלטיניים.
לא נניח ידע מוקדם מעבר לתואר ראשון.