Thursdays 12:20 to 13:50 in S11
By email appointment.
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.2019: estimates of factorials and binomials, brief introduction to generating functions
28.2.2019: definition of generating functions, Newton formula, main theorem on sequences and generating functions, application: Fibonacci numbers
7.3.2019: application: counting binary trees using generating functions (Catalan numbers), definition of flows and cuts, proof that the value of the max flow is at most the capacity of the min cut
14.3.2019: max-flow min-cut theorem, integral capacities imply integral max flow
21.3.2019: vertex capacitated max-flow min-cut theorem, bipartite matchings and Hall's theorem, bipartite vertex covers and König's theorem
28.3.2019: vertex- and edge-connectivity of graphs, their behaviour when removing vertices and edges, and their relation to each other
4.4.2019: Menger's theorem, ear decompositions
11.4.2019: Cayley's formula and Prüfer codes, nr of spanning trees in a complete graph minus one edge, a lower bound on the maximum number of edges of graphs not containing C_3 as a subgraph
18.4.2019: maximum number of edges not containing C_3 or C_4 as a subgraph, maximum size of an antichain in a poset
25.4.2019: finite projective planes, Fano plane, definition of dual
2.5.2019: a lower bound on the maximum number of edges of graphs not containing C_4 as a subgraph, Latin squares
9.5.2019: Ramsey numbers: upper and lower bounds, longest increasing/decreasing subsequences: upper and lower bounds
16.5.2019: error correcting codes, checksums, Hamming distance, error detection and correction, codes based on finite projective planes
23.5.2019: linear codes, Hamming code, Hamming bound, Singleton 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 Ashutosh Rai on Thursdays 15:40 to 17:10 in S11
Herbert S. Wilf: generatingfunctionology.