Introduction to Combinatorics and Graph Theory  0366.1123
Noga Alon ( nogaa@tau.ac.il )
2nd (=Spring) Semester, 20152016, Monday 1416, Melamed Hall
School of Mathematics
TelAviv 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, inclusionexclusion, 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):

Feb. 29:
Introduction, Basic enumeration methods, Basic enumeration
problems

March 7:
The Binomial coefficients

March 14:
Catalan numbers

March 21:
The pigeonhole principle,
The Erdos Szekeres Theorem

March 28:
Inclusion Exclusion

April 4:
Asymptotic estimates

April 11:
Recurrence relations

April 18,25:
Passover

May 2:
More recurrence relations, generating functions

May 9:
More Generating functions

May 16:
End of generating functions, Basic Graph Theory

May 23:
No class

May 30 (3 hours):
More Graph Theory

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