Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3610/pdf |
| _version_ | 1797270399146262528 |
|---|---|
| author | Alexey Spiridonov |
| author_facet | Alexey Spiridonov |
| author_sort | Alexey Spiridonov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:39Z |
| format | Article |
| id | doaj.art-18e2503823ab42a1aa99aac7c1f27a8c |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:39Z |
| publishDate | 2008-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-18e2503823ab42a1aa99aac7c1f27a8c2024-03-07T14:38:06ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502008-01-01DMTCS Proceedings vol. AJ,...Proceedings10.46298/dmtcs.36103610Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)Alexey Spiridonov0Department of Mathematics [MIT]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.https://dmtcs.episciences.org/3610/pdfpattern-avoidancefillinggrid shapele-diagramacyclic orientationyoung diagram[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Alexey Spiridonov Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) Discrete Mathematics & Theoretical Computer Science 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] |
| title | Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) |
| title_full | Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) |
| title_fullStr | Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) |
| title_full_unstemmed | Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) |
| title_short | Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) |
| title_sort | pattern avoidance in binary fillings of grid shapes short version |
| topic | 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] |
| url | https://dmtcs.episciences.org/3610/pdf |
| work_keys_str_mv | AT alexeyspiridonov patternavoidanceinbinaryfillingsofgridshapesshortversion |