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)

  1. Estimates of factorials and binomials (Invitation 3.4 to 3.6)

  2. Generating functions (Invitation 12.1 to 12.3)

  3. Network flows (Modern Graph Theory III.1)

  4. Bipartite matchings (Modern Graph Theory III.3)

  5. Graph connectivity (Modern Graph Theory III.2)

  6. Ear decompositions (Invitation 4.6)

  7. Spanning trees and double counting (Invitation 5.3, 8.1, 8.?)

  8. Extremal theory and double counting (Invitation 4.7, 7.2, 7.3)

  9. Finite projective planes (Invitation 9)

  10. Ramsey theory (Invitation 11)

  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

  1. Jiří Matoušek and Jaroslav Nešetřil, Invitation to Discrete Mathematics, 2nd ed. 2009

  2. Béla Bollobás, Modern Graph Theory, 1998

  3. 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