Solving the Wolverine Problem with Graph Coloring | Infinite Series

At one time, Wolverine served on four different superhero teams. How did he do it? He may have used graph coloring.

Tweet at us! @pbsinfinite
Email us! pbsinfiniteseries [at] gmail [dot] com

Graph coloring may seem simple but the mathematics behind it is surprising difficult and it pops up in a number strange places. Kelsey discusses Sudoku, the Four Color Theorem, the Hadwiger Nelson Problem and how graph coloring can be used to schedule the most effective way to save the planet. Find out how math can defeat the combined might of Thanos, Magneto, Kang, Dormammu, Ultron, Apocalypse and Dr. Doom.

Correction: At 3:58, "Four is the maximum number of required colors"

Previous Episode - What is a Random Walk?

Links to other resources:

Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux

Comments answered by Kelsey:

Ofir David

Bertie Blue

​TehAvenger29

[shubhamshinde]

PBS digital studios is a gift to the world!

[sicklebrick]

She's such a good presenter. So clear, so well spoken, everything's so well explained, no rushing. Thanks!

[marcuslaurel]

How about let's not let epsilon be less than zero.

[slagondrayer]

I have no idea what's going on, but I'm going to keep watching these.

[jotha]

As of April 8 2018, The Hadwiger–Nelson problem is now bounded between 5 and 7 (a non-4-colourable as been found!)

[jakubpekarek]

"What is it that you do?"
"The last few years, I do research of graph coloring."
- silent stare -
"I swear I'm sane."
(my life in a nutshell)

[gauravmanwani]

A bit intuitive approach to the problem-
Imagine the plane to be composed of minuscule square pixels. Now to make sure that our condition is satisfied, colour the vertices in four distinct colours. Now because each pixel shares a pair of vertices common with 4 other pixels, we can grow our Qualified Pixel many folds to cover the plane, thus getting the required Qualified Plane. To use this in problems like HWN problem, just vary then side lengths of each square, as per need. Math is beautiful!

[kamoroso]

For the challenge question, the graph at 10:47 can be thought of a subgraph of the graph that connects all the points in the plane that are 1cm apart. This is because this graph can be constructed such that each vertex is situated 1cm apart from all the other vertices it shares an edge with. When you find that the chromatic number of this graph is 4, that means the graph which it's a part of must have a chromatic number of at least 4, since it's embedded in it. It can have a higher chromatic number, but not one less. That's my proof in layman's terms :)

[Pika]

There is no equivalent of the four-color theorem to 3-dim space. Take the unit 1 x 1 square and color it in such a way that any two points that have the same x coordinate are the same color, and no two points that have different x coordinates are the same color. Let 1/2 be the thickness of this square. Take a copy of this square, rotate it 90 degrees counterclockwise, and glue it directly on top of the original. In this way we obtain a cube where every color touches every other color at least once: a *c* coloring.

[CorbinSimpson]

Hi! I am, among other things, a compiler author. Here's the graph coloring problem I'm most familiar with.

In register machines, a common class of computer which includes the CPUs in laptops, routers, phones, The Cloud, etc., there is a problem called *register coloring* which is equivalent to graph coloring, and we must tackle it every time we compile code for register machines. A k-coloring of a graph is equivalent to a compiled program's usage of k registers, so we first generate a graph describing the program's register usage, and then we try to color it.

In practice, k is usually too large for the target CPU, so some of the registers must be *spilled*, which just means that we emulate the register with a location in RAM. Spilling slows things down when we do it, but allows us to compile all programs. So we have to have spilling but we try to minimize how much we spill, which means that we are interested in partial solutions and optimizing, not just exact solutions.

My favorite planar graph which cannot be 3-colored is the graph corresponding to the map of the states of the continental USA.

[verdatum]

For awhile now, I've been one of a tiny number of software-engineers maintaining and improving some sophisticated enterprise-level graphing software. I learned about graphs in college, but only really briefly as part of my discrete-structures course. Man is-it-ever one *huge* field of study. I've still got tons to learn.
I know it's not directly a coloring problem, but my favorite graphing topic is minimal-crossing arrangement heuristics. The actual solution is NP-hard, so the trick is to have algorithms that, for problems dealing with more than a handful of vertices and edges, do an OK job at rearranging without telling the user to send their great grandchildren over sometime next century to see the result.

[atridas]

The part about sudoku and graph coloring made me thing about something:

Almost every game moderately puzzle-based (not "physical") is a NP problem behind the scenes. Think most of the modern tabletop games (Agricola, Carcassone, etc...) and a lot of videogames (Bejewelled, The Witness, ...).

[Daniel-Brous]

Challenge Problem Answer: In the graph that you gave us to work with, one can draw such a graph with all of the sides having length 1 centimeter. Since each length connects two different colors, no one needs to be replicated 1 centimeter away from the section. One can imagine a circle of radius 1 centimeter coming out of each colored point. Looking at each of the triangles in the graph, we know that if we draw that circle around one of the vertices, it will only intersect the other two vertices of the triangle and nothing inside of it. So by drawing a point inside each of the smaller triangles, but of the same color as the outer vertex, the diagram still works because one can have any amount of the same color within a triangle, just not along that circle. The only other time the color appears is greater than 1 centimeter away from the closest points. Thus, the diagram satisfies that no two points of the same color are 1 centimeter apart, even though they may be infinitely close to 1 centimeter apart. So since this diagram can be filled with four colors at minimum, the entire plane must be filled in no less than 4, or in other words, at least 4.

[Mohanchous]

By stacking one brick atop another, a finite stack can project arbitrarily far as shown in the video. But an infinite stack can only project half a brick width.

[GelidGanef]

It requires at least four colors to color every planar graph of unit-length edges, because the picture given (10:55) is a graph whose edges are all the same length and it requires at least four colors.

Obviously, you have to color the center vertex a "fourth" color if you use three different colors for the outside of the hexagon. So instead, we're just going to use two, alternating back and forth between red and blue. That triangle in the center connects to three of our hexagon vertices, but because we alternated between only two colors, it connects to three vertices of the same color. Now we have to color three vertices, which all connect to each other. But one of the two colors we used before is ruled out, because they also all connect to that color.

Since trying to color this graph with three colors still forces us to use four colors, the graph must require at least four colors.

[mesplin]

Wolverine: Professor X! I need your help scheduling!
Prof X: Don't worry, I have studied graph theory.
* Colors graph then saves the world *

[mitrajsinhchavda]

Woha... Education, that girl and marvel.. Best combination man! Loved it

[lukasnor]

My solution to the challenge question is the following (assuming that the graph connects points which are one centimeter appart):
You assume that the given graph is 3-colorable and divide the graph into two parts. The inner triangle alone can be colored with 3 different colors, as well as the regular hexagon together with its midpoint. Now consider the options to color the hexagon: You need one color for the midpoint, and the other two colors alternating on the edge to color this part of the graph. Considering the options for the inner triangle, you see, that you need one color for each vertex.
When you connect the two graphs in the same way as in the given graph, you can "choose" between one of the three colors for the vertecies on the hexagon, since these three points must have the same color. But each of these vertecies connect to another vertex of the inner triangle, which already uses all the colors. So there will always be one edge with same colored vertecies. This is a contradiction to the assumption that the graph is 3-colorable. And well, the inner triangle needs at least three colors, so less than three wont work out. Therefore you need at least four colors.
Greetings from Germany :)
EDIT: format and "vertecies" to "points"

[fyermind]

This is an awesome video! I love the how you managed to touch on so many different problems and really describe their similarities rather than trying to dive too deeply into their intricacies. I left this video wanting to learn more, and to try to solve the University Course Catalog problem: why all the courses I want are either at the same time or not offered this semester.

[juanborjas]

The content keeps getting better and nerdier. Keep up the good work of making math interesting and fun, and I hope you get a lot more of subscribers.