| Time: | Tue, Thu 13:15 – 14:30 |
| Instructor: | Matthew Kwan,
Office hours: Tue 14:30 – 15:30 or by appointment |
| Assistant: | None |
This is an introductory class on the probabilistic method as a proof technique, and possibly some additional topics in probabilistic combinatorics. The primary textbook for the course will be The probabilistic method by Alon and Spencer, though we may sometimes refer to other books or papers. The breadth and depth of material we cover will depend on the ability and appetite of the students.
The only “hard” prerequsite for this class is familiarity with elementary probability theory (e.g., if you can comfortably use the law of total expectation you are probably fine). Some background in combinatorics and graph theory will be helpful but not essential. The most important “soft” prerequisites for the class are mathematical maturity and familiarity with basic problem-solving techniques.
This course will be graded on a pass/fail basis. Your grade will be determined by some mixture of homework problems and (possibly, if enrollment numbers are sufficiently low for this to be feasible) a presentation on some theorem or technique at the end of the semester.
The Alon–Spencer textbook has some great problems, and I will also collect some other problems at this link. Not all of the Alon–Spencer problems actually require the probabilistic method, and some are very difficult. But you will learn a lot by persevering!
There is no teaching assistant for this class, so grading capacity will be limited. Depending on the number of enrolled students, I will designate some number of exercises as “for credit”, which can be turned in by some deadline to be graded. For other problems, I encourage you to discuss your solutions with your classmates, or compare with the hints at the back of the book, or visit my office hours.
For students interested in affiliation: your progress on these exercises will be useful information for deciding whether you would be a good fit for my group. You should attempt all of the problems in the first 9 chapters of the book and in the above overleaf file, and send me a document with solutions to as many of them as possible (ideally before your rotation). If any of the problems were solved with assistance (e.g., hints from the book, or from other students), please note this down.