More on graph theory: List colorings.

For those of my readers who know some combinatorics and have seen graphs before, I'd like to say a little bit more on one topic from graph theory that I've been learning about. If you aren't so interested in math and don't care about graphs, then you can skip ahead and read the last two paragraphs. The topic I want to tell you about is list coloring, which is a generalization of coloring a graph.

As you may know, a graph's vertices can be colored such that no two adjacent vertices are the same color. Now let's restrict how we can color the graph: given a graph G, at each vertex v of G, put a list of colors L(v). We now properly color G such that each vertex v has a color from its list L(v); this is called a list coloring of G.

The chromatic number χ(G) is the smallest number of colors with which G can be properly colored, without list restrictions. We can define a similar notion for list colorings, considering the size of each color list. The list-chromatic number, or choice number, is the smallest r such that G can be list-colored for every possible system of lists of length r. We denote this as ch(G). Note that this number gives the length of each list, not necessarily the number of colors we use; this confused me at first.

The choice number and chromatic number are related: for any graph G,  χ(G) ≤ ch(G). Do we ever have χ(G) = ch(G)? In my graph theory class we learned that, if G is the line graph of a bipartite graph, then χ(G) = ch(G). (By the way, the proof of this theorem uses the stable-marriage existence theorem!)

This theorem is applicable to an important combinatorial problem: Given an n-by-n matrix where each position carries a list of length n, is it possible to fill each position with an item from its list in such a way that each row and each column has n distinct items? If we have {1, …, n} at each position, then it is possible; such a matrix is called a Latin square. But can this be done for any system of lists?

This problem can be solved by constructing a graph with the entries of the matrix as vertices and drawing edges between two vertices if they are in the same row or column of the matrix. Then the problem becomes: is χ(G) = ch(G) for this graph? The graph is actually the line graph of the complete bipartite graph. So, by the theorem I mentioned earlier, there is a list coloring; the answer to our question is yes, we can always select items for the matrix, no matter what the lists are.

One problem on my graph theory homework this week was to prove that, if all of the positions of the matrix have length-n lists except one list which is length-(n/2), then a proper choice is not always possible. This means that we have to construct such a system of lists on the n-by-n matrix, such that it is impossible to choose n distinct items in each row and column.

This is perhaps the hardest problem that I had so far been given in graph theory, and I didn't really know where to start on this one; fortunately, neither did my two roommates. So last night, we sat down together for a few hours and tried to construct the list-system. We made lots of sketches and guesses, most of which didn't work. But over time, we got to know the problem and understand parts of it, and eventually one of us had a breakthrough. One of my roommates found a list system on the 4-by-4 matrix that worked; then the other roommate found a way to prove why it worked (using the pigeonhole principle!); and then I was able to extend the construction and the proof to the general n-by-n case. We had solved the problem—but more importantly, we had fun with it. It was exhilarating to try different approaches and finally find one that worked, and I was really happy that I had friends that shared this feeling with me.

That's what I love most about the BSM program: I always have math to do, I always have people to do the math with if I want, and we always have tons of fun doing the math. I feel like I'm swimming in math, and every day I am even more sure that this is what I want to be doing for the rest of my life.