2 added 151 characters in body

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!

1

# Count of binary matrices that avoids a certain sub-matrix

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.