Introduction to Combinatorics and Graph Theory - 0366.1123.01

Noga Alon ( nogaa@tau.ac.il )
2nd Semester, 2009-2010 - Tuesday 16-18, Dan David 001
School of Mathematics
Tel-Aviv University

Procedural Matters:

Desirable background: Introduction to Set Theory.
Exercises will be given during the course and their solutions will be graded and form about 10% of the final grade. There will also be a final exam.

Text books:

There are many books that cover the area, including the following.
A. Avron, Introduction to Discrete Mathematics (in Hebrew)
N. Linial and M. Parnas, Discrete Mathematics (in Hebrew)
J. Matousek and J. Nesetril, Invitation to Discrete Mathematics.

Course syllabus:

Basic enumeration methods, the Binomial coefficients, the pigeonhole principle, inclusion-exclusion, asymptotic estimates, recurrence relations, generating functions, the basics of Graph theory: connectivity, bipartite graphs, matchings.

Exercises

More relevant information, including exercises, will appear during the term in: Introduction to Combinatorics and Graph Theory

Course Outline (to be updated during the term):

  1. Feb. 23:
    Introduction, Basic enumeration methods, Basic enumeration problems
  2. March. 2:
    The Binomial coefficients
  3. March 9:
    Catalan numbers, the pigeonhole principle
  4. March 16:
    More on the pigeonhole principle, The Erdos Szekeres Theorem, Inclusion Exclusion
  5. March 23:
    More Inclusion Exclusion
  6. March 30, April 6:
    Passover
  7. April 13:
    Asymptotic estimates
  8. April 20:
    Independence Day
  9. April 27:
    Recurrence relations
  10. May 4:
    More on recurrence relations.
  11. May 11:
    Generating functions
  12. May 18:
    Shavuot
  13. May 25:
    More generating functions
  14. June 1:
    Basic Graph Theory
  15. June 8:
    More Graph Theory, conclusion

Final Exam