SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Combinatorics - NMAG403
Title: Kombinatorika
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
Class: M Mgr. MSTR
M Mgr. MSTR > Povinné
Classification: Mathematics > Algebra
Annotation -
Basic topics of graph theory and regular combinatorial structures.
Last update: Hladík Milan, prof. Mgr., Ph.D. (01.04.2015)
Course completion requirements -

Credit for recitations is given after obtaining at least 50% points from home assignments (typically 4 sets of problems per semester) + at least 50% attendance of the recitations. These can be substituted in both ways following the formula 2x+4y>=3, where x is the ratio of attendance and y is the ratio of correctly solved home assignments. There is no alternative way nor second try.

Last update: Kratochvíl Jan, prof. RNDr., CSc. (14.10.2023)
Literature -

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

Last update: T_KA (14.05.2013)
Requirements to the exam -

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.

Last update: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)
Syllabus -

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.

Last update: Hladík Milan, prof. Mgr., Ph.D. (01.04.2015)
Charles University | Information system of Charles University |