Module also offered within study programmes:
General information:
Name:
PROBABILISTIC METHODS IN GRAPH THEORY
Course of study:
2016/2017
Code:
AMA-3-203-s
Faculty of:
Applied Mathematics
Study level:
Third-cycle studies
Specialty:
-
Field of study:
Mathematics
Semester:
2
Profile of education:
Academic (A)
Lecture language:
Polski i Angielski
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Academic teachers:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
dr hab. Przybyło Jakub (przybylo@wms.mat.agh.edu.pl)
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
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 Examination,
Activity during classes
Skills
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 Examination,
Activity during classes
M_U002 Rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. MA3A_U01 Examination,
Activity during classes
Knowledge
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 Examination,
Activity during classes
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
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. + + - - - - - - - - -
Skills
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. + + - - - - - - - - -
Knowledge
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. + + - - - - - - - - -
Module content
Lectures:

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.

Auditorium classes:
Program ćwiczeń zgodny z wykładami
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 100 h
Module ECTS credits 4 ECTS
Participation in lectures 28 h
Participation in auditorium classes 28 h
Realization of independently performed tasks 43 h
Examination or Final test 1 h
Additional information
Method of calculating the final grade:

Ocena z egzaminu.

Grade from examination.

Prerequisites and additional requirements:

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

Recommended literature and teaching resources:

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.

Scientific publications of module course instructors related to the topic of the module:

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.

Additional information:

None