Graduate Programs
Graduate Home
Ph D Programs
Masters Degree
Ph D Program Requirements
Course Descriptions
Current Courses
Admissions
Current Graduate Students
Graduate Student Seminar
SIAM Chapter Seminar
Recent Graduates
Incoming Students

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 closedform solution!)(Note: This talk is adapted from a chapter in Jiri Matousek's book "Thirtythree 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 