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

בהרצאה נדבר על גרפים מרחיבים, למה הם מעניינים, ואיך אפשר לבנות אותם. אחרי זה נראה שני שימושים יפהפיים: תיקון שגיאות, ודה-רנדומיזציה.

אם הזמן יאפשר, נדבר קצת על המרחיבים הכי טובים שיכולים להתקיים -- גרפי רמנוג'ן -- וכמה קשה היה לבנות כאלו.