Spektralna teoria grafów i ekspandery

Czas i miejsce

Sala 3230

poniedziałek 23.04: 16-18
środa 25.04: 16-18
piątek 27.04: 18-20
sobota 28.04: 14-18

Plan wykładu

1. dzień: spektrum grafu, podstawowe własności, ekspansja, własności ekspanderów
2. dzień: nierówność Cheegera, nierówność Alona-Boppany
3. dzień: algebraiczne konstrukcje ekspanderów, ekspander Margulisa
4. dzień: kombinatoryczna konstrukcja ekspanderów, zig-zag product
5. dzień: zastosowania ekspanderów w informatyce teoretycznej + desery

Być może oprócz wykładów odbędą się ćwiczenia (do ustalenia). Tu znajduje się skrypt do wykładu (wszelkie uwagi dot. jego treści, a także błędów, literówek itp. mile widziane)

Bibliografia

Lista kilku pozycji (książki, artykuły) o ekspanderach - nie jest oczywiście wyczerpująca, bo literatura na ten temat jest bardzo obszerna. Jakby ktoś chciał coś z tej listy przeczytać, a ma problemy ze znalezieniem, niech napisze.

S. Hoory, N. Linial, Nathan, A. Wigderson Expander graphs and their applications

obszerny (120 stron) i dobry artykuł przeglądowy poruszający większość tematów związanych z ekspanderami (konstrukcje, zastosowania w informatyce teoretycznej, grafy losowe etc.)

T. Tao Math 254B Notes

notatki do wykładu Terence'a Tao; o ekspanderach jest część I, w części II można poczytać o własności (T); dalsze części są na trochę inny (też ciekawy) temat niż niniejszy wykład (ekpansja w grupach typu Liego, kombinatoryka addytywna)

G. Davidoff, P. Sarnak, A. Valette Elementary number theory, group theory, and Ramanujan graphs

książka poświęcona konstrukcji grafów Ramanujana autorstwa Phillipsa, Lubotzk'yego i Sarnaka

F. C. Graham Spectral graph theory

książka o spektralnej teorii grafów (ekspanderom poświęcony jest jeden z rozdziałów)

A. Lubotzky Discrete Groups, Expanding Graphs and Invariant Measures

książka poświęcona związkom ekspanderów z własnością (T), problemem Ruziewicza, grupami Liego, teorią reprezentacji

A. Lubotzky Expander Graphs in Pure and Applied Mathematics

artykuł przeglądowy o zastosowaniach ekspanderów w czystej matematyce

G. Pete Probability and Geometry on Groups

świetne notatki (a w zasadzie książka - 180 stron i stale rośnie) poświęcone tematom z pogranicza probabilistyki i geometrycznej teorii grup; ciekawych zagadnień jest tam mnóstwo, najbliżej tematyki ekspanderów jest rozdział 7.

L. Trevisan Graph Partitioning and Expanders

notatki do wykładu Luki Trevisana; jak nazwa wykładu wskazuje, dużo miejsca poświęcone jest zastosowaniom algorytmicznym

B. Bekka, P. de la Harpe, A. Vallete Property (T)

gruba książka poświęcona własności (T), raczej dla osób zainteresowanych geometryczną teorią grup i pokrewnymi zagadnieniami