# 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.