Combinatorics (MATH 84530)


Graduate Course in Mathematics and Computer Science
Offered by János Pach
Fall Term, 2006, Wednesdays 4:15-6:15pm
CUNY Graduate Center, Rm 6496


We give a systematic introduction to some core areas of combinatorics 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 linear algebra, calculus, and familiarity with the notion of finite fields are required.

We cover the following topics:

  • Combinatorial counting
  • Double-counting, parity arguments
  • The number of spanning trees
  • Dilworth' theorem and extremal set theory
  • Finite projective planes, latin squares
  • Proofs by counting: probabilistic proofs
  • Generating functions
  • Partitions
  • Applications of linear algebra
  • Combinatorial designs

Recommended Textbooks J. Matoušek and J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press, 1998.
L. Lovász, J. Pelikán and K. Vesztergombi: Discrete Mathematics, Springer, Berlin, 2003.


Midterm 2001
(combmidterm2.ps, combmidterm2.pdf)

Final Exam 2001 (final)

  Midterm 2006 (combmidterm3.pdf, combmidterm3.ps)  
  Final 2006 (combfinal3.pdf, combfinal3.ps)