MA4050 – Combinatorics and Graph Theory

Course Information

Tentative Syllabus

  1. Basic counting: sum rule, product rule, and inclusion–exclusion principle.
  2. Pigeonhole principle, generalized pigeonhole principle, and their applications.
  3. Permutations and combinations; permutations and combinations with repetitions; binomial and multinomial coefficients.
  4. Weak compositions, compositions, set partitions, Stirling numbers, Bell numbers, integer partitions, Ferrers shapes, conjugate partitions, and Catalan numbers.
  5. Recurrence relations; solving linear recurrence relations with constant coefficients.
  6. Ordinary generating functions and exponential generating functions; solving recurrence relations using generating functions.
  7. Burnside's lemma and linear algebraic methods in combinatorics.
  8. Basics of graphs, graph isomorphism, trees, minimum spanning trees, and Kruskal's algorithm.
  9. Counting spanning trees, Prüfer sequences, Cayley's formula, and the Matrix–Tree theorem (without proof).
  10. Mantel's theorem; bipartite graphs; matchings; Hall's theorem; and systems of distinct representatives.
  11. Eulerian graphs, decompositions, the Graham–Pollak theorem, and Veblen's theorem.
  12. Hamiltonian graphs and Ore's theorem.
  13. Planar graphs, Euler's formula, and its applications.
  14. Chromatic number and the Five Color Theorem.

Textbooks

Problem Sheets