Syllabus
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.
Course web page (Irena Penev, Winter 2020/2021): https://iuuk.mff.cuni.cz/~ipenev/NDMI011.html
Annotation
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.