|
|
|
||
|
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.
Last update: PANGRAC/MFF.CUNI.CZ (08.04.2010)
|
|
||
|
Guillermo Gamboa, Gaurav Kucheriya (Winter 2025/2026): To obtain tutorial credit, students must obtain at least 50 points. Up to 30 points can be obtained for homeworks, up to 30 points for activity during tutorials, up to 30 points for short tests given during lectures. To take the exam, students must first obtain tutorial credit. There is no other provision for repeated attempts at obtaining a course credit. Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (06.10.2025)
|
|
||
|
J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)
R. Diestel: Graph Theory (4th edition), Springer (2010) Last update: Jelínek Vít, doc. RNDr., Ph.D. (22.11.2012)
|
|
||
|
Zdeněk Dvořák (Winter 2025/2026): To take the exam, students must first obtain tutorial credit. The exam has a combined form: written and oral. In the written part, you might be required to state a definition/theorem from the lecture; to prove a theorem from the lecture; and/or to solve a problem related to the material covered in the lecture/tutorial. Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (06.10.2025)
|
|
||
|
Double Counting: Sperner Theorem, The maximum number of edges in a graph without C4 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. Last update: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
|