Syllabus for Qualifying Exam in Combinatorics

The Combinatorics exam covers the following topics from Enumeration, Graph Theory, and Discrete and Computational Geometry.

Enumeration

Basic counting, permutations.
Binomial coefficients (various interpretations), permutations and combinations of multisets.
Stirling numbers with applications to finite differences and Newton interpolation.
Generating functions (ordinary and exponential).
Linear recurrence relations with constant coefficients.
Catalan numbers.
Partitions, Euler's pentagonal theorem, Gauss binomial coefficients.
Inclusion-exclusion principle, permutations with forbidden positions, rook polynomials.
Permutation statistics, Eulerian numbers.
Cayley's enumeration of trees, Prufer code.
Polya's counting.

Matrices and isomorphism, decomposition and special graphs.
Connection in graphs, bipartite graphs, Eulerian circuits.
Extremal problems.
Properties of trees, distance in trees and graphs.
Spanning trees in graphs, minimum spanning tree, Kruskal's algorithm, shortest paths, Dijkstra's algorithm.
Maximum matchings, P. Hall's matching condition and applications (Latin squares), Konig-Egervary Min-Max theorem, independent sets and covers.
Augmenting Path algorithm for maximum matchings in bipartite graphs, the optimal assignment problem and the Hungarian algorithm.
Vertex and edge connectivity, k-connected and k-edge-connected graphs, Menger's theorem.
Maximum network flow, integral flows.
Turan's theorem.

Convex sets and their basic properties.
Caratheodory's Theorems.
Helly's Theorem.
Separation theorems for convex bodies.
Faces of convex polytopes.
Lattices and quadratic forms, lattice constants of convex bodies.
Minkowski's Theorem.
Packing, covering, and tiling; packing and covering densities.
Minkowski-Hlawka theorem.
Sphere packings, codes and groups; sphere packing densities and their bounds; densest sphere packings in low dimensions.
Convex hull algorithms; algorithms for Voronoi diagrams; algorithms for triangulations.

Richard A. Brualdi, Introductory Combinatorics, Third edition, Prentice Hall, 1999.
Richard P. Stanley, Enumerative combinatorics, Volume 1, Cambridge University Press, 2000.
Richard P. Stanley, Enumerative combinatorics, Volume 2, Cambridge University Press, 2001.
Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2000.
Janos Pach and Pankaj K. Agarwal, Combinatorial Geometry, John Wiley & Sons, 1995.
Peter M. Gruber and Cornelis G. Lekkerkerker, Geometry of Numbers, 2nd edition, North-Holland, 1987.
John H.Conway and Neil J.A.Sloane, Sphere Packings, Lattices and Groups, Third edition, Springer Verlag, Grundlehren der mathematischen Wissenschaften, Vol. 327, 1998.