Combinatorics and Graph Theory I (summer 2018)
Time and place:
Tuesdays 15:40 to 17:10 in S11
Office hours:
By email appointment.
Syllabus (book chapters)
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)
Spanning trees and double counting (Invitation 5.3, 8.1, 8.?)
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)
Lectures
20. Feb: Estimates of factorials and binomials, definition of generating functions
28. Feb: Generating functions
6. Mar: Network flows
13. Mar: Network flows, Bipartite matchings
20. Mar: Graph connectivity
22. Mar: Graph connectivity, Ear decompositions
22. & 27. Mar: Spanning trees and double counting
27. Mar & 3. Apr: Extremal theory and double counting
10. & 17. Apr: Finite projective planes
17 Apr: Ramsey theory
24 Apr & 15. May: Error correcting codes
Literature
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"
Exam
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).
Other links
English tutorials given by Andrew Goodall on Mondays 15:40 to 17:10 in S11
Herbert S. Wilf: generatingfunctionology.