Tiling simply connected regions by rectangles

Combinatorics Seminar
Friday, November 2, 2012 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Math, UCLA

Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles?  In general this decision problem is undecidable for infinite regions and NP-complete for finite regions.  In the case of simply connected finite regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes.  We construct a fixed set of rectangular tiles whose tileability problem is NP-complete even for simply connected regions.This is joint work with Igor Pak.