"Tajne komplety": Spektralna Teoria Grafów
Marcin Kotowski
będziemy z bratem na przełomie kwietnia i maja w Warszawie - w związku
z tym wpadł nam pomysł, żeby zorganizować "tajne komplety" ze
spektralnej teorii grafów i ekspanderów.
Spektralna teoria grafów jest to dział matematyki zajmujący się
analizowaniem własności grafów poprzez badanie wartości własnych ich
macierzy sąsiedztwa. Okazuje się, że prowadzi to głębokich i ciekawych
problemów z przecięcia probabilistyki, kombinatoryki, teorii grup,
algorytmiki i informatyki teoretycznej. Jednym z głównych obiektów
badań są ekspandery, czyli grafy o dobrych własnościach
izoperymetrycznych - znajdują one liczne zastosowania w informatyce
teoretycznej, a ich konstrukcje wymagają nietrywialnych metod z
algebry, kombinatoryki i teorii liczb. Jest to dynamicznie rozwijająca
się gałąź współczesnej matematyki/informatyki, niestety na MIMUWie
właściwie zupełnie nieobecna.
Przykładowe zagadnienia, jakie mogą się pojawić:
1. Podstawowe własności ekspanderów, izoperymetria i nierówność Cheegera
2. Konstrukcje ekspanderów (wybór)
- konstrukcja probabilistyczna, spektralne własności grafów losowych
- konstrukcja algorytmiczna, iloczyn zygzakowy
- konstrukcje algebraiczne - grafy Cayleya grup i własność (T)
- grafy Ramanujana
3. Wybrane zastosowania
- derandomizacja
- teoria kodów
- łańcuchy Markowa
- algorytmy (spectral clustering)
Ciekawego materiału jest oczywiście znacznie więcej, wystarczyłoby go
na co najmniej 1-2 hardcorowe semestralne przedmioty - warsztaty mają
stanowić jedynie wstęp do tematu.
Warsztaty trwałyby ok. tydzień, w trybie - codziennie wykład,
ewentualnie także ćwiczenia/prace domowe, może nawet egzamin domowy
(szczegóły do ustalenia); będą to więc zajęcia dość intensywne.
Wymagana jest jedynie podstawowa znajomość algebry liniowej, elementy
rachunku prawdopodobieństwa i teorii grup. Jeśli jesteście
potencjalnie zainteresowani uczestnictwem (choćby wstępnie, np. modulo
dokładny termin), napiszcie - jeśli zgłoszą się 2 czy 3 osoby, to
raczej szkoda zachodu (przygotowanie takich zajęć wymaga dużo pracy),
ale jeśli zbierze się grupa dobrych chętnych osób chcących aktywnie
uczestniczyć, myślę, że będzie fajnie.
Jeśli kojarzysz kogośz matematyków lub informatyków, kto może być
zainteresowany, a nie ma go wśród adresatów - zachęcam do
sforwardowania maila. W razie jakichkolwiek pytań etc., piszcie
śmiało.
Pozdrawiam,
Marcin