Kombinatorika - NMAG403

• Anglický název: Combinatorics
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jan Kratochvíl, CSc.
• Třída: M Mgr. MSTR; M Mgr. MSTR > Povinné
• Kategorizace předmětu: Matematika > Algebra

Anotace

čeština

Poslední úprava: T_KA (14.05.2013)

Vytvořující funkce a kombinatorická enumerace. Extremální otázky v grafech a množinových systémech. Ramseyova teorie. Toky v sítích. Strukturálni otázky množinových systémů, transverzály a systémy různých reprezentantů. Pravidelné kombinatorické struktury (bloková schémata, Steinerovy systémy trojic, Latinské čtverce, konečné projektivní roviny). Vnořování grafů na plochy vyšších rodů.

angličtina

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (01.04.2015)

Basic topics of graph theory and regular combinatorial structures.

Podmínky zakončení předmětu

čeština

Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)

Zápočet se uděluje za získání alespoň 50% bodů za domácí úkoly (zpravidla 3 serie úloh). Povaha kontroly studia neumožňuje opakování této kontroly.

angličtina

Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)

Credit for recitations is given after obtaining at least 50% points from home assignments (typically 3 sets of problems per semester). There is no alternative way nor second try.

Literatura

čeština

Poslední úprava: T_KA (14.05.2013)

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2002

Diestel, R.: Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer Verlag, Fourth Edition 2010

Hall, M. Jr.: Combinatorial Theory, Wiley, New York, 1986

Bollobás, B.: Modern Graph Thoery, Graduate Texts in Mathematics, Springer Verlag, 1998

Požadavky ke zkoušce

čeština

Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (23.09.2020)

Zkouška je ústní, může mít kontaktní nebo distanční formu. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce.

angličtina

Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (23.09.2020)

The exam is oral and may be performed remotely. The knowledge and skills examined correspond to the syllabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the acquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enrolling to an exam.

Sylabus

čeština

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (01.04.2015)

Vytvořující funkce a kombinatorická enumerace.

Extremální otázky v grafech a množinových systémech.

Ramseyova teorie.

Toky v sítích a míra souvislosti grafu.

Strukturální otázky množinových systémů, transverzály a systému různých reprezentantů.

Vnořování grafů na plochy vyšších rodů a jejich barevnost.

Pravidelné kombinatorické struktury, jejich existence.

Bloková schémata.

Steinerovy systémy trojic.

Symetrická schémata, věta Bruck-Ryser-Chowla.

Hadamardovy matice.

Latinské čtverce.

Konečné projektivní roviny.

angličtina

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (01.04.2015)

Generating functions and combinatorial enumeration.

Extremal graph theory.

Ramsey theory.

Network flows and graph connectivity measures.

Structural aspects of set systems and transversals.

Embedding of graphs to surfaces of higher genus and their chromatic numbers.

Regular combinatorial structures, existence.

Finite projective planes.

Balanced incomplete block designs.

Steiner triple systems.

Symmetric designs, Bruck-Ryser-Chowla theorem.

Hadamard matrices.

Mutually ortogonal Latin squares.