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.

Graph Theory

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

Discrete and Computational Geometry

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

References

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