Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Metody probabilistyczne w teorii grafów
Tok studiów:
2019/2020
Kod:
ZSDA-3-0241-s
Wydział:
Szkoła Doktorska AGH
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Szkoła Doktorska AGH
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. Przybyło Jakub (przybylo@wms.mat.agh.edu.pl)
Dyscypliny:
matematyka
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Tematyką modułu są podstawy i zastosowania metody probabilistycznej do rozwiązywania problemów kombinatorycznych, ze szczególnym naciskiem na zaprezentowanie wybranego materiału na podstawie zagadnień związanych z kolorowaniami grafów.
The scope of of this modulus are basics and applications of the probabilistic method to solve combinatorial problems, with special emphasis put on presentation of the chosen subjects on the basis of problems related to graph colourings.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
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. SDA3A_W01 Egzamin
Umiejętności: potrafi
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. SDA3A_U01 Aktywność na zajęciach
M_U002 Rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. SDA3A_U01 Egzamin
Kompetencje społeczne: jest gotów do
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. SDA3A_K01 Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
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. - + - - - - - - - - -
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 zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 39 godz
Egzamin lub kolokwium zaliczeniowe 1 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):

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.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX
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 (30h):

Program ćwiczeń zgodny z wykładami
(Classes’ programme consistent with the lectures)

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: wykład tablicowy; blackboard lecture
  • Ćwiczenia audytoryjne: ćwiczenia z aktywnym udziałem studentów; classes with active participtaion of students
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Obecnośc i aktywność na zajęciach
(attendance and activity within classes)

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: aktywny udział, interakcja z prowadzącym; active participation, interaction with the lecturer
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: aktywny udział, interakcja z prowadzącym; active participation, interaction with the lecturer
Sposób obliczania oceny końcowej:

Ocena z egzaminu.
Grade from examination.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Studiowanie książki ,,Graph Colouring and the Probabilistic Method".
Studying of the book “Graph Colouring and the Probabilistic Method”.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

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 of the Faculty of Applied Mathematics).

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) 1. 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) 2. 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) 3. 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:

-