Count of binary matrices that avoids a certain sub-matrix

Question

What is the number of $n$ by $m$ zero-one matrices that avoid a $2$ by $2$ sub-matrix of all ones?

For the motivation, I'm trying to generate nontrivial examples of differential posets, which are locally finite, ranked, and equipped with a $\mathbb Z$-linear operator $Ux = \sum_{y \gtrdot x} y$.

By restricting to $R_n$, the set of elements of rank $n$, we get a map $U_n: \mathbb Z[R_n] \to \mathbb Z[R_{n+1}]$ ($\mathbb Z[R_n]$ is the free vector space with basis vectors indexed by elements in $R_n$.) The main condition differential posets satisfy is $U_n^t U_n - U_{n-1} U_{n-1}^t = I$, which is called the differential condition.

Since knowing $U$ give complete information about the poset, I'm trying to recursively generate $U_n$--given $U_{n-1}$, figure out all the matrices $U_n$ that satisfies the differential condition above. It turns out that the differential condition forces $U_n$ to avoid a $2$ by $2$ sub-matrix of all ones. I'd like to be able to use this fact to prune my search space (which is frickin huge), but it might be more trouble than it's worth, and hence I'm asking the question.

Also, if anyone knows a better way to generate all such differential posets, I'd love to know.

EDIT: By avoid, I mean when you restrict to two rows and two columns, you get all 1s. Answers to the other question are still good to know though!

Answer 1

Seth Pettie has done some fascinating work on this topic and generalizations. In his setting, the goal is to upper bound the number of 1s in a 0-1 matrix that excludes a particular submatrix pattern. Your specific example (if restricted to the case of m=n) is the problem he denotes as Ex($P_5$, n) in this paper, in which he mentions earlier work by Furedi and Hajnal giving an upper bound of $O(n^{3/2})$ for the total number of ones.

While the number of ones doesn't answer your question directly, it gives an upper bound. I don't know how precise you need your answer to be, but this might help.

Answer 2

This looks like it will be a difficult question to answer in general, but here's the answers for $m \in \{2,3\}$. Let N(m,n) be the number of m by n (0,1)-matrices without a 2 by 2 all-1 submatrix.

Let A=00 B=01 C=10 D=11. Then any n by 2 (0,1)-matrix counted by N(2,n) is equivalent to a word of length n on the alphabet {A,B,C,D} without two D's. Hence \[N(2,n)=n \cdot 3^{n-1}+3^n.\] The first term counts when there is a D in the word, the other term counts without any D's. See: http://www.oeis.org/A006234

Now let A=000 B=001 C=010 D=011 E=100 F=101 G=110 H=111. Then any (0,1)-matrix counted by N(2,n) is equivalent to a word of length n without (a) two D's (b) two F's (c) two G's (d) two H's or (e) an H and one of D, F or G. Hence \[N(3,n)=n \cdot 4^{n-1}+\sum_{i=0}^{3} {3 \choose i} (n)_i 4^{n-i}\] where $(n)_i=n(n-1)\cdots(n-i+1)$. The first term is the number of words containing H. The sum counts the terms without any H: First we choose i of D, F or G, and place them in the word. The remaning letters must be A, B, C or E.

Answer 3

It is worth to mention that if we forbid also $2\times 2$ submatrices of all zeros, then there will be no such matrices as soon as $m,n\geq 5$. In other words, every binary $5\times 5$ matrix contains a $2\times 2$ submatrix consisting of all ones or all zeros.

Answer 4

For the case when $m = n$, these appear to have been computed as this sequence in Sloane. I don't know how they were computed, though; I found the sequence by solving the cases $m = n = 1$, $m = n = 2$, $m = n = 3$ by hand and searching.