{"id":"arxiv/2608.17294","url":"https://arxiv.org/abs/2608.17294","tags":["math.CO","cs.DM"],"score":0,"title":"Enumerating forcing and strongly forcing (0,1)-matrices","domain":"math.CO","source":"arxiv","authors":["Lei Cao","Jesse Geneson"],"reviews":0,"subject":"math.CO","summary":"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$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}