A polyomino is a configuration of unit squares in the plane. Squares are joined along their edges and the configuration may not contain holes. In this talk we consider two topics on polyominoes: Gray codes for polyominoes and Venn diagrams of minimum area constructed from polyominoes.
The Gray codes that we consider are for column-convex polyominoes, which are those whose intersections with vertical lines are connected. In the code successive polyominoes differ by the movement of one square. These Gray codes have interesting connections with certain classical distributive lattices studied in algebraic combinatorics, particularly with regard to questions of rank unimodality.
A Venn diagram is a collection of n simple closed curves (e.g., the outlines of polyominoes) whose 2^n possible interior intersections are all non-empty and connected. A Venn diagram whose curves are polyominoes has minimum area if every intersection of curve interiors is a unit square, with the exception of the empty set. Previously they were known to exist only for n <= 4 polyomino curves; we give examples showing that they exist up to n=7 polyomino curves, and give an approximation algorithm to construct them with close to minimum area for all n.
This is joint research with my graduate student Stirling Chow.