Combinatorics and Graph Theory I (summer 2019)

Time and place:

Thursdays 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. 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.2019: estimates of factorials and binomials, brief introduction to generating functions

28.2.2019: definition of generating functions, Newton formula, main theorem on sequences and generating functions, application: Fibonacci numbers

7.3.2019: application: counting binary trees using generating functions (Catalan numbers), definition of flows and cuts, proof that the value of the max flow is at most the capacity of the min cut

14.3.2019: max-flow min-cut theorem, integral capacities imply integral max flow

21.3.2019: vertex capacitated max-flow min-cut theorem, bipartite matchings and Hall's theorem, bipartite vertex covers and König's theorem

28.3.2019: vertex- and edge-connectivity of graphs, their behaviour when removing vertices and edges, and their relation to each other

4.4.2019: Menger's theorem, ear decompositions

11.4.2019: Cayley's formula and Prüfer codes, nr of spanning trees in a complete graph minus one edge, a lower bound on the maximum number of edges of graphs not containing C_3 as a subgraph

18.4.2019: maximum number of edges not containing C_3 or C_4 as a subgraph, maximum size of an antichain in a poset

25.4.2019: finite projective planes, Fano plane, definition of dual

2.5.2019: a lower bound on the maximum number of edges of graphs not containing C_4 as a subgraph, Latin squares

9.5.2019: Ramsey numbers: upper and lower bounds, longest increasing/decreasing subsequences: upper and lower bounds

16.5.2019: error correcting codes, checksums, Hamming distance, error detection and correction, codes based on finite projective planes

23.5.2019: linear codes, Hamming code, Hamming bound, Singleton 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