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

Abstract

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 $c$ for the numbers of nonzero rows and columns of $Q$, equality holds if and only if \[ (H=1\text{ or }r=1)\qquad\text{and}\qquad(W=1\text{ or }c=1). \] Thus the minimum over all nonzero $s\times t$ patterns is $2^{HW}$, attained exactly by singleton patterns when $H,W>1$, and every fixed nonzero pattern has square growth rate $1$. We also refine the count by weight. If $o(Q)$ is the number of $1$-entries of $Q$, then the number of strongly $Q$-forcing matrices at the minimum positive weight $o(Q)$ is $\binom{H+r-1}{r}\binom{W+c-1}{c}$; at every fixed density in $(0,1)$, the logarithmic growth rate is the binary entropy when $m$ and $n$ are comparable. For ordinary forcing, where every $s\times t$ submatrix contains the $1$-entries of $Q$ in their prescribed positions, let $F(m,n,Q)$ be the number of forcing matrices and let $\mathfrak m(m,n,Q)$ be their minimum weight. We prove \[ F(m,n,Q)=2^{mn-\mathfrak m(m,n,Q)} \quad\text{and}\quad 2^{\,mn-\mathfrak m(m,n,Q)+HW} \le F(m,n,Q)F^{*}(m,n,Q) \le 2^{mn}. \] The lower product bound has the same equality cases as the strong-forcing lower bound above, while the upper product bound is attained exactly by singleton patterns. In particular, the product is at least $2$, with equality exactly when $s=m$, $t=n$, and $Q$ is the all-ones pattern.

Disclosure

“Declaration of generative AI and AI-assisted technologies During the preparation of this draft, JG used Codex with GPT-5.6 Sol Ultra to assist with manuscript editing. The authors reviewed and edited the content as needed and take full re- sponsibility for the content of the article. References [1] D. Bienstock, E. Győri, An extremal problem on sparse 0-1”

PDF page 21

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T05:20:50.657494Z

Structural counts