SubjectsSubjects(version: 875)
Course, academic year 2020/2021
Combinatorics and Graph Theory 1 - NDMI011
Title: Kombinatorika a grafy 1
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. RNDr. Vít Jelínek, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
Andreas Emil Feldmann, Dr.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMA001
Annotation -
Last update: PANGRAC/MFF.CUNI.CZ (08.04.2010)
Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.
Course completion requirements -
Last update: Andrew Goodall, D.Phil. (24.04.2020)

Andrew Goodall:

To pass the class you should complete satisfactorily the weekly quizzes by the due dates (which are pass/ fail - you are informed if you fail one when feedback is given to you).

Those quizzes that you have not completed (you will be reminded which ones you have not submitted/ passed by the end of May) can be retaken in the three extra weeks added to this semester, which now ends 12 June 2020.

There is no other provision for repeated attempts at obtaining a course credit.

Literature -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (22.11.2012)

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)

R. Diestel: Graph Theory (4th edition), Springer (2010)

Requirements to the exam -
Last update: Andreas Emil Feldmann, Dr. (29.04.2020)

The exam has a combined form: written and oral. It can be taken either as a remote (online) or a classroom (offline) exam.

The knowledge requirements for the exam correspond to the syllabus of the course.

The ability to generalize and apply the acquired theoretical knowledge from the tutorials is also required.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

Double Counting: Sperner Theorem, The maximum number of edges in a graph without K4 and without K3.

Number of spanning trees (determinant proof) and electrical networks.

Generating functions (understood as Taylor series), applications: Catalan, Fibonacci numbers, solving recurrences, asymptotics of the solution.

Finite projective planes.

Error-correcting codes, basic properties. Hammnig code, Hadamard code. Existence of asymptotically good codes (Gilbert-Varshamov). Hamming's lower bound.

Maximum matching in graphs, Hall's theorem and its applications (Birkhoff-von Neumann theorem), Tutte theorem.

k-connectivity, Menger's theorem. Ear lemma, structure of 2-connected graphs.

Ramsey theorem, Ramsey theorem for p-tuples, Ramsey infinite theorem.

König's theorem on the infinite branch.

Charles University | Information system of Charles University |