Graduate Seminar

Brendan Sullivan
Carnegie Mellon University
Title: How Many Ways Can We Tile a Rectangular Chessboard With Dominos? : Counting Tilings With Permanents and Determinants

Abstract: Consider an m by n rectangular chessboard. Suppose we want to tile this board with dominoes, where a domino is a 2 by 1 rectangle, and a tiling is a way to place several dominoes on the board so that all of its squares are covered but no dominos overlap or lie partially off the board. Is such a tiling possible? If so, how many are there? The first question is simple, yet the second question is quite difficult! We will answer it by reformulating the problem in terms of perfect matchings in bipartite graphs. Counting these matchings will be achieved efficiently by finding a particularly helpful matrix that describes the edges in a matching, and then finding the determinant of that matrix. (Remarkably, there is even a closed-form solution!)

(Note: This talk is adapted from a chapter in Jiri Matousek's book "Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra".)

Date: Thursday, February 21, 2013
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Brian Kell