Algebra and Combinatorics Seminar

Date: October 12, 2012

Time: 3:00PM - 3:50PM

Location: MILN 317

Speaker: Jed Yang, UCLA

Title: Hard tiling problems with rectangular tiles

Abstract: 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. It is sometimes easier to tile simply connected regions using combinatorial group theory. Indeed, tiling simply connected finite regions by two rectangles can be solved in polynomial time. What about more rectangles? In this talk, we will describe a set of rectangular tiles whose tileability problem is NP-complete for simply connected regions.

Joint work with Igor Pak.