MAD 6206-7 Combinatorics

There is no adopted text, but the following are suggested textbooks:

  • Combinatorics: Topics, Techniques, Algorithms, by Cameron, 1995.
  • A Course in Combinatorics, by van Lint and Wilson, 2001.
  • Enumerative Combinatorics, by Stanley, Volume I (2011) and Volume II (2001).

The topics of the PhD Exam vary based upon what was covered during the most recent offering of MAD 6206/6207, and it is therefore highly recommended that students preparing for the test meet with the most recent instructor of MAD 6206/6207. At a minimum, students should demonstrate mastery of the undergraduate sequence MAD 4203/4204, which uses the text A Walk Through Combinatorics by Bona, 2011.

The topics are roughly divided into five parts:

  1. Enumerative combinatorics: generating functions, the binomial theorem, inclusion-exclusion, enumeration under group action.
  2. Graph theory: connectivity, trees, matchings, coloring, planarity, Euler’s theorem, Ramsey’s theorem.
  3. Order theory: posets, Dilworth’s theorem, lattice theory, Moebius inversion.
  4. Extremal combinatorics: intersecting families, Sperner’s theorem, the de Bruijn-Erdos theorem, the probabilistic method (as applied to extremal combinatorics).
  5. Designs: Latin squares, Steiner triple systems, projective planes and finite geometries, block designs, error-correcting codes.
  6. Combinatorial algorithms: bubblesort, quicksort, shortest paths, P, NP.