LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Existence of Graphs with High Girth and High Chromatic Number
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Existence of Graphs with High Girth and High Chromatic Number

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

Yufei Zhao teaches this lecture from MIT's course 18.226, Probabilistic Methods in Combinatorics. The subject is a classic result of Erdős, proved using the probabilistic method: for any choice of girth and chromatic number, there exists a graph achieving both simultaneously. Zhao builds the proof by constructing a random graph model, then shows how to delete a small number of vertices to destroy short cycles while preserving a high chromatic number, a counterintuitive combination since high girth graphs look locally sparse and tree-like. The lecture walks through the probabilistic estimates step by step, including bounds on the expected number of short cycles and the independence number, showing how these pieces combine into the final existence argument. It assumes familiarity with basic probability and graph theory and runs about twenty five minutes as part of a graduate-level sequence on probabilistic techniques in combinatorics.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime25 m
Compared with MathematicsShorter than 97%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 9 of 92 h 48 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
Threshold for a Random Graph to Contain a Triangle

Threshold for a Random Graph to Contain a Triangle

MIT · 29 MIN