Galvin's Proof of Dinitz's Conjecture

An n × n Latin square is a grid with n rows and n columns such that each cell of the grid is filled with one number from the set {1,2,...n} and no number is repeated in any row or any column. For instance, any solved Sudoku puzzle is a 9 × 9 Latin square. In 1979, Jeff Dinitz proposed the existence of "generalized Latin squares", which became known as the Dinitz conjecture.

The Dinitiz conjecture states that given an n × n grid, a number m ≥ n, and for each cell of the grid an n-element subset of {1,2,...,m}, it is possible to fill each cell with one of those elements such that no number is repeated in any row or any column. In 1994, Fred Galvin proved Dinitz's conjecture. Doron Zeilberger wrote of Galvin's proof, "When I finished reading and digesting the proof, I kicked myself. I felt that I could have found it myself ... With the very generous help of Lady Hindsight, I will now describe how I (and you!) could have, and should have, found the very same proof ...".

And that's exactly what we will do in this talk!