|
~~~~~
Ma 121 is the
advanced undergraduate/introductory graduate course in
combinatorics. The third term will concentrate on the
probabilistic method, which is a powerful tool premised on the
following basic idea. In order to prove existence of a
combinatorial structure with certain properties, we construct an
appropriate probability space, and show that a randomly chosen
element of this space has the desired property, with positive
probability. Topics covered will include the second moment
method, the local lemma, martingales, correlation and large
deviation inequalities, Poisson approximation and
pseudo-randomness.
Textbook: The probabilistic
method, by N. Alon and J. Spencer, second edition.
Grading: Grades will be
based on fortnightly homework assignments. There will be no
exams.
Homework Policy:
Collaboration on solving the homework problems is encouraged;
however, each student must demonstrate their individual
understanding of the solution by writing it up on their own, in
their own words. Late homework will not be considered without a
documented excuse.
Homework:
Turn in
homework to Ma 121 box outside 253
Sloan.
|