Combinatorics and Graph Theory I (summer 2017)
Time and place:
Wednesdays 12:20 to 13:50 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
22. Feb: Estimates of factorials and binomials
1. Mar: Generating functions
8. Mar: Generating functions
15. Mar: Network flows
22. Mar: Network flows
29. Mar: Bipartite matchings, Graph connectivity
5. Apr: Graph connectivity, Ear decompositions
12. Apr: Spanning trees and double counting
19. Apr: Extremal theory and double counting
26. Apr: Finite projective planes
3. May: Finite projective planes (Latin squares), Ramsey theory
10. May: Error correcting codes
24. 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 Wednesdays 14:00 to 15:30 in S11 (right after the lecture)
Herbert S. Wilf: generatingfunctionology.