Enumeration of pattern-avoiding $(0,1)$-matrices and their symmetry classes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910190043922432 |
|---|---|
| author | Eu, Sen-Peng Lee, Yi-Lin |
| author_facet | Eu, Sen-Peng Lee, Yi-Lin |
| contents | Recently, Brualdi and Cao studied $I_k$-avoiding $(0,1)$-matrices by decomposing them into zigzag paths and proved that the maximum number of $1$'s in such a matrix is given by an exact formula. We further study the structure of maximal $I_k$-avoiding $(0,1)$-matrices (IAMs) by interpreting them as families of non-intersecting lattice paths on the square lattice. Using this perspective, we establish a bijection showing that IAMs are equinumerous with plane partitions of a certain size. Moreover, we classify all ten symmetry classes of IAMs under the action of the dihedral group of order $8$ and show that the enumeration formulas for these classes are given by simple product formulas. Extending this approach to skew shapes, we derive a conceptual formula for enumerating maximal $I_k$-avoiding $(0,1)$-fillings of skew shapes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26168 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enumeration of pattern-avoiding $(0,1)$-matrices and their symmetry classes Eu, Sen-Peng Lee, Yi-Lin Combinatorics 05A05, 05A15, 05A19, 05B20 Recently, Brualdi and Cao studied $I_k$-avoiding $(0,1)$-matrices by decomposing them into zigzag paths and proved that the maximum number of $1$'s in such a matrix is given by an exact formula. We further study the structure of maximal $I_k$-avoiding $(0,1)$-matrices (IAMs) by interpreting them as families of non-intersecting lattice paths on the square lattice. Using this perspective, we establish a bijection showing that IAMs are equinumerous with plane partitions of a certain size. Moreover, we classify all ten symmetry classes of IAMs under the action of the dihedral group of order $8$ and show that the enumeration formulas for these classes are given by simple product formulas. Extending this approach to skew shapes, we derive a conceptual formula for enumerating maximal $I_k$-avoiding $(0,1)$-fillings of skew shapes. |
| title | Enumeration of pattern-avoiding $(0,1)$-matrices and their symmetry classes |
| topic | Combinatorics 05A05, 05A15, 05A19, 05B20 |
| url | https://arxiv.org/abs/2510.26168 |