SubjectsSubjects(version: 944)
Course, academic year 2023/2024
   Login via CAS
Combinatorics and Graph Theory 1 - NDMX011
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: 6
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: cancelled
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: doc. RNDr. Vít Jelínek, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
doc. Andreas Emil Feldmann, Dr.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMA001, NDMI011
Interchangeability : NDMI011
Is incompatible with: NDMI011
Is interchangeable with: NDMI011
Annotation -
Last update: Mgr. Petr Jedelský (22.08.2019)
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: Mgr. Petr Jedelský (22.08.2019)

Andrew Goodall:

There will be two written tests for obtaining a credit (pass) for this course, taken during the semester, based on the topics covered in lectures and tutorials.

To pass the class you should satisfy one of the following criteria:

1) get a score of at least 50% of the total marks on each test taken during the semester.

2) get a score of at least 60% of the total marks on each test that is either missed due to absence or fails to score at least 50% of the total marks, by (re)taking the corresponding test(s), and this to be done latest one week after the end of semester.

You will be informed of what the total mark is when taking the tests.

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

Literature -
Last update: Mgr. Petr Jedelský (22.08.2019)

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: Mgr. Petr Jedelský (22.08.2019)

The exam has a combined form: written and oral. 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: Mgr. Petr Jedelský (22.08.2019)

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 |