UVictoria Discrete Math Seminar: Joy Cooper

In how many ways can an m x n chessboard be tiled using 2 x 1 tiles? The solution is given by the number of perfect matchings in a related graph. Although computationally difficult in general, in this circumstance we are able to efficiently count these matchings.

Originally shown by P.W Kastelyn in 1961, I shall present an adapted solution given by Jiří Matoušek in his book "Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra" published in 2010.