Combinatorics and Graph Theory I (summer 2020)

Time and place:

Fridays 12:20 to 13:50 in S9

Office hours:

By email appointment.

Online forum:

Questions regarding the lecture content and exercise sheets can be asked on piazza.

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. Counting spanning trees (Invitation 5.3, 8.1, 8.4)

  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

21.2.2020: estimates on factorials, estimates on binomial coefficients, definition of flows

28.2.2020: generating functions, generalized binomial theorem, convergence of generating functions for exponentially bounded sequences, useful operations, applications: Fibonacci numbers and Catalan numbers (i.e., counting binary trees)

6.3.2020: flows and cuts, max-flow min-cut theorem, integer flows in graphs with integer capacities

13.3.2020 (remotely): bipartite graphs and matchings, Hall's theorem

20.3.2020 (remotely): graph connectivity, Menger's theorem

27.3.2020 (remotely): ear decompositions, Ramsey theory, Erdös-Szekeres theorem

3.4.2020 (remotely): Cayley's formula, number of spanning trees, number of edges in graphs without C3

17.4.2020 (remotely): finite projective planes

24.4.2020 (remotely): Latin squares, Sperner's Theorem

15.5.2020 (remotely): error correcting codes

22.5.2020 (remotely): Haming and Singleton bounds, number of edges in graphs without C4, examples of graphs exhibiting this bound

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