Tiling simply connected regions by rectangles

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

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.