Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
A little offtop, but what you take as $R_n$'s? –  Leonid Petrov Jul 3 '10 at 1:36
    
The set of elements of rank n. –  Charles Chen Jul 3 '10 at 2:49
    
But which concrete examples you consider? Purely abstract finite sets? –  Leonid Petrov Jul 3 '10 at 6:13
    
Yeah, abstract finite sets. The basic concrete example is Young's lattice. –  Charles Chen Jul 3 '10 at 7:16
add comment

4 Answers

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.

share|improve this answer
2  
One other lower bound that may be of use...If you $n=p^2+p+1$ and the incidence matrix of a projective plane you get a matrix with about $n^{3/2}$ nonzero entries satisfying the property (an all-$1$ submatrix would correspond to two lines intersecting in two points). Replacing any subset of the $1$ by $0$ still works, so you have $2^{n^{3/2}}$, which unfortunately grows very quickly with $n$. This example comes from the lower bound to the $O(n^{3/2})$ bound mentioned in Pettie's paper. I'm not sure the original source for it. –  Kevin P. Costello Jul 3 '10 at 18:36
add comment

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.

share|improve this answer
1  
Note that there can be at most (m choose 2) columns with two or more ones, and the remaining columns must have fewer than two ones. Further if one column has j ones, then that limits the number of other columns with two or more ones to (m choose 2) minus (j choose 2). So the answer will be a sum of powers of (m+1). If n > (m choose 2), then the answer will be a multiple of a power of (m+1). Gerhard "Ask Me About System Design" Paseman, 2010.07.02 –  Gerhard Paseman Jul 3 '10 at 5:40
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
(It's possible I might have had the wrong notion of "avoid" here, seeing Douglas Stone's answer below.) –  Michael Lugo Jul 3 '10 at 4:07
    
No, it is not the right sequence. The number of $n\times n$ matrices with no $2\times 2$ submatrix of all ones for $n=1,2,3,4,5$ is: 2, 15, 334, 18521, 2293896 This counts match A133791 only for $n=2$. –  Max Alekseyev Jul 3 '10 at 14:40
    
The difference here is that submatrices are assumed to be contiguous (I think this is not the standard definition of a submatrix -- but is common enough to cause problems). –  Douglas S. Stones Jul 4 '10 at 12:53
    
Even if submatrices are assumed to be contiguous, A133791 is still not the right sequence. In particular, for $m=n=1$ we have 2 matrices, while A133791(1) gives 1. –  Max Alekseyev Jul 4 '10 at 19:00
1  
@Dimension10 Hi, it is great you update the links. But please do not do too many at the same time. Better do batches of just 3 or 4. If not there is a burst of edits on te front page and some do not like this. –  quid Oct 29 '13 at 11:54
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.