Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Prawdopodobieństwo w grafach

Informacje ogólne

Kod przedmiotu: 1000-1M19PNG Kod Erasmus / ISCED: 11.1 / (0541) Matematyka
Nazwa przedmiotu: Prawdopodobieństwo w grafach
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla IV - V roku matematyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

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).

Pełny opis:

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.

Literatura:

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"

Efekty uczenia się:

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.

Zajęcia w cyklu "Semestr letni 2019/20" (zakończony)

Okres: 2020-02-17 - 2020-08-02
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Michał Kotowski
Prowadzący grup: Michał Kotowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.