Learn · MIT OpenCourseWare

Photo of Paul Erdős wearing glasses.

Course18.22611 lectures

Probabilistic Methods in Combinatorics

Prof. Yufei Zhao · Massachusetts Institute of Technology

Start with lecture 1 At MIT OpenCourseWare

About

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

Lecture Videos

  1. Large Bipartite Subgraph Video
  2. Lower Bounds to Ramsey Numbers Video
  3. Extremal Set Theory: Sperner's Theorem Video
  4. Extremal Set Theory: Intersecting Families Video
  5. Linearity of Expectations Video
  6. Independent Sets and Turán's Theorem Video
  7. Crossing Number Inequality Video
  8. Markov, Chebyshev, and Chernoff Video
  9. Bounded Differences Inequality (aka Azuma-Hoeffding Inequality) Video
  10. Threshold for a Random Graph to Contain a Triangle Video
  11. Existence of Graphs with High Girth and High Chromatic Number Video

Syllabus and materials

At MIT OpenCourseWare, as the course publishes them.

Credits and licence

Institution
Massachusetts Institute of Technology
Department
Mathematics
Teacher
Prof. Yufei Zhao
Term
Fall 2022
Level
Graduate
Language
English
Subjects
Mathematics
Source
MIT OpenCourseWare
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only. MIT OpenCourseWare's terms
Attribution
Prof. Yufei Zhao. Probabilistic Methods in Combinatorics. Fall 2022. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
MIT OpenCourseWare gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed