Fillings of skew shapes avoiding diagonal patterns
A skew shape is the difference of two top-left justified Ferrers shapes sharing the same top-left corner. We study integer fillings of skew shapes. As our first main result, we show that for a specific hereditary class of skew shapes, which we call D-free shapes, the fillings that avoid a north-east...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6171/pdf |
| _version_ | 1797270028353011712 |
|---|---|
| author | Vít Jelínek Mark Karpilovskij |
| author_facet | Vít Jelínek Mark Karpilovskij |
| author_sort | Vít Jelínek |
| collection | DOAJ |
| description | A skew shape is the difference of two top-left justified Ferrers shapes
sharing the same top-left corner. We study integer fillings of skew shapes. As
our first main result, we show that for a specific hereditary class of skew
shapes, which we call D-free shapes, the fillings that avoid a north-east chain
of size $k$ are in bijection with fillings that avoid a south-east chain of the
same size. Since Ferrers shapes are a subclass of D-free shapes, this result
can be seen as a generalization of previous analogous results for Ferrers
shapes.
As our second main result, we construct a bijection between 01-fillings of an
arbitrary skew shape that avoid a south-east chain of size 2, and the
01-fillings of the same shape that simultaneously avoid a north-east chain of
size 2 and a particular non-square subfilling. This generalizes a previous
result for transversal fillings. |
| first_indexed | 2024-03-11T21:32:04Z |
| format | Article |
| id | doaj.art-b54416bb60924cf0906e10a1a070c677 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:45Z |
| publishDate | 2021-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b54416bb60924cf0906e10a1a070c6772024-03-07T15:41:55ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-06-01vol. 22 no. 2, Permutation...Special issues10.46298/dmtcs.61716171Fillings of skew shapes avoiding diagonal patternsVít Jelínekhttps://orcid.org/0000-0003-4831-4079Mark KarpilovskijA skew shape is the difference of two top-left justified Ferrers shapes sharing the same top-left corner. We study integer fillings of skew shapes. As our first main result, we show that for a specific hereditary class of skew shapes, which we call D-free shapes, the fillings that avoid a north-east chain of size $k$ are in bijection with fillings that avoid a south-east chain of the same size. Since Ferrers shapes are a subclass of D-free shapes, this result can be seen as a generalization of previous analogous results for Ferrers shapes. As our second main result, we construct a bijection between 01-fillings of an arbitrary skew shape that avoid a south-east chain of size 2, and the 01-fillings of the same shape that simultaneously avoid a north-east chain of size 2 and a particular non-square subfilling. This generalizes a previous result for transversal fillings.https://dmtcs.episciences.org/6171/pdfmathematics - combinatoricscomputer science - discrete mathematics05a05 (primary), 05b50 (secondary) |
| spellingShingle | Vít Jelínek Mark Karpilovskij Fillings of skew shapes avoiding diagonal patterns Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics 05a05 (primary), 05b50 (secondary) |
| title | Fillings of skew shapes avoiding diagonal patterns |
| title_full | Fillings of skew shapes avoiding diagonal patterns |
| title_fullStr | Fillings of skew shapes avoiding diagonal patterns |
| title_full_unstemmed | Fillings of skew shapes avoiding diagonal patterns |
| title_short | Fillings of skew shapes avoiding diagonal patterns |
| title_sort | fillings of skew shapes avoiding diagonal patterns |
| topic | mathematics - combinatorics computer science - discrete mathematics 05a05 (primary), 05b50 (secondary) |
| url | https://dmtcs.episciences.org/6171/pdf |
| work_keys_str_mv | AT vitjelinek fillingsofskewshapesavoidingdiagonalpatterns AT markkarpilovskij fillingsofskewshapesavoidingdiagonalpatterns |