Introduction to Combinatorics and Graph Theory - 0366.1123

Noga Alon ( )
2nd (=Spring) Semester, 2015-2016, Monday 14-16, Melamed Hall
School of Mathematics
Tel-Aviv University
Instructor: Gal Kronenberg

Procedural Matters:

Desirable background: Introduction to Set Theory, Linear Algebra 1, Calculus 1.
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 and Catalan numbers, the pigeonhole principle, inclusion-exclusion, asymptotic estimates, recurrence relations, generating functions, the basics of Graph theory: connectivity, bipartite graphs, matchings.

(Much) more relevant information, including exercises, will appear in the course page in Moodle: Introduction to Combinatorics and Graph Theory

Course Outline (to be updated during the term):

  1. Feb. 29:
    Introduction, Basic enumeration methods, Basic enumeration problems
  2. March 7:
    The Binomial coefficients
  3. March 14:
    Catalan numbers
  4. March 21:
    The pigeonhole principle, The Erdos Szekeres Theorem
  5. March 28:
    Inclusion Exclusion
  6. April 4:
    Asymptotic estimates
  7. April 11:
    Recurrence relations
  8. April 18,25:
  9. May 2:
    More recurrence relations, generating functions
  10. May 9:
    More Generating functions
  11. May 16:
    End of generating functions, Basic Graph Theory
  12. May 23:
    No class
  13. May 30 (3 hours):
    More Graph Theory
  14. June 6:
    End of Graph Theory, conclusion

Exams from previous years:

Spring 2010, Moed A

Spring 2010, Moed B

Spring 2011, Moed A

Spring 2011, Moed B

Spring 2013, Moed A

Spring 2013, Moed B

Spring 2014, Moed A

Spring 2014, Moed B

Spring 2015, Moed A

Spring 2016, Moed A