LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Threshold for a Random Graph to Contain a Triangle
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Threshold for a Random Graph to Contain a Triangle

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

Yufei Zhao teaches a session of MIT's 18.226 Probabilistic Methods in Combinatorics, tackling the question of when a random graph typically contains a triangle. Working on the Erdos-Renyi model, he develops the threshold function for triangle appearance and shows how to pin it down using the first and second moment methods, the core toolkit of the probabilistic method. The lecture walks through computing the expected number of triangles, then uses variance estimates to show concentration around that expectation, demonstrating why the threshold is sharp rather than gradual. Zhao works through the calculations on the board step by step, connecting the abstract moment techniques to the concrete combinatorial count of triangles in a graph. Runtime is under half an hour, making it a focused treatment of a single technique rather than a broad survey, suited to viewers who already know basic graph theory and probability.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime29 m
Compared with MathematicsShorter than 96%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 8 of 92 h 19 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
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
Existence of Graphs with High Girth and High Chromatic Number

Existence of Graphs with High Girth and High Chromatic Number

MIT · 25 MIN