Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-311-MZ-s
Name:
Probabilistic Methods in Discrete Mathematics
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
3
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Kalinowski Rafał (kalinows@agh.edu.pl)
Academic teachers:
dr hab. Kalinowski Rafał (kalinows@agh.edu.pl)
Module summary

Grafy losowe. Metoda probabilistyczną Erdősa, w tym metoda wartości oczekiwanej i lokalny lemat Lovásza.

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)
Skills
M_U001 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. MA2A_W01, MA2A_W07, MA2A_U01, MA2A_U13, MA2A_U16, MA2A_U14 Activity during classes,
Examination,
Test,
Oral answer
M_U002 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. MA2A_U11 Activity during classes,
Examination,
Test,
Oral answer
M_U003 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. MA2A_U01, MA2A_U02 Activity during classes,
Examination,
Test,
Oral answer
Knowledge
M_W001 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. MA2A_W05, MA2A_U11 Activity during classes,
Examination,
Test,
Oral answer
M_W002 zna podstawy teorii grafów losowych. MA2A_W05, MA2A_U13 Activity during classes,
Examination,
Test,
Oral answer
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
Skills
M_U001 potrafi zastosować poznane metody probabilistyczne do rozwiązywania deterministycznych problemów matematyki dyskretnej. + + - - - - - - - - -
M_U002 umie wyznaczyć rozkłady podstawowych niezmienników grafów losowych. + + - - - - - - - - -
M_U003 rozumie dowody twierdzeń przedstawionych na wykładzie i potrafi je przedstawić w mowie i piśmie. + + - - - - - - - - -
Knowledge
M_W001 zna metodę probabilistyczną Erdősa, w tym metodę wartości oczekiwanej i lokalny lemat Lovásza. + + - - - - - - - - -
M_W002 zna podstawy teorii grafów losowych. + + - - - - - - - - -
Module content
Lectures:

1. Zliczanie obiektów kombinatorycznych, w tym kombinacje z powtórzeniami, rozmieszczenia. Zasada włączania i wyłączania. Działanie grupy na zbiorze.

2. Podstawowy model grafów losowych. Wybrane niezmienniki grafów jako zmienne losowe.

3. Twierdzenie Ramseya. Liczby Ramseya.

4. Podstawowa metoda probabilistyczna i jej zastosowanie do oszacowania liczb Ramseya i liczb van der Waerdena.

5. 2-kolorowanie hipergrafów. Systemy różnych reprezentantów

6.. Metoda wartości oczekiwanej i jej zastosowanie: zbiory wolne od sum, 2-kolorowanie hipergrafów.

7. Metoda modyfikacji i jej zastosowanie do oszacowania liczb Ramseya i liczby niezależności grafu. Twierdzenie o zbiorze dominującym.

8. Twierdzenie Tutte’a o grafach bez trójkątów o dowolnie dużej liczbie chromatycznej – z dowodem Mycielskiego. Twierdzenie Erdősa o istnieniu grafów z dowolnie dużą talią i dużą liczbą chromatyczną.

9. Lokalny lemat Lovásza (LLL) w wersji symetrycznej (bd.) i jego zastosowanie do 2-kolorowania regularnych hipergrafów jednolitych.

10. Twierdzenie Erdősa-Lovásza o kolorowaniu prostej rzeczywistej.

11. LLLL i jego zastosowanie do 2-kolorowania hipergrafów.

12. Własności asymptotycznie prawie wszystkich grafów. Przykłady.

13. Funkcje progowe własności grafów. Metoda pierwszego momentu. Metoda drugiego momentu.

14. Twierdzenie o funkcji progowej dla własności zawierania kliki rzędu k. Ewolucja grafów losowych (bd.).

Auditorium classes:
Program ćwiczeń pokrywa się z programem wykładów

Rozwiązywanie problemów (głównie związanych z zagadnieniami teoretycznymi) ilustrujących treści przekazywanych na kolejnych wykładach

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 157 h
Module ECTS credits 6 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 60 h
Participation in auditorium classes 30 h
Preparation for classes 30 h
Contact hours 5 h
Examination or Final test 2 h
Additional information
Method of calculating the final grade:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 1/3 OC + 2/3 OE,
    gdzie OC jest oceną uzyskaną z ćwiczeń,
    a OE jest oceną uzyskaną z egzaminu.
  3. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
  4. Niewielkie odstępstwa są możliwe w zależności od kompetencji egzaminowanego wykazanej w czasie egzaminu.
Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. Z. Palka, A. Ruciński, Niekonstruktywne metody matematyki dyskretnej, WNT 1996.
  2. N. Alon, J. Spencer, The Probabilistic Method, J.Wiley & Sons 1992.
Scientific publications of module course instructors related to the topic of the module:

1. Kalinowski, Rafał; Pilśniak, Monika; Distinguishing graphs by edge-colourings; Eur. J. Comb. 45, 124-131 (2015).

2. Kalinowski, Rafał; Woźniak, Mariusz; Edge-distinguishing index of a graph; Graphs Comb. 30, No. 6, 1469-1477 (2014).

3. Imrich, Wilfried; Kalinowski, Rafał; Lehner, Florian; Pilśniak, Monika; Endomorphism breaking in graphs. Electron. J. Comb. 21, No. 1, Research Paper P1.16, 13 p., electronic only (2014).

4. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; How to personalize the vertices of a graph? Eur. J. Comb. 40, 116-123 (2014).

5. Horňák, Mirko; Kalinowski, Rafał; Meszka, Mariusz; Woźniak, Mariusz
Minimum number of palettes in edge colorings. Graphs Comb. 30, No. 3, 619-626 (2014).

6. Baudon, Olivier; Bensmail, Julien; Kalinowski, Rafał; Marczyk, Antoni; Przybyło, Jakub; Woźniak, Mariusz
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph; Discrete Math. Theor. Comput. Sci. 16, No. 1, 225-232, (2014).

7. Kalinowski, Rafał; Pilśniak, Monika; Przybyło, Jakub; Woźniak, Mariusz; Can colour-blind distinguish colour palettes?; Electron. J. Comb. 20, No. 3, Research Paper P23, 12 p., electronic only (2013).

8. Kalinowski, Rafał; Pilśniak, Monika; Schiermeyer, Ingo; Woźniak, Mariusz; Dense arbitrarily partitionable graphs, Discuss. Math. Graph Theory 36 (2016) 5-22.

9. Kalinowski, Rafał; Pilśniak, Monika; Woźniak, Mariusz; Distinguishing graphs by total colourings, Ars Math. Contemp. 11 (2016), 79-89.

10. The distinguishing index of the Cartesian product of finite graphs; Aleksandra GORZKOWSKA, Rafał KALINOWSKI, Monika PILŚNIAK; Ars Mathematica Contemporanea (2017) vol. 12 no. 1, s. 77–87

11. Distinguishing cartesian products of countable graphs; Ehsan Estaji, Wilfried Imrich, Rafał KALINOWSKI, Monika PILŚNIAK, Thomas Tucker; Discussiones Mathematicae. Graph Theory (2017) vol. 37 iss. 1, s. 155–164.

Additional information:

None