Syllabus for the Comprehensive Exam in Discrete Mathematics

  1. Basic Topics: Inclusion-exclusion; generating functions; recurrence relations and applications to the analysis of algorithms; basic graph algorithms (search algorithms, shortest paths, spanning trees, network flows); basic complexity theory notions (P, NP, NP-completeness)
  2. Fundamentals of Graphs: Isomorphism; trees; spanning trees (minimum-weight spanning trees, counting); bipartite graphs; contraction and minors; Eulerian and Hamiltonian graphs; cycle space and cut space
  3. Connectivity: The max-flow min-cut theorem; Menger's theorem; the structure of 1-, 2-, and 3-connected graphs (blocks, ear-decomposition, contractible edges, Tutte's synthesis of 3-connected graphs)
  4. Matching: Hall's theorem; system of distinct representatives; Tutte's 1-factor theorem; Dilworth's theorem; stable matchings
  5. Coloring: Greedy coloring; Brooks's theorem; chromatic polynomial; Vizing's theorem; the Erdos-de Bruijn compactness theorem; list coloring; perfect graphs; the perfect graph theorem; the vertex-packing polytope
  6. Planar Graphs: Faces and their boundaries; Euler's formula; Kuratowski's theorem; the 5-color theorem; 3-edge-coloring 3-regular planar graphs; planar duality; testing planarity
  7. Extremal Problems: Turan's theorem; the problem of Zarankiewicz; minors
  8. Ramsey Theory: Ramsey's theorem for graphs; upper and lower bounds; Ramsey's theorem for k-tuples
  9. Random Graphs: Models; lower bound for Ramsey numbers; highly chromatic graphs of large girth; properties of random graphs (number of edges, chromatic number, clique number, connectivity, subgraphs, threshold functions, 0-1 law); thresholds and appearance of subgraphs; perfect matchings
  10. Basic Probabilistic Methods: First and second moment methods; alterations
  11. Refined Techniques: Applications of conditioning; the Lovász local lemma; dependent random choice
  12. Inequalities and Applications: Concentration inequalities; correlation inequalities; entropy inequalities; combinatorial applications

 

Suggested textbooks: Modern Graph Theory by Bollobas; The Probabilistic Method by Alon and Spencer; Random Graphs by Janson, Luczak, and Ruciński
Suggested courses: 6014 and 7018
Other relevant courses: 3012