Pattern-avoidance in binary fillings of grid shapes
Alexey Spiridonov · DSpace@MIT (Massachusetts Institute of Technology) · 2009
A grid shape is a set of boxes chosen from a square grid; any Young diagram is an example. This paper considers a notion of pattern-avoidance for 0-1 fillings of grid shapes, which generalizes permutation pattern-avoidance. A filling avoids some patterns if none of its sub-shapes equal any of the patterns. We focus on patterns that are pairs of 2 × 2 fillings. For some shapes, fillings that avoid specific 2 × 2 pairs are in bijection with totally nonnegative Grassmann cells, or with acyclic orientations of bipartite graphs. We prove a number of results analogous to Wilf-equivalence for these objects — that is, we show that for certain classes of shapes, some pattern-avoiding fillings are equinumerous with others.