Lei Cao

Enumerating forcing and strongly forcing (0,1)-matrices

Let $Q$ be a nonzero $s\times t$ $(0,1)$-pattern, and let $m\ge s$ and $n\ge t$. An $m\times n$ matrix is strongly $Q$-forcing if every $1$-entry belongs to an $s\times t$ submatrix equal to $Q$. Let $F^{*}(m,n,Q)$ count these matrices. Put $H=m-s+1$ and $W=n-t+1$. We prove \[ F^{*}(m,n,Q)\ge 2^{HW}. \] Writing $r$ and...