(Still on my math streak.)

1994 had an exciting moment when Fred Galvin solved the 1979 Jeff Dinitz conjecture on list-coloring Latin squares.

Latin squares are a simple predecessor to puzzles such as Soduko. A Latin square is an n by n grid of the integers 0 through n-1 (called “colors”) such that no row or column has any repeated integers. For example, here is a 2 by 2 Latin square.

Latin squares have their uses in experimental design, and power a number of interesting puzzles and questions.

One of the great properties of Latin squares is: we know how to fill them in row by row. If the top r-rows of partially filled in table look like they come from a Latin square, we can fill in more rows to complete the square. We can’t get stuck!

In terms of our Latin square, if we started with the following partial fill-in.

We can fill in the missing entries to complete the square. This was proven by Marshall Hall in 1945. The proof technique uses important and beautiful ideas about distinct representatives (one of the core ideas of combinatorics). It tells us we can find rows to continue a partial fill in. Finding continuing rows involves computing matchings, but those algorithms are considered very well understood.

There are even many ways to fill in a Latin square all at once. For example assigning cell(i, j) = (i + j) % n is a nice solution.

In 1979 Jeff Dinitz considered a variation of the Latin square problem called list coloring. In our earlier problem each cell we filled in for our n by n Latin square could pick from the same set of “colors”: 0 through n-1. In list coloring each cell has its own list of allowed colors.

Consider the following list coloring example specification of sets we are allowed to pick from for each cell (the “lists”):

The question in general is: if all the lists are of at least size n, then is there at least one valid list coloring?

This list coloring Latin square specification does have a valid list coloring solution:

However, unlike the non-list coloring, we can get stuck with a seemingly harmless partial fill-in. Even picking 0 for the upper left corner ruins the problem, as we can’t extend that partial solution in into a full solution.

What happened is, the heterogeneous lists lost us a lot of the symmetries that had made the earlier problem “easy.”

Galvin’s breakthrough was to propose a viable filling-in technique. The write up is excellent (1), and there are already a number amazing appreciations of Galvin’s proof technique (1, 2, 3). However, let’s ignore the proofs and consider only the algorithm.

Galvin’s algorithm is the following. Starting with an empty partial fill-in.

• Pick a color we have not yet used in our partial fill-in.
• Select this color for a set of cells allowing this color in a pattern that forms a “graph kernel” or “stable marriage.”
• Continue the above steps until the coloring is complete.

And that is it. The partial fill in is done by colors instead of rows. We do still need to know what a graph kernel or stable marriage is, and how to identify such.

For the stable marriage we take a standard latin square and use it to annotate edges onto our proposed list colorable later square. We have some freedom here, and we have picked our edges so that each cell points to a lower value in its column and a higher value in its row. We illustrate this below (combining our original regular Latin square fill-in with our list coloring requirements):

The magic of this orientation is: each cell has exactly n-1 incoming and n-1 outgoing arrows. The genius of the orientation is: each cell is responsible only for picking a color that avoid conflicts with its outgoing arrows. Cells that point to a given cell take on the responsibility of avoiding conflicts with the cell. As each cell starts with n colors and n-1 outgoing arrow responsibilities, it looks like we have enough degrees of freedom to color. And this is in fact the case, as our coloring strategy maintains the invariant: each cell has at least one more color available than responsibilities.

The tool to maintain the above invariant is the stable marriage or graph kernel. In our case a stable marriage or a graph kernel is exactly a set of cells with a given color option such that:

• No two cells in our set point at each other.
• Any cell not in our set that has our given color in its options is pointing to one of our cells.

In our example the upper right and lower left cells are a stable marriage for the color 0. Neither of these cells directly points to each other, and the only other cell that is considering color zero points to one of our cells.

This gives us why the iterative coloring scheme works: when we assign a color the only cells we miss are ones that can not use the color! They lose one of their outgoing options, but they also lose cells they have to avoid. Each cell starts with n-1 outgoing arrows, and enough colors to avoid color conflicts with along all of these arrows. The iterative coloring process preserves the “enough available colors to avoid conflicts with remaining active outgoing arrows” invariant. And thus the coloring process is sound (but here we are getting into the proof!).

The Gale–Shapley stable marriage algorithm is itself an explainable and interesting algorithm (part of the Shapley and Roth the Nobel Prize in Economics of 2012).

It is a bit of a surprise that the Galvin proof is so constructive with an explicit efficient algorithm. List coloring and kernel style problems (graph independent sets, graph dominating sets) are commonly thought to not have efficient algorithms in general, as they are NP-hard. However, the instances we encounter here are all provably “easy.”

For fun I am sharing a Python implementation of Galvin’s algorithm here. It can solve problems such as our example as follows.

echo '[[{0, 2}, {0, 1}], [{0, 2}, {1, 2}]]' | python Galvin.py

# [[2, 0], [0, 1]]

This is a second valid solution to the original list coloring problem. [[2, 1], [0, 2]] is also a solution, so even this “restricted” 2 by 2 system has more solutions than the non-list coloring problem of the same size. This is the sense that we think list coloring is “easier” than non-list coloring. Remember: Dinitz’s conjecture was that the list coloring was always non-empty for color lists of size at least n. Showing list coloring has even more solutions than the standard Latin square coloring problem would be a much stronger result!

We share some counts and more examples here.

Hopefully this shares some of the joy of constructive (or algorithmic) combinatorics.

Categories: Mathematics Uncategorized

Tagged as: Combinatorics Latin Squares

jmount

Data Scientist and trainer at Win Vector LLC. One of the authors of Practical Data Science with R.