Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Metody probabilistyczne w teorii grafów
Tok studiów:
2016/2017
Kod:
AMA-3-403-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Matematyka
Semestr:
4
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Osoby prowadzące:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
dr hab. Przybyło Jakub (przybylo@wms.mat.agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Ma rozszerzoną wiedzę o podstawach metody probabilistycznej, obejmującą m.in. różne wersje lokalnego lematu Lovásza oraz szereg twierdzeń o koncentracji. Zna konkretne przykłady zastosowań poznanych narzędzi probabilistycznych w dowodach twierdzeń kombinatorycznych. MA3A_W01 Egzamin,
Aktywność na zajęciach
Umiejętności
M_U001 Potrafi zastosować poznane metody probabilistyczne do rozwiązania deterministycznych problemów matematyki dyskretnej. Potrafi zidentyfikować problem, do rozwiązania którego można posłużyć się metodą probabilistyczną, potrafi stworzyć w tym celu odpowiedni model losowy i wykonać niezbędne operacje optymalizacyjne w celu uzyskania możliwie najmocniejszej tezy. MA3A_U01 Egzamin,
Aktywność na zajęciach
M_U002 Rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. MA3A_U01 Egzamin,
Aktywność na zajęciach
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i rozwoju swoich umiejętności w zakresie stosowania metody probabilistycznej. MA3A_K01 Egzamin,
Aktywność na zajęciach
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Ma rozszerzoną wiedzę o podstawach metody probabilistycznej, obejmującą m.in. różne wersje lokalnego lematu Lovásza oraz szereg twierdzeń o koncentracji. Zna konkretne przykłady zastosowań poznanych narzędzi probabilistycznych w dowodach twierdzeń kombinatorycznych. + + - - - - - - - - -
Umiejętności
M_U001 Potrafi zastosować poznane metody probabilistyczne do rozwiązania deterministycznych problemów matematyki dyskretnej. Potrafi zidentyfikować problem, do rozwiązania którego można posłużyć się metodą probabilistyczną, potrafi stworzyć w tym celu odpowiedni model losowy i wykonać niezbędne operacje optymalizacyjne w celu uzyskania możliwie najmocniejszej tezy. + + - - - - - - - - -
M_U002 Rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. + + - - - - - - - - -
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy, zdaje sobie sprawę z potrzeby dalszego kształcenia i rozwoju swoich umiejętności w zakresie stosowania metody probabilistycznej. + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

PL

1. Twierdzenie Madera nawiązujące do hipotezy Hadwigera – przypomnienie podstaw metody probabilistycznej.

2. Przypomnienie lokalnego lematu Lovásza, zasada wzajemnej niezależności oraz zastosowanie do badania kolorowań z ograniczeniami powiązanych z listową liczbą chromatyczną.

3. Ograniczenie Chernoffa i jego zastosowanie do znajdowania kontrprzykładów przeciwko hipotezie Hajósa.

4. Hipoteza o kolorowaniu totalnym – połączenie lokalnego lematu Lovásza z ograniczeniem Chernoffa.

5. Nierówności Talagranda vs ograniczenie Chernoffa i prosta nierówność koncentracyjna.

6. Naiwna procedura kolorowania a kolorowanie grafów bez trójkątów.

7. Kolorowanie grafów rzadkich i silne kolorowania krawędzi.

8. Nierówność Azumy.

9. Podejście iteracyjne a kolorowania grafów o talii przynajmniej pięć.

10. Metoda pseudolosowa – kontynuacja; uwagi o dowodzie twierdzenia Kahna nawiązującego do hipotezy o listowym kolorowaniu wierzchołków grafu.

11. Różne wersje lokalnego lematu Lovásza oraz ich zastosowania.

12. Liczba chromatyczna Thuego – ograniczenie górne i ograniczenie dolne wykorzystujące grafy losowe.

13. Metoda kompresji entropii a listowa wersja twierdzenia Thuego.

14. Inne zastosowania metody kompresji entropii.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

EN

1. Mader’s theorem on the way towards Hadwiger’s Conjecture – reminder of the basics of the probabilistic method.

2. Reminder of the Lovász Local Lemma, mutual independence principle, and an application to investigate constrained colourings associated with the list chromatic number.

3. The Chernoff Bound and its application for finding counterexamples against Hajós’ Conjecture.

4. The Total Colouring Conjecture – combining the Lovász Local Lemma and the Chernoff Bound.

5. Talagrand’s Inequalities vs Chernoff Bound and the Simple Concentration Bound.

6. A naive colouring procedure and colouring triangle-free graphs.

7. Colouring sparse graphs and strong edge colourings.

8. Azuma’s Inequality.

9. Iterative approach and colouring graphs of girth at least five.

10. Pseudo-random method – a continuation; remarks on Kahn’s proof towards the List Colouring Conjecture.

11. Variations of the Lovász Local Lemma and their applications.

12. The Thue chromatic number – the upper bound and the lower bound exploiting random graphs.

13. The entropy compression method and a list version of Thue’s theorem.

14. Other applications of the entropy compression method.

Ćwiczenia audytoryjne:
Program ćwiczeń zgodny z wykładami
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 100 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 28 godz
Udział w ćwiczeniach audytoryjnych 28 godz
Samodzielne studiowanie tematyki zajęć 43 godz
Egzamin lub kolokwium zaliczeniowe 1 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena z egzaminu.

Grade from examination.

Wymagania wstępne i dodatkowe:

Teoria grafów oraz metody probabilistyczne matematyki dyskretnej (w zakresie wykładanym na studiach magisterskich WMS) .

Graph Theory and Probabilistic Methods of Discrete Mathematics (in the area that is taught in graduate studies in our faculty).

Zalecana literatura i pomoce naukowe:

1. M. Molloy, B. Reed, Graph Colouring and the Probabilistic Method, Springer 2002.

2. N. Alon, J. Spencer, The Probabilistic Method, J. Wiley & Sons 2008.

3. Z. Palka, A. Ruciński, Niekonstruktywne metody matematyki dyskretnej, WNT 1996.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak, On decomposing regular graphs into locally irregular subgraphs, European Journal of Combinatorics 49 (2015) 90-104.
2. J. Grytczuk, J. Przybyło, Xuding Zhu, Nonrepetitive List Colourings of Paths, Random Structures Algorithms Volume 38, Issue 1-2 (2011) Pages 162–173.
3. W. Imrich, R. Kalinowski, F. Lehner, M. Pilśniak, Endomorphism breaking in graphs, The Electronic Journal of Combinatorics, 21 (2014) #P1.16.
4. R. Kalinowski, M. Pilśniak, J. Przybyło, M, Woźniak, Can colour-blind distinguish colour palettes?, The Electronic Journal of Combinatorics, 20 (2013) #P23.
5. P. Majerski, J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28(1) (2014) 197-205.
6. P. Majerski, J. Przybyło, Total vertex irregularity strength of dense graphs, J. Graph Theory 76(1) (2014) 34-41.
7. J. Przybyło, Asymptotically optimal neighbour sum distinguishing colourings of graphs, Random Structures Algorithms 47 (2015) 776-791.
8. J. Przybyło, Colour-blind can distinguish colour pallets, Electron. J. Combin. 21(2) (2014) #P2.19.
9. J. Przybyło, On colour-blind distinguishing colour pallets in regular graphs, Journal of Combinatorial Optimization 28(2) (2014) 348-357.
10. J. Przybyło, On decomposing graphs of large minimum degree into locally irregular subgraphs, arXiv:1508.01129.
11. J. Przybyło, On the facial Thue choice index via entropy compression, J. Graph Theory 77(3) (2014) 180-189.
12. J. Przybyło, On upper bounds for multiple domination numbers of graphs, Discrete Appl. Math. 161(16-17) (2013) 2758-2763.

Informacje dodatkowe:

Brak