What's the most useful and surprisingly difficult math problem that sounds like an activity for children?

Probably graph colorings.

Let's say you have a graph, which is just a bunch of vertices connected by edges.

A coloring of the graph is a way to color all of the vertices so that no two vertices which are connected by an edge are the same color, like this.

A k-coloring, where k is some number, is a coloring of the graph that only uses k different colors.

For example, this is a 3-coloring.

There's 3 colors on the vertices, and adjacent vertices have different colors.

This is a 4-coloring.

Notice that we can only do this on graphs without loops.

If there is an edge which connects a vertex to itself, a loop, then it's impossible to color it, so we'll pretty much ignore graphs with loops.

So if I give you a specific graph, like this one, and ask if it's possible to k-color it for some specific number k, how do you figure it out?

What do you do?

This might sound kind of silly, like an exercise you'd give to a child to keep them entertained on a road trip, but graph colorings are actually highly applicable mathematics.

Don't believe me?

Sudoku is actually solving for a 9-coloring.

Sudoku is a game where you fill out a 9 by 9 grid with the numbers 1 through 9 so that each number only appears once in each column, once in each row, and once within each of the 9 3 by 3 blocks.

Let's make it into a graph.

Each of the 81 squares is a vertex.

Connect every vertex that's in the same row by an edge, and connect every vertex that's in the same column.

We're only showing it for one row and one column because the graph would be to visually complicated if we put them all in.

Then we connect all the vertices which are in the same 3 by 3 square.

Again, we're only showing it on 1 of the 9 blocks.

If we showed all the edges, there would be 810 of them.

Now, a 9-coloring of this graph is the same as a Sudoku.

The edges encode which squares can not have the same color or number, as in the Sudoku case.

A Sudoku begins with a certain number of squares filled out, which is equivalent to saying that our graph is partially colored, and your task is to color the remaining vertices so that you end up with a 9-coloring.

Why is this useful?

Well, for one, it's just kind of cool that a popular game, Sudoku, is exactly the same as a difficult and well studied math question, graph colorings.

But also, graph colorings are a really well-studied branch of math, so you can apply that knowledge to Sudoku.

It's not exactly going to help you solve Sudoku, because figuring out how to properly 9-color a graph is exactly as hard as solving a Sudoku puzzle, but it can provide you with new tools and perspectives.

In the description, we've linked to a paper with more information.

Probably the most famous example of a coloring is the 4-color theorem.

It says that you can color any map using 4 colors so that no two countries, or states, or regions which share a border are the same color.

If they only touch at a corner, like New Mexico and Utah, then they can be the same color.

The regions in our map need to be contiguous, so states like Michigan or Hawaii, which are broken into pieces, don't work.

Some maps require 4 colors to be properly colored, like this one.

It can't be colored using 3 But all maps can be colored using 4 colors.

4 is the minimum number of required colors.

Let's ask the analogous question for any graph.

Given a graph, what's the smallest k such that you can k-color the graph?

In other words, what's the smallest number of colors you need to color each vertex so that no two vertices which are connected by an edge are the same color.

The number that is the answer to this question is called the chromatic number of the graph.

For example, the chromatic number of this graph is 2.

In general, any cycle of even length can be colored by 2 colors, but a cycle of odd length, like this, requires three colors.

It simply can't be colored with only 2 colors, so it has chromatic number 3.

This graph has chromatic number 6.

There are six vertices, and every vertex is connected to every other one, so they all need to be different colors.

In general, it's hard to find the chromatic number of a graph.

If you want to write an algorithm so that you could hand in any graph and it would hand you back the chromatic number, that algorithm would probably take a long time.

But finding the chromatic number of a graph can be applied to lots of common scheduling problems, like arranging committee meetings where several people are on multiple committees.

We're going to use it to solve the Wolverine problem.

At one time, Wolverine was on four different superhero teams and he needed to balance his time.

A super team can't efficiently save the world if they're constantly waiting around for their teammates to show.

But, using graph colorings, we can figure out a way that Wolverine and the other superheroes can best serve on multiple teams.

Here's the set-up.

7 omega-level super villains are attacking the planet on the same day.

Dr. Doom, the Dread Dormammu, Kang, Ultron, Magneto, Apocalypse, and Thanos.

We have 7 teams of superheroes.

The Fantastic Four, The Defenders, The Avengers Unity Squad, The New Avengers, the X-Men, X-Force, and Guardians of the Galaxy.

Here's their rosters.

These teams need to stop these super villains today in order to save the world.

The problem we have is that these teams are only effective when their entire roster is available, but many of their members are serving double, or in wolverine's case, quadruple duty.

So we need to figure out the most efficient way to schedule when these teams can attack.

How do we minimize their wait time so all the super villains can be stopped as quickly as possible?

Create a graph where each node represents 1 team.

If there's a superhero which is on 2 teams, create an edge connecting those teams.

For example, Wolverine is on New Avengers, Avengers Unity Squad, the X-Men, and X-Force, so there are edges that connect each of these teams.

Even though X-Men and X-Force share 3 team members, we just connect them by 1 edge.

Guardians of the Galaxy doesn't share any members with any of the other teams, so it's not connected by any edges.

Now, we want to find a coloring of the graph.

That is, we want to find a way to color the vertices so that any two vertices connected by an edge are different colors.

The color of a vertex corresponds to what time the team goes to fight their villain.

And since we want to fight them as quickly as possible, we want to use the least number of colors.

Here's an example using 4 colors.

Since Wolverine is on 4 teams, those four teams have to be different colors.

Besides making sure that Wolverine's 4 teams are different colors, we have options for how to color the other vertices.

The Guardians of the Galaxy doesn't share any team members, so they can be any of the four colors.

The coloring could look like this instead.

Since it requires at least 4 colors to properly color, we say this graph has chromatic number 4.

How does this graph coloring give us a schedule?

Well, all the teams that are 1 color can fight their villain at the same time.

So here's the schedule.

All the blue teams go first, then all the red, then all the green, and then all the purple.

Since the graph has chromatic number 4, it will take 4 rounds of fighting to defeat all the villains.

There's no way all the teams can go out in less than four rounds.

Just for fun, here's what the graph would look like if Wolverine got too busy and dropped out of the New Avengers and the X-Men.

It has chromatic number 2.

And while they're mixing up team members, Human Torch decides to join the Defenders.

Now the chromatic number is 3.

Even though each individual superhero is on no more than 2 teams.

You can imagine that with a lot more superheroes and a lot more teams, this scheduling problem gets complicated very fast.

OK. Back to the less heroic math.

Let's try to find the chromatic number of a particularly weird graph.

Here's the Hadwiger Nelson problem.

What's the smallest number of colors needed to color the plane-- flat, two dimensional space-- so that no 2 points which are exactly 1 centimeter apart have the same color?

So anywhere I lay down a 1 centimeter long stick, the two ends of the stick should be in regions of different colors.

Here's an example of a 7-coloring which works.

The distance across each of these hexagons is just a little bit smaller than 1 centimeter.

If we color the plane with this repeating pattern of 7 colors, then any 1 centimeter line will be in 2 different hexagons of different colors.

How is this even a graph coloring?

Imagine every point on the plane, all infinitely many of the points, are the vertices of a graph.

Then, for any 2 points which are 1 centimeter away, connect the 2 vertices that represent them with an edge.

Now, the Hadwiger Nelson problem is asking about the chromatic number of that graph.

We know it must be 7 or smaller, since I showed you an example with 7 colors.

But maybe there are other shapes we can cover the plane with which require less colors so that every line of length 1 has its end points in 2 shapes of different colors.

This diagram proves that it takes at least 4 colors.

Why?

I'll leave it as a challenge to you to answer that question.

So the chromatic number is between 4 and 7.

It's either 4, 5, 6, or 7.

But mathematicians don't know which one.

Maybe you can figure it out.

What's your favorite graph coloring problem?

Let us know in the comments.

See you next time on infinite series.

Hey, guys.

Before I respond to comments about the Random Walks episode, I wanted to make a quick announcement.

From now on, we're going to be giving out a PBS t-shirt to one random commenter who correctly answers the challenge question.

So for this episode, make sure to tell us why it takes at least four colors to color the plane.

OK. On to random walk responses.

Ofir David said "How about some group theory?

Random walks coming from groups can model many phenomena.

For example, questions like how many shuffles do you need before a deck of cards is randomized."

He's referencing a famous result by Persi Diaconus, which says that you need to shuffle a deck of 52 cards 7 times in order to make sure it's all mixed up.

This is an example of a bigger phenomenon called cutoff, which would make a really cool future episode.

Birdie Blue gave us two great examples of applications of random walks.

The first is evolution, where genetic drift is represented by a random walk, and the second is climate change, where photons are performing a random walk bouncing off CO2 molecules.

Finally, TheAvenger and others mentioned that they'd like to know how these probabilities change as the dimensions go up.

In particular, why does it suddenly change from recurrent to transient between dimensions 2 and 3.

There are computations which show this using the variables fi and sn that we defined.

But, as far as I'm aware, there's not one great intuitive answer.

I've attached a few links with more information.

See you guys next week.