CS6350 - Topics in combinatorics

Brief Syllabus:

THE CLASSICS: The Erdos-Szekeres theorem, Mantel's theorem, Turan's theorem, Dirichlet's theorem.

EXTREMAL SET THEORY: Intersecting families: The sunflower lemma, The Erdos-Ko-Rado theorem. Chains and antichains: Dilworth's theorem, Sperner's theorem, Bollobas's theorem.

THE LINEAR ALGEBRA METHOD: A short introduction to some basic concepts of linear algebra. The basic method (using linear independence): Fisher's inequality, polynomial technique, Frankl-Wilson theorem, another proof of Bollobas's theorem. Orthogonality and rank arguments: Orthogonal coding, a bribery party, balanced families.

THE PROBABILISTIC METHOD: The basic method, linearity of expectation, alteration technique, second moment method, the local lemma.

POLYNOMIAL METHOD: DeMillo-Lipton-Schwartz-Zippel Lemma, Combinatorial Nullstellensatz

Course books:

  • Extremal combinatorics, by Stasys Jukna.

  • The probabilistic method, by Noga Alon and Joel Spencer.

  • Linear algebra methods in combinatorics with applications in geometry and computer science, by Laszlo Babai and Peter Frankl.

  • Handbook of combinatorics, by R. L. Graham, M. Grotschel, and L. Lovasz.