Four Great Numberphile Graph Theory Videos

A quick link to our previous post: Gil Bor, Luis Hernández-Lamoneda, Valentín Jiménez-Desantiago, and Luis Montejano-Peimbert: On the isometric conjecture of Banach.


We have mentioned the Numberphile video channel before (here, and here, and here). It has amazing videos for the very general public about mathematics. And the general public is interested! The channel has more than 3 millions subscribers and a Numberphile video gets usually well over 100,000 views.  While the videos are for very general audiences it is quite common that I learn new mathematics while watching these videos. Today I mention four recent Numberphile videos on graph theory.

Before that, let me mention that, while combinatorics has a special appeal for general audiences, it is a hard challenge to explain to a very large audience (or even to the large audience of Quanta Magazine) some very abstract areas of mathematics. It is not impossible: Here is Kevin Hartnett’s article in Quanta Magazine on ∞-categories and Jacob Lurie’s work and here is a 2016 article by Erica Klarreich on perfectoid spaces and Peter Schotze’s work. I hope to see Numberphile moving into these areas as well.

A breakthrough in Graph theory:  Yaroslav Shitov’s counterexample to Hedetniemi’s conjecture as told by Erica Klarreich.

For more on this development see this post. The video contains nice pictures of Stephen Hedetniemi and his 1966 thesis. An exciting open question is: Given two graphs of chromatic number n is the chromatic number of their tensor product at least some f(n), where f(n) tends to infinity with n.

Maria Chudnovsky – perfect graphs

Starting with the definition and ending with the strong perfect graph theorem (conjectured by Claud Berge) by Chudnovsky, Seymour, Robertson and Thomas.

An exciting open question: Find a good definition for perfect r-uniform hypergraphs.

We discussed perfect graphs and related notions in this post, this one and this one.

(Remark: Numberphile misguidedly regarded this video as a continuation of the “planar graph” video. The truth of the matter is that these are separated topics and the perfect graph video should be a separate Numperphile video.)

Maria Chudnovsky – planar graphs

Planar graphs are deep and fascinating (and miraculous, and always surprising) mathematical objects.  In Hebrew we can say about the topic that it is “Olam Umelo’o” (עולם ומלואו) (=a whole world with all its content). There are many fascinating properties of planar graphs and many open problems about them.

There are also many fascinating generalizations. Let me mention Abby Thompson’s problem: Suppose that G is the graph of a simple d-polytope with n vertices. Suppose also that n is even (this is automatic if d is odd). Can we always properly color the edges of G with d colors? (For d=3, the answer is yes and this is the four color theorem.)

(We discussed planar graphs here and on MO, many times.)

Discussing vertex covers and Alcuin numbers for graphs – and a famous old puzzle. Filmed at MSRI with Annie Raymond.

We discussed here and in other posts the important notion of vertex covers, but the mathematics of the video was completely new to me.

This entry was posted in Combinatorics and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s