Course: MCS 582: The Probabilistic Method Call no: 43767 Time: MWF 12:00-12:50pm Place: BH 304 (in person)
Professor: Dhruv Mubayi Office: 620 SEO E-mail: mubayi@uic.edu Course Web Page: http://www.math.uic.edu/~mubayi/582/Spring2024/ProbMethodSpring24info.html Office Hours: W 10-12 and by appointment
Grading Policies and Points Breakdown:
Your grade will be based on homework assignments every 2 weeks (80%), and attendance and
participation (20%). A grade of 80% on homework (meaning 16/20 for each homework) will usually correlate with an A in the course, assuming good attendance and participation.
You can discuss homework with each other but must write it up independently with no help from anyone else. Do not search the web for solutions, but you are permitted to
search the web for definitions (or just email me)
Homework *MUST* be typed in Latex
and posted on blackboard as a pdf file before class begins on the day it is due.
Accommodations: 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.
Course Goals and Learning Objectives: To gain proficiency in applying the probabilistic method to problems in all areas of mathematics and computer science.
Recommended Coure Materials: 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)
Policy for missed or late work, including acceptance of revised work: Homework turned in late will not be graded unless prior approval of the instructor
has been obtained.
Attendance/Participation Policy: Attendance is required and students are expected to actively participate and engage with the material during lectures.
Community Agreement/Classroom Conduct Policy: Community Agreement: Ground Rules for a Safe/Brave Space
Be present (turn off cell phones and remove yourself from other distractions)
Be respectful
Assume good will
Challenge with care - approach discussion as a think out loud
Take space/make space
11
Identities stay, learning leaves
Try not to make assumptions, seek to understand, not to judge
Be open to challenges as an opportunity to learn something new
Be open to different perspectives
Debate the concepts not the person
Be flexible when things dont work
Share helpful tips
Use preferred names and gender pronouns
No side conversations
Be willing to work together
Homework 1, Due Friday January 19
Homework 2, Due Friday February 2
Homework 3, Due Friday February 16
Homework 4, Due Friday March 1
Homework 5, Due Friday March 15
Homework 6, Due Friday April 5 (extra week due to Spring break)
Homework 7, Due Friday April 19