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