The list that cannot run out

A Latin square is an n × n array of n symbols with no repeat in any row or column. It is one of the oldest objects in combinatorics, and the fact that one exists is easy. Write the numbers in order along the top row and shift them one place for each row below. That construction uses the fact that all cells draw on the same n symbols, and it says nothing if they do not.

In 1979 Jeff Dinitz asked what happens when each cell gets its own list. Fix any list of n symbols for each cell, with the lists differing from cell to cell in any way at all, and try to pick one symbol from each cell’s list so that no row or column has a repeat. Is that always possible? With the same list everywhere it is the Latin square, and differing lists look as if they should only make it easier, because two cells with different lists are less likely to want the same symbol. Yet there are comparable colouring problems on other graphs where differing lists do make things harder, and nobody could make either intuition into a proof. The question stood for fifteen years and collected partial results, each using cleverer tools.

Fred Galvin settled it in 1994, in a paper of six pages published the following year whose central argument takes about one. It does not use any of the tools built for the problem. It uses a stable set. The solution concept from the book of 1944, found on a sub-table by deferred acceptance, is applied again and again, once per colour, and a one-line count does the rest. This essay runs the proof, step by step, on squares small enough to see.

Why doing it cell by cell fails #

The natural algorithm is to read the cells in order and give each cell the first colour in its list that does not clash with its row or its column so far. Cells near the end of the reading have many neighbours already coloured, and a list of n can be entirely blocked by them.

In the figure the first five cells are coloured without any trouble, each taking the lowest free entry in its list. The sixth cell, at the end of the second row, has the list 1, 2, 4. Its row already uses 2 and 1, and its column has used 4, so it is stuck. There are only three cells in the same row and column that have been coloured by that point, and they have used three different colours, and those three happen to be its whole list. A cell can see up to 2(n − 1) neighbours altogether and has only n entries in its list, so this kind of blockage is always possible when the order is arbitrary. And nothing stops it from happening. Whether a better order always exists, and how anyone would find it, is the question itself.

The trials later in this essay put a rough number on it. On random lists at three by three from four colours, reading in order succeeds about 65 per cent of the time, and on four by four from five colours about 51 per cent. The failure rate is high enough for it to be a matter of luck, and it does not disappear on larger squares.

An ordinary colouring, used as preferences #

Galvin’s first step uses the one thing that is available without any cleverness: an ordinary Latin square, with no connection to the lists at all. Take the cyclic one, and read its entries as preferences. Within a row, a cell moves to any cell with a larger entry. Within a column, a cell moves to any cell with a smaller entry. That defines a move graph on the cells of the square, the same shape as the graph on pairs in a marriage table, with rows as men and columns as women, and each person’s list given by the Latin square.

Now the count on which everything rests. A cell holding entry e has exactly n − e larger entries in its row, since every symbol appears once in each row. Likewise it has exactly e − 1 smaller entries in its column, because each symbol appears once in each column. The two add up to n − 1, for every cell, whatever e is. The figure shows a cell at one extreme, where all its moves are in the column. A cell in the middle has some of each.

That number is the whole reason for choosing a Latin square. A preference built any other way would give some cells many more moves than others. What the Latin property provides is a uniform budget: no cell can be “moved past” more than n − 1 times. Since the lists have n entries, each cell has one more entry than it has moves. That single unit of slack is the entire proof.

One colour at a time #

Now the peeling. Pick any colour. Look at all the uncoloured cells whose lists contain it. Those cells form a sub-table of the square, with the preferences inherited from the Latin square, and on that sub-table the deferred acceptance algorithm finds a stable set, for the reason the last essay gave. A cell’s list is a strict order along its row and a strict order down its column. So there is no need for a search. Rows propose in order of the entries they prefer, and columns hold on to the best so far.

The first panel can be followed by hand. Six uncoloured cells have this colour in their lists. Three rows are in play, and each row wants its cell with the largest Latin entry among those six: the first row its 2 over its 1, the second its 2 over its 1, the third its 2 over its 1. Those three cells lie in three different columns, so all three are held at once and the run ends without a single refusal. The three cells passed over each have a larger entry in their own row, now coloured. The next panel starts from what is left, with the next colour, and its wanting cells fall differently. The run there again produces one cell per row wherever a row has a cell left that wants the colour, and a column resolves any clash by keeping its smaller entry.

Give the stable set that colour, and remove those cells. They do not clash: the stable set has no two cells in a line, because any two cells in a line have a move between them. Each shaded cell that was not chosen now has the colour struck from its list, since a neighbour along the line now has that colour. So far this is what any careful colouring would do. What is special is what the stable set guarantees about those passed-over cells. By the absorbing condition, each has a move into the stable set, which is to say, one of the cells it could move to has just been coloured and removed.

So the bookkeeping is exact. A cell not wanting this colour is unchanged. A cell chosen is finished. And a cell passed over has lost one entry from its list and at least one move, both at the same moment. Therefore the quantity list length minus remaining moves can never go down. It began at one for every cell, because n − (n − 1) = 1. So it stays at one or higher for every cell, always, which means every uncoloured cell always has at least one colour left in its list, however little else remains of it.

The table reports that count on the square just coloured. At the start every open cell has a margin of exactly one. Passing through the colours, the margin sometimes rises, when a cell loses a move without losing a list entry because another cell on its line was coloured by a colour it did not want. It never falls. When the colours are used up every cell has been coloured, since a cell can leave only by being coloured, and an uncoloured cell always has an unprocessed colour left to try. Each colour class has no repeat in a line, so the result is a valid filling from the lists.

That is the theorem. The order of the colours does not matter, and neither does the choice of Latin square. A stable set is available at each step because each sub-table inherits the clique structure of the table, and this is why marriage rather than parity was the theorem required. Richardson’s condition is no use here, because the graph on a Latin square has odd cycles of its own. The condition that does survive taking sub-tables is that each line’s preference remains a strict order. A family closed under taking parts, with a stable set in each, is exactly what a repeated peeling needs. That is the same peeling that builds a Grundy labelling from stable sets, in a different coat: there, the first stable set was labelled zero and the next one, of what remained, was labelled one. Here the first stable set gets the first colour, and the next, on the cells remaining, gets the second.

The surprise: where the connection came from #

The connection here is genuinely strange, and it is worth setting out what each piece was originally for. The two conditions on a set were written to describe a consistent social arrangement among coalition partners. Gale and Shapley’s algorithm was published as a way of allocating college places and of pairing people off. The lemma tying stable sets to list colouring, that a list longer than a vertex’s out-degree suffices if every part of the graph has a stable set, is credited to Bondy, Boppana and Siegel, and it was in print in a 1992 paper by Alon and Tarsi that treats list colouring by a method using graph orientations. Galvin’s addition was to notice two further things. First, that a Latin square gives the required out-degree. Second, that the existence of stable sets on the sub-graphs involved had already been settled in 1962. Neither of those is a hard theorem in itself, and that combination is why the proof takes a page.

The proof’s main tool, a stable set, is what a game theorist would recognise as a set of lost positions. And there is a reading of the whole proof as play, though not an especially natural one. For each colour, cells are in a token game on the sub-table and the lost positions (or their generalisation in a loopy game, which is what a stable set is) take that colour. Everything that could have moved into one of those has lost an option. Stated like that, the argument could be read as peeling the zero-positions off a game, as the Sprague–Grundy theory does, with lists playing the role of the remaining labels.

What each piece contributes, taken away in turn #

A proof this short invites a check of which parts are necessary, and each can be removed in thought.

Remove the Latin square, and use any other preference on rows and columns. A cell can then have up to 2(n − 1) moves, and a list of n can be exhausted long before they are. Take a preference where a row and a column agree in ranking one cell last in both. That cell has every neighbour as a move, the count fails for it, and there is no margin at all. So the uniform count is not an elegance. It is the condition that makes n colours enough rather than 2n − 1, which is what plain greedy colouring already gives.

Remove the stable set, and use any set of non-clashing cells among those wanting the colour, such as a maximum one. A passed-over cell loses a list entry, but it need not lose a move, because nothing says it had a move into the chosen set. The margin can then fall, and when it reaches zero with a move still outstanding, the proof has nothing to say. This is the essential point. A large set is what intuition asks for at this step. A stable set need not be the largest, and what it has instead is that it reaches everything it passes over. The proof requires that reach and has no use for the size.

Remove the two-sided structure, and the existence of the stable set at each step goes, which is the roommate problem from the last essay.

How it compares with the trials #

Trials cannot prove a theorem, and this one needs no help. They do serve another purpose, which is to calibrate the alternative and to check that the program does what the proof says.

Every one of the 2,000 squares at each setting is coloured correctly by the peeling, each result checked independently for proper use of the list and for repeats. Reading in order succeeds on 65 per cent of the three-by-three lists from four colours, 87 per cent from six, and on 51 per cent of the four-by-four lists from five colours, and on 89 per cent from eight. That second figure does what intuition says: with more colours in play, lists overlap less, and collisions are rarer, so even a careless method does better. But the failure never goes away. At six by six from nine colours the careless method manages 66 per cent.

The tightest case for the lists themselves is when they are all the same. Reading in order on an n × n square with one shared list of n symbols would have to discover a Latin square by accident. So the differing lists are, in the end, no harder than the shared list, which was the original intuition. It was right, and no intuition about differing lists was any part of the proof.

The convention named #

The lists are of size exactly n. With n − 1 colours in all, a row would run out, so n is the fewest that can possibly suffice, and the theorem says it does. Since a square’s cells form the edges of a complete bipartite graph, with rows on one side and columns on the other, what has been proved is that the edges of $K_{n,n}$ can be coloured from any lists of size n. That is the special case of a theorem for all bipartite multigraphs in Galvin’s paper, with n replaced by the largest degree. The same statement for graphs that are not bipartite is the list colouring conjecture, and it remains open. The two-sided structure is doing the same job it did in the marriage table, and the roommate triangle is the reason it cannot simply be dropped.

In the trials, lists are drawn uniformly from a palette, and the palette’s size matters to the right-hand column of the table and not at all to the proof. A hostile choice of lists is what the theorem covers; a uniform draw is only what the trials happen to try.

A further convention sits inside the phrase stable set, and the proof depends on it. It needs a stable set among the cells wanting the colour, on the graph restricted to those cells. A stable set of the whole square would not do: a cell outside the wanting group cannot take this colour, however much it might be preferred. The restriction is what makes the sub-table a new instance each time, and it is why the existence result has to apply to every part of the table rather than to the table once. That requirement has a name in the graph literature, kernel-perfect, and it is the same property that a Grundy labelling needed on a graph with no odd cycle. The Latin square itself is never coloured and appears in the answer nowhere. It supplies an order and then has no further role.

What the trials cannot show #

That this is the only route. Everything drawn here follows one argument, and nothing here rules out another. What the figures establish is that this one works and how little it uses.

Anything about non-bipartite graphs. The peeling needs a stable set on each sub-graph and a uniform budget of out-degree. On the line graph of a general graph the first of those fails, for the reason four roommates demonstrated, and the second has no analogue with a Latin square. The conjecture for general graphs has resisted a long time, and the failure of this method is no evidence about its truth.

Whether a random colouring from lists is usually easy. The right-hand column of the table is a single naive rule, not the best simple rule. A careless method with a smarter order, or backtracking of a few steps, might succeed much more often. No measurement here says how hard it is on average to find a colouring without the theorem.

Still open: when the question is the existence of the set itself #

A stable set has now done two kinds of work. In a game it says who has lost, and in a colouring argument it is a step used many times. Every time, though, its existence has been known in advance, because of a theorem: no cycle, or no odd cycle, or clean orders along every line. Each family came with an easy way to find it. It remains to ask about the general case, an arbitrary graph with no structure at all. Whether a stable set exists there is a plain yes or no, and the definition is two conditions a child could check. The answer is that this is as hard as anything in NP, although outcome labelling on the same graph is as easy as it gets. It was among the first results of its kind, published in 1973, and the reduction that proves it uses nothing but the triangle and the two-way pair.