LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Crossing Number Inequality
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Crossing Number Inequality

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

Yufei Zhao teaches this lecture from MIT's 18.226 Probabilistic Methods in Combinatorics, proving the crossing number inequality for graph drawings. The lecture shows how the probabilistic method, a tool for proving existence results by analyzing random constructions, can be applied inside graph theory to bound the minimum number of edge crossings in any drawing of a graph with many edges relative to its vertices. Zhao builds the proof step by step, starting from the basic crossing number bound derived from Euler's formula and then strengthening it through a random sampling argument on vertex subsets. The lecture is tightly focused on a single theorem and its proof technique, aimed at students already familiar with basic graph theory and probability, and runs about eighteen minutes as part of the fall 2024 course sequence.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime18 m
Compared with MathematicsShorter than 98%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 6 of 91 h 41 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
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