LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Lower Bounds to Ramsey Numbers
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Lower Bounds to Ramsey Numbers

43 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Probabilistic Methods in Combinatorics · LECTURE 2

Yufei Zhao teaches this session from MIT's 18.226 Probabilistic Methods in Combinatorics, covering how the probabilistic method produces lower bounds for Ramsey numbers. He develops the basic random coloring argument before refining it with the alteration (deletion) method, which removes problematic vertices or edges from a random construction to sharpen the bound. The lecture then turns to the Lovász Local Lemma, showing how it handles dependencies between bad events that the simple union bound cannot, and applies it to push Ramsey number lower bounds further than elementary counting allows. Zhao works through the arguments on the board step by step, connecting each technique back to the central question of how large a graph can be while avoiding both a clique and an independent set of a given size. The lecture assumes familiarity with basic probability and graph theory from earlier sessions in the course.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime43 m
Compared with MathematicsShorter than 93%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 1 of 90 m before this · 3 h 13 m in total

More from this course

8 LECTURES
Extremal Set Theory: Sperner's Theorem

Extremal Set Theory: Sperner's Theorem

MIT · 13 MIN
Extremal Set Theory: Intersecting Families

Extremal Set Theory: Intersecting Families

MIT · 17 MIN
Linearity of Expectations

Linearity of Expectations

MIT · 13 MIN
Independent Sets and Turán's Theorem

Independent Sets and Turán's Theorem

MIT · 15 MIN
Crossing Number Inequality

Crossing Number Inequality

MIT · 18 MIN
Bounded Differences Inequality (Azuma-Hoeffding Inequality)

Bounded Differences Inequality (Azuma-Hoeffding Inequality)

MIT · 20 MIN
Threshold for a Random Graph to Contain a Triangle

Threshold for a Random Graph to Contain a Triangle

MIT · 29 MIN
Existence of Graphs with High Girth and High Chromatic Number

Existence of Graphs with High Girth and High Chromatic Number

MIT · 25 MIN