קסומים ומרחיבים

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

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

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