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)

  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

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

  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