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 :
Document type :
Conference papers
Domain :

Cited literature [9 references]

https://hal.inria.fr/hal-01185144
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 19, 2015 - 11:41:32 AM
Last modification on : Wednesday, June 26, 2019 - 2:48:03 PM
Long-term archiving on: : Friday, November 20, 2015 - 10:27:36 AM

File

dmAJ0158.pdf
Publisher files allowed on an open archive

Citation

Alexey Spiridonov. Pattern-Avoidance in Binary Fillings of Grid Shapes (short version). 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.677-690, ⟨10.46298/dmtcs.3610⟩. ⟨hal-01185144⟩

Record views