|
|
|
||
|
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)
|
|
||
|
Hadi Zamani (Winter 2024/2025): To obtain tutorial credit, students must obtain at least 60/90 points from the HW assignments, or at least 60/100 points from the quizzes (best 2 of 3 quizzes count), or at least 100 points in total. To take the exam, students must first obtain tutorial credit. Last update: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
|
|
||
|
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)
|
|
||
|
Josef Tkadlec (Winter 2024/2025): 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: Tkadlec Josef, Bc., Ph.D. (14.10.2024)
|
|
||
|
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)
|