שיטות הסתברותיות בקומבינטוריקה
תשע״ד
-
הרצאה 1 ←
מבוא לשיטה ההסתברותית
מספרי רמזי אלכסוניים
תכונה של גרפי טורניר
2-צביעה בהיפר-גרפים
קבוצות בלי סכום
תתי קבוצות זרות -
הרצאה 2 ←
משפחות נחתכות וארדש-קו-ראדו
ליניאריות התוחלת
נקודות שבת בפרמוטציה אקראית
חתך אקראי גדול בגרף
k-קליקות מונוכרומטיות ב-2-צביעה אקראית של הגרף השלם
מספר המסלולים ההמילטוניים על גרף טורניר והפרמננטה -
הרצאה 3 ←
שיפור החסם על מספרי רמזי אלכסוניים
קבוצות בלתי תלויות גדולות בגרפים
גרפים עם מותן ומספר צביעה גדולים
חסמים משופרים על גודל היפר-גרף שאינו 2-צביע
סכום מאוזן של וקטורים במקדמים פלוס-מינוס 1 -
הרצאה 4 ←
שיטת המומנט השני ואי שוויון צ'בישב
קבוצות עם סכומים שונים
תכונות מונוטוניות על גרפים ופונקציות סף
פונקציית סף להופעה של תת גרף (מאוזן) נתון -
הרצאה 5 ←
הלמה המקומית של לובאש - גרסה סימטרית
2-צביעה של היפרגרפים יוניפורמיים
מספרי רמזי אלכסוניים
מספרי רמזי של Kk,K3
גרסה כללית של הלמה
קבוצות צבעוניות של מספרים ממשיים
טיולים לטיניים על מטריצות -
הרצאה 6 ←
-
הרצאה 7 ←
חזרה על בחירה מקרית תלויה
שיכון גרף דו-צדדי בגרף חסום דרגות
משפט ארבע הפונקציות
אי שוויון FKG
מסקנות: משפט האריס והלמה של קלייטמן -
הרצאה 8 ←
משפט ה-XYZ כמסקנה של FKG
חסמי ריכוז של מידה: צ'בישב וצ'רנוף
מרטינגלים ודוגמאות: מרטינגל דוב, מרטינגל חשיפת קדקודים/צלעות
אי שוויון אזומה
ריכוז מספר הצביעה של גרף מקרי -
הרצאה 9 ←
חישוב מספר הצביעה של גרף מקרי
ריכוז של מספר הצביעה על אחד מ-4 ערכים
סכום של וקטורים במרחב נורמי
הפרשים חסומים בלתי תלויים (אי שוויון מקדיארמיד)
שימוש: אי שוויון איזופרימטרי על היפר קוביה
אי שוויות טלגרנד -
הרצאה 10 ←
המשך - אי שוויון טלגרנד
שימוש אופייני: תכונות ברות אישור ביחס לפונקציה
אורך תת סדרה עולה מקסימלית של פרמוטציה מקרית
אי שוויון ינסון, מספר הקליקה של גרף מקרי
הסיכוי שגרף מקרי ל-p קטן יכיל משולש -
הרצאה 11 ←
תזכורת על אי שוויון ינסון
אי שוויונות בונפרוני
פרדיגמת פואסון והנפה של ברון
פונקציית סף לכך שכל קדקוד מוכל במשולש
אי שוויונות עבור סטיות גדולות למשתנים מקריים כמעט בלתי תלויים
חסם על מספרי רמזי שאינם (בהכרח) על האלכסון -
הרצאה 12 ←
חזרה - משפחות זרות מקסימליות
עוד על הסיכוי שכל קדקוד נמצא במשולש
אינפורמציה ואנטרופיה
הלמה של שירר
מסקנה על מידה: אי שוויון לומיס-ויטני
משפחות גרפים שהחיתוך של כל שתיים מהן מכיל משולש -
הרצאה 13 ←
הוכחת הלמה של שירר
מספר הקבוצות הבלתי תלויות המקסימליות בגרף רגולרי
ההוכחה למקרה הדו-צדדי והרדוקציה מהמקרה הכללי
מספר החציות של גרף
מסקנה מעניינת: משפט סמרדי-טרוטר
חסם על מספר הסכומים והמכפלות זוגות של איברים בקבוצה