Course: MCS 582: The Probabilistic Method Call no: 45127 Time: MWF 9:00-9:50pm Place: ONLINE through Zoom
Professor: Dhruv Mubayi Office: 620 SEO E-mail: mubayi@uic.edu Course Web Page: http://www.math.uic.edu/~mubayi/591/Fall2020/ProbMethodFall20info.html Office Hours: M 1-3 on Zoom
Grading Policies:
Your grade will be based on homework assignments (every 2 weeks), attendance and
participation (to the extent possible on Zoom).
Homework *MUST* be typed in Latex
and emailed to me as a pdf file before class begins on the day it is due.
Disability Policy: Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).
Prerequisite: An undergraduate course in combinatorics or probability and the mathematical maturity of a graduate student.
Course Description: The probabilistic method is a powerful tool for tackling many problems in mathematics, statistics and computer science. The basic idea of the method is as follows: in order to prove that a structure with certain desired properties exists, once defines an appropriate probability space of structure
s and then shows that the desired properties hold in this space with positive probability. Introduced by Erdos in the 1940s to solve a basic problem in Ramsey theory, it has since proven useful in many
different areas of mathematics (e.g. geometry, number theory, combinatorics) and more recently in computer science
and statistics as well. The course should therefore be interesting and useful for students in a
variety of fields.
This course will be a thorough introduction to the probabilistic method. While we will focus on applicati
ons in combinatorics, problems in different areas will often be explored.
A sampling of topics: Ramsey numbers, random graphs, Local Lemma, second moment method, correlation inequa
lities (the four function theorem and the FKG inequality), martingales, circuit complexity, discrepancy, geometric problems, derandomization.
Text: The Probabilistic Method by Alon and Spencer (Fourth edition)
Optional Texts:
Random Graphs by Bollobas (second edition)
Random Graphs by Janson, Luczak, Rucinski
Introduction to Random Graphs by Frieze and Karonski (available for free at https://www.math.cmu.edu/~af1p/BOOK.pdf)
Homework 1, Due Friday September 4 (now available)
Homework 2, Due Friday September 18 (now available)
Homework 3, Due Friday October 2 (now available)
Homework 4, Due Friday October 16 (now available)
Homework 5, Due Friday October 30 (now available)
Homework 6, Due Friday November 13 (now available)
Homework 7, Due Friday December 4 (now available)