Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)
Abstrak
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.
Topik & Kata Kunci
Penulis (1)
Alexey Spiridonov
Akses Cepat
- Tahun Terbit
- 2008
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.3610
- Akses
- Open Access ✓