LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Independent Sets and Turán's Theorem
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Independent Sets and Turán's Theorem

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

Yufei Zhao continues MIT's 18.226 Probabilistic Methods in Combinatorics with a lecture on independent sets and cliques in graphs, building toward a proof of Turán's theorem. He shows how the probabilistic method, rather than direct combinatorial construction, can establish lower bounds on the size of an independent set a graph must contain given its edge density. The argument proceeds by assigning a random ordering to the vertices and analyzing the expected size of the set this ordering produces, turning an existence question into a calculation about averages. The lecture fits into the course's broader project of using randomness as a proof technique in extremal graph theory. It assumes familiarity with basic graph theory and probability, and works through the argument on the board with minimal digression, typical of the course's dense, proof-driven style.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime15 m
Compared with MathematicsShorter than 99%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 5 of 91 h 26 m before this · 3 h 13 m in total

More from this course

8 LECTURES
Lower Bounds to Ramsey Numbers

Lower Bounds to Ramsey Numbers

MIT · 43 MIN
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
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