# Probabilistic Methods in Combinatorics

- Institution: Massachusetts Institute of Technology
- Department: Mathematics
- Teacher: Prof. Yufei Zhao
- Term: Fall 2022
- Level: Graduate
- Language: English
- Subjects: Mathematics
- Source: [MIT OpenCourseWare](https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/)
- Licence: [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) (Non-commercial use only.)
- Syllabus: [at the source](https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/pages/syllabus/)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

This course is a graduate-level introduction to the probabilistic methods, a fundamental and powerful technique in combinatorics and theoretical computer science. The essence of the approach is to show that some combinatorial object exists and prove that a certain random construction works with positive probability. The course focuses on methodology as well as combinatorial applications.

## Lectures

1. [Large Bipartite Subgraph](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/c8edc96ac3e6) (Video)
2. [Lower Bounds to Ramsey Numbers](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/280862fda36a) (Video)
3. [Extremal Set Theory: Sperner's Theorem](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/93592a4d4b55) (Video)
4. [Extremal Set Theory: Intersecting Families](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/ac838cbd3ee8) (Video)
5. [Linearity of Expectations](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/7d9c825e8fa7) (Video)
6. [Independent Sets and Turán's Theorem](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/cb007f5d190f) (Video)
7. [Crossing Number Inequality](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/a7861ef5042c) (Video)
8. [Markov, Chebyshev, and Chernoff](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/96d56a4b265d) (Video)
9. [Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/d390c3945f64) (Video)
10. [Threshold for a Random Graph to Contain a Triangle](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/20c46ced8386) (Video)
11. [Existence of Graphs with High Girth and High Chromatic Number](https://invisiblenetwork.ai/learn/mit/18-226-probabilistic-methods-in-combinatorics-fall-2022/67e3fe41c4e0) (Video)