Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)

Abstract

A $\textit{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 $\textit{pairs}$ of $2 \times 2$ fillings. For some shapes, fillings that avoid specific $2 \times 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.

Keywords

• pattern-avoidance
• filling
• grid shape
• le-diagram
• acyclic orientation
• young diagram
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]