PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Discrete Mathematics of Paul Erdős - NDMI107
Anglický název: Discrete Mathematics of Paul Erdős
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: https://kam.mff.cuni.cz/~chvatal/NDMI107
Garant: prof. Václav Chvátal, Ph.D.
Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika
Anotace -
Paul Erdős (1913 -- 1996) byl výjimečný, produktivní, vlivný, legendární matematik. Budeme studovat jeho vybrané výsledky z teorie čísel, geometrie, Ramseyovy teorie, extremální kombinatoriky a teorie grafů, které položily základy diskrétní matematiky, než se vyvinula do dnešní dynamické podoby. Občas od jeho práce odbočíme k výsledkům jeho spolupracovníků a následníků, ale nikdy se nevzdálíme z Erdősova gravitačního působení.
Poslední úprava: Bureš Tomáš, prof. RNDr., Ph.D. (15.11.2019)
Podmínky zakončení předmětu -

Osvojení látky v rozsahu syllabu a schopnost je aplikovat na úlohy z oboru.

Poslední úprava: Klimošová Tereza, Mgr., Ph.D. (18.11.2019)
Literatura -

Collected Papers of Paul Erdős up to 1989

S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics DS1: Mar 3, 2017

F.R.K. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), 3-36.

Ronald L. Graham and Fan R. K. Chung, Erdős on Graphs: His Legacy of Unsolved Problems. A K Peters, 1998.

J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley, 1995.

R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory, Wiley, 1990.

E.M. Palmer, Graphical evolution. An introduction to the theory of random graphs, Wiley, 1985.

N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 2016.

V. Chvátal, A De Bruijn-Erdős theorem for graphs? In: Graph Theory Favorite Conjectures and Open Problems - 2, edited by Ralucca Gera, Teresa W. Haynes, and Stephen T. Hedetniemi, Springer Nature Switzerland (2018), pp. 149--176.

Poslední úprava: Klimošová Tereza, Mgr., Ph.D. (18.11.2019)
Sylabus -

Důkaz Bertrandova postulátu. Erdős-Szekeresova, Sylvester-Gallaiova a De Bruijn-Erdősova věta. Ramseyova věta a Ramseyova čísla. Delta systémy a Dezův důkaz Erdős-Lovászovy domněnky. Spernerova věta a Erdős-Ko-Radova věta. Turánova čísla. Vlastnost B a barvení hypergrafů. Van der Waerdenova věta a van der Waerdenova čísla. Extremální teorie grafů. Věta o přátelství, silně regulární grafy a Moorovy grafy průměru dva. Chromatické číslo grafu a pravděpodobnostní metoda. Erdős-Rényiho náhodné grafy a jejich vývoj. Hamiltonovské kružnice.

Poslední úprava: Bureš Tomáš, prof. RNDr., Ph.D. (15.11.2019)
 
Univerzita Karlova | Informační systém UK