Fridays 12:20 to 13:50 in S9
By email appointment.
Questions regarding the lecture content and exercise sheets can be asked on piazza.
Estimates of factorials and binomials (Invitation 3.4 to 3.6)
Generating functions (Invitation 12.1 to 12.3)
Network flows (Modern Graph Theory III.1)
Bipartite matchings (Modern Graph Theory III.3)
Graph connectivity (Modern Graph Theory III.2)
Ear decompositions (Invitation 4.6)
Counting spanning trees (Invitation 5.3, 8.1, 8.4)
Extremal theory and double counting (Invitation 4.7, 7.2, 7.3)
Finite projective planes (Invitation 9)
Ramsey theory (Invitation 11)
Error correcting codes (Lecture notes 2: section 3, Lecture notes 3: all sections, Lecture notes 4: section 1)
21.2.2020: estimates on factorials, estimates on binomial coefficients, definition of flows
28.2.2020: generating functions, generalized binomial theorem, convergence of generating functions for exponentially bounded sequences, useful operations, applications: Fibonacci numbers and Catalan numbers (i.e., counting binary trees)
6.3.2020: flows and cuts, max-flow min-cut theorem, integer flows in graphs with integer capacities
13.3.2020 (remotely): bipartite graphs and matchings, Hall's theorem
20.3.2020 (remotely): graph connectivity, Menger's theorem
27.3.2020 (remotely): ear decompositions, Ramsey theory, Erdös-Szekeres theorem
3.4.2020 (remotely): Cayley's formula, number of spanning trees, number of edges in graphs without C3
17.4.2020 (remotely): finite projective planes
24.4.2020 (remotely): Latin squares, Sperner's Theorem
15.5.2020 (remotely): error correcting codes
22.5.2020 (remotely): Haming and Singleton bounds, number of edges in graphs without C4, examples of graphs exhibiting this bound
Jiří Matoušek and Jaroslav Nešetřil, Invitation to Discrete Mathematics, 2nd ed. 2009
Béla Bollobás, Modern Graph Theory, 1998
Lecture notes "Algorithmic Introduction to Coding Theory"
To pass the course you need to pass the exam at the end of the term. To participate in the exam you also need to pass the tutorials (see below).
English tutorials given by Andrew Goodall on Fridays 14:00 to 15:30 in S9
Herbert S. Wilf: generatingfunctionology.