Rutgers Discrete Mathematics Seminar

Title: Tiling with Triangles is Hard

Speaker: Jed Yang, U. Minnesota

Date: Monday, November 16, 2015 2:00 pm

Location: Hill center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ


Knutson, Tao, and Woodward introduced puzzle pieces consisting of two triangles and a rhombus (with edge labels). They proved that tilings by these puzzle pieces (allowing rotations) of triangular regions (with edge labels) are counted by Littlewood-Richardson coefficients, which are numbers that appear naturally in many contexts.

Together with the saturation conjecture, proved by Knutson and Tao, this means, in particular, that tileability of triangular regions by puzzle pieces can be decided in polynomial time. In this talk, we will discuss the problem of tiling arbitrary regions with these puzzle pieces. Regardless of whether reflections are allowed when tiling, the problem is NP-complete. Joint work with Igor Pak.