Advanced Combinatorics

Graduate Course in Mathematics and Computer Science
Offered by János Pach
CUNY Graduate Center

We give a systematic introduction to some core areas of combinatorics and graph theory, with special emphasis on links between seemingly unrelated areas and on applications to problems in other parts of mathematics and computer science. Some basic knowledge of combinatorics, linear algebra, and calculus are required.

We cover the following topics:

  • Chromatic number vs. clique number, perfect graphs
  • Coloring algorithms, greedy and probabilistic
  • Graph minors, Hadwigers's conjecture, Hajós theorem
  • Large topological minors in dense graphs
  • Menger's theorem, Konig-Hall theorems, connectivity
  • Lipton-Tarjan separator theorem, divide-and-conquer
  • Applications of linear algebra
  • Combinatorial designs

Recommended Textbooks R. Diestel: Graph Theory, Springer, 1997, 2000.
B. Bollobás: Modern Graph Theory, Springer, 1998.
S. Jukna: Extremal Combinatorics, Springer, 2001.

Midterm 2007
(, combmidterm4.pdf)

Alon-Seymour-Thomas proof (proof of the separator theorem)

VC-dimension and epsilon-nets (hypergraph transversals)