נושאים
- מבוא
- דרישות הקורס
דרישות הקורס
הציון בקורס יקבע באופן הבא:
50 נקודות - מבחן כיתה.
50 נקודות - ציוני עבודות בית (ינתנו 4-6 עבודות)
- רשימת ספרות
רשימת ספרות
1. L. Babai and P. Frankl. Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science.
2. S. Jukna. Extremal Combinatorics.
3. O. Pikhurko. Algebraic Methods in Combinatorics.
4. N. Alon. Combinatorial Nullstellensatz.
5. S. Horry, N. Linial and A. Wigderson. Expander graphs and their applications.
6. R. Saptharishi. A survey of lower bounds in arithmetic circuit complexity
7. V. Guruswami, C. Umans and S. Vadhan Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
- סיכומי הרצאות
סיכומי הרצאות
מצורפים סיכומי הרצאות של הקורס משנת תשע״ה. הסיכומים חלקיים ולא ערוכים.
בנוסף, מצורף סיכום קצר של הנקודות העיקריות שהועברו בכל שיעור.
- נושא 4
- שיעור 1 29.10.14
שיעור 1 29.10.14
1. משפט לינדסטרום
2. הלמה של רדון
3. משפט הלי
4. n נקודות שאינן על ישר אחד קובעות n ישרים לפחות.
5. Even town - Odd town
6. אי שיוויון פישר
7. מספרי רמזי והבניה ההסתברותית של ארדש
8. בניית גרף רמזי של נאגי - שיעור 2 5.11.2014
- שיעור 3 12.11
שיעור 3 12.11
דיברנו על משפט Ray-Chaudhuri-Wilson ווריאנטים שלו (מודולרי-לא מודולרי, יוניפורמי-לא יוניפורמי).
ראינו מספר שימושים:
מספר צביעה של גרף מרחקי היחידה במרחב (ראינו גם חסמי כיסוי ואריזה ע״י כדורים n-מימדיים).
בניית גרף רמזי של Frankl-Wilson
- שיעור 4 19.11.2014
שיעור 4 19.11.2014
דיברנו על ערכים עצמיים של מטריצות.
הוכחנו את משפט הופמן סינגלטון ומשפט הידידות.
התחלנו לדבר על גרפים מרחיבים וראינו שימוש להורדת טעות באלגוריתמים אקראיים.
דיברנו גם על קודים לתיקון שגיאות.
- שיעור 5 26.11.2014
שיעור 5 26.11.2014
בנייה של קודים לתיקון שגיאות מגרפים מרחיבים דו-צדדיים ואלגוריתם לתיקון שגיאות.
גרף אקראי מרחיב בהסתברות גבוהה
חסם תחתון על הערך העצמי השני (בערך מוחלט) ע״י שורש הדרגה
הצגת הבנייה של LPS של גרף רמנוג׳אן
Expander Mixing Lemma
- שיעור 6 3.12.2014
שיעור 6 3.12.2014
הילוכים מקריים על גרפים
הילוך מקרי על גרף מרחיב ״בורח״ מכל קבוצה
חסם צ׳רנוף
חסם צ׳רנוף להילוכים על גרפים מרחיבים
- שיעור 7 10.12.2014
שיעור 7 10.12.2014
סיימנו הוכחת חסם צ׳רנוף להילוכים מקריים על גרפים מרחיבים
הגדרנו אקסטרקטורים
בניית אקסטרקטור למקורות עם מינ-אנטרופי גבוה דרך הילוך על גרף מרחיב.
- שיעור 8 17.12.2014
שיעור 8 17.12.2014
קודי Reed-Solomon
אלגוריתם Berlekamp-Welch לפענוח טעויות עד חצי המרחק
הגדרת List-Decoding
חסם קומבינטורי על גודל הרשימה לקודי ריד-סולומון
אלגוריתם List-Decoding של מדהו סודאן.
בעיית קקייה (Kakeya) הממשית ובשדות סופיים.
פתרון לבעיית קקייה בשדות סופיים.
- שיעור 9 24.12.2014
- שיעור 10 31.12.2014
שיעור 10 31.12.2014
שימושים של משפט האפסים הקומבינטורי:
- 1. משפט קושי-דבנפורט
- 2. משפט שבלי-וורנינג
- 3. הצגת הקוביה הבוליאנית המנוקבת כאיחוד של על מישורים.
- 4. למת הפרמננט ושימושיה
טרנסורם פורייה.
מבחן ליניאריות של BLR.
- 1. משפט קושי-דבנפורט