Enumeration of pattern-avoiding (0,1)-matrices and their symmetry classes

2025/10/30 by Eu, Sen-Peng, Lee, Yi-Lin
#05A05 #05A15 #05A19 #05B20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.26168

Abstract

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 number. 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.

Citations

• Diagonally symmetric alternating sign matrices
• Plane partitions with bounded size of parts and biorthogonal polynomials
• Four factorization formulas for plane partitions
• Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole
• k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams
• Crossings and Nestings of Matchings and Partitions
• Symmetry Classes of Alternating Sign Matrices
• Advanced Determinant Calculus

Related

• Pattern-Avoiding (0,1)-Matrices
• Forbidden Configurations and Boundary Cases
• Enumeration of permutations avoiding a triple of 4-letter patterns is all done
• Generating and enumerating 321-avoiding and skew-merged simple permutations
• On the structure of matrices avoiding interval-minor patterns