Prawdopodobieństwo na grafach 1000-1M24PGR

Wykład będzie poświęcony prawdopodobieństwu na dyskretnych strukturach takich jak grafy, grupy, permutacje. Jest to aktualnie żywo rozwijająca się tematyka mająca bliskie związki z kombinatoryką, teorią grup, fizyką statystyczną, informatyką teoretyczną. Poznamy wybrane metody probabilistyczne i geometryczne służące do analizy błądzeń losowych, łańcuchów Markowa, własności spektralnych grafów, przejść fazowych.

Wśród omówionych tematów znajdą się m.in.:

- podstawy teorii grafów losowych (model Erdosa-Renyi'ego, losowe grafy d-regularne, przejścia fazowe w grafach losowych)

- czasy mieszania w łańcuchach Markowa (tasowanie kart, coupling, metody spektralne, cut-off)

- permutacje losowe (proces wymiany i jego struktura cyklowa, rozkład Poissona-Dirichleta, metody z teorii reprezentacji)

a jeśli czas nam na to pozwoli, to także:

- spektralna teoria grafów (nierówność Cheegera, ekspandery, grafy Ramanujana)

- granice grafów w sensie Benjaminiego-Schramma, podstawowe własności spektralne grafów nieskończonych

W zależności od zainteresowań słuchaczy mogą pojawić się dodatkowe tematy (np. perkolacja na grafach skończonych, zastosowania non-backtracking random walk, związki z geometryczną teorią grup, metoda probabilistyczna w kombinatoryce).

Wykład przewiduję raczej dla ambitniejszych studentów, czy może bardziej precyzyjnie - dla osób chcących włożyć trochę pracy w solidne nauczenie się czegoś, np. poprzez regularne rozwiązywanie prac domowych i spisywanie notatek z wykładu. W zamian obiecuję dobrą zabawę przy poznawaniu nowej matematyki.