Finding Structure in Expander Graphs (Trinity term)
Classroom C2, 11:00 every Friday
Topics and Materials (We'll cover parts of the following papers (and a few others)):
Introduction and Basic Tools
Main definitions and key properties of expanders. Probabilistic tools, inequalities, notation.
Reference: arXiv:1812.11562
If you have not previously encountered probabilistic methods in combinatorics, you might find it helpful to review
the first chapter of The Probabilistic Method by Alon and Spencer.
Finding Long Paths in Expanders (DFS)
Depth-first search algorithms for constructing long paths.
Reference: Krivelevich, Expanders – how to find them, and what to find in them, available at arXiv:1812.11562
Trees in Expanders (The Extendability Method)
Embedding trees in expanding graphs. The extendability method and rollback technique.
Reference: Draganic, Krivelevich, Nenadov, Rolling backwards can move you forward, available at arXiv:2007.08332
Regularity Lemma
Szemerédi’s Regularity Lemma. Applications to graph embeddings.
References: Komlós, Simonovits, Szemerédi’s Regularity Lemma and Its Applications in Graph Theory
...
Pósa Rotation (Classic and Modern Variations)
Introduction to Pósa’s rotation-extension technique for paths and cycles. Classic applications and recent advancements.
References: Frieze, Karonski, Introduction to Random Graphs, Chapter 6, available at this link.
...
Sublinear Expansion
Definitions and key techniques for analyzing sublinear expanders. Applications to embedding sparse structures.
Reference: Letzter, Sublinear expanders and their applications, available at arXiv:2401.10865
Previous teaching and organizing
Spring 2023 - course organizer for Graph Theory, ETH Zurich.
Fall 2022 - course organizer for Probabilistic Methods in Combinatorics, ETH Zurich.
Autumn 2022 - organizer of the Student Seminar in Combinatorics, ETH Zurich.
Spring 2022 - teaching assistant and course organizer for Graph Theory, ETH Zurich.
Fall 2021 - teaching assistant and course organizer for Algebraic Methods in Combinatorics, ETH Zurich.
Spring 2021 - teaching assistant for Graph Theory, ETH Zurich.
Spring 2020 - teaching assistant for Graph Theory, ETH Zurich.
Spring 2019 - teaching assistant for Analysis II, ETH Zurich.
Fall 2018 - teaching assistant for Analysis I, ETH Zurich.
Fall 2017 - teaching assistant for Analysis I, ETH Zurich.