Flag-Shaped Blockers of 123-Avoiding Permutation Matrices

Abstract

A blocker of $123$-avoiding permutation matrices refers to the set of zeros contained within an $n\times n$ $123$-forcing matrix. Recently, Brualdi and Cao provided a characterization of all minimal blockers, which are blockers with a cardinality of $n$. Building upon their work, a new type of blocker, flag-shaped blockers, which can be seen as a generalization of the $L$-shaped blockers defined by Brualdi and Cao, are introduced. It is demonstrated that all flag-shaped blockers are minimum blockers. The possible cardinalities of flag-shaped blockers are also determined, and the dimensions of subpolytopes that are defined by flag-shaped blockers are examined.

19 pages