Math 5464 (Combinatorics)

Fall of 2008, Professor Brown

Text: "Applied Combinatorics, 2nd Edition" by Roberts and Tesman

What's Combinatorics, anyway?

In a word, it's the art and science of counting. The three basic problems of combinatorics are enumeration (example: "How many ways can you color the faces of a cube using exactly three colors, two colorings being the same if you can rotate one into another?"), existence (example: "Can you arrange 36 officers, taken from six different regiments and having six different ranks, in a six--by--six array in such a way that each row and each column contains someone from each regiment and each rank?"), and optimization (example: "In a factory with eighteen workers and eighteen jobs, with each worker ranking jobs by preference and each job ranking workers by suitability, are there conditions under which no switch of jobs would either satisfy more workers or make more jobs suitable?").

In Math 5464, we will mainly study the Enumeration and Existence problems. Topics include basic counting rules, occupancy problems, generating functions, recurrence relations, the principle of inclusion and exclusion, Polya's theory of counting, combinatorial designs, and any other topic in combinatorics that seems interesting --- if there's time.  Material will be taken from Chapters 1, 2, 5, 6, 7, 8 and 9 of the text. Optimization is usually covered in a course in Graph Theory (Math 5454, to be offered Spring 2009).

Prerequisites: Consent. This is based on a combination of previous courses, mathematical sophistication, and experience. See Instructor for details.