Probability on Graphs

General data

Course ID:	1000-1M19PNG
Erasmus code / ISCED:	11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Mathematics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Probability on Graphs
Name in Polish:	Prawdopodobieństwo w grafach
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for 2nd stage studies in Mathematics
ECTS credit allocation (and other scores):	(not available) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Type of course:	elective monographs
Short description:	(in Polish) Wykład będzie poświęcony procesom losowym na dyskretnych obiektach takich jak grafy, grupy skończone, permutacje, łańcuchy Markowa. Wśród omówionych tematów będą m.in. grafy losowe (model Erdosa-Renyi'ego, grafy d-regularne) i występujące w nich przejścia fazowe, błądzenia losowe i ich czasy mieszania, permutacje losowe, ekspandery i spektralna teoria grafów, a jeśli starczy czasu - związki między grafami skończonymi a nieskończonymi (granice grafów w sensie Benjaminiego-Schramma).
Full description:	(in Polish) 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.
Bibliography:	(in Polish) R. Lyons, Y. Peres "Probability on Trees and Networks" G. Pete "Probability on Graphs and Groups" L. Saloff-Coste "Random Walks on Finite Groups" S. Janson, T. Łuczak, A. Ruciński "Random Graphs" D. Levin, Y. Peres "Markov Chains and Mixing Times" F. Chung "Spectral Graph Theory"
Learning outcomes:	(in Polish) Satysfakcja z poznania nowego kawałka matematyki. Poczucie dobrze spędzonego czasu. Znajomość problemów i metod występujących w rachunku prawdopodobieństwa na dyskretnych strukturach.

This course is not currently offered.

Course descriptions are protected by copyright.
Copyright by University of Warsaw.