Hard Tiling Problems with Triangles and Rhombi

Wednesday, November 12, 2014 - 10:30am - 10:55am
Keller 3-180
Jed Yang (University of Minnesota, Twin Cities)
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.
These numbers appear naturally in many contexts,
intersection of Schubert varieties,
multiplication of Schur functions,
and tensor products of irreducible representations of general linear groups.

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.)
MSC Code: