Monotone subsequences in (0,1)-matrices (Q1076026)

A length-k monotone subsequence of 0's in a (0,1)-matrix, denited by \(\delta_ 0(k)\), is a sequence of k 0's in cells \((i,j_ 1),(i+i,j_ 2),...,(i+k-1,j_ k)\) for some i and \(j_ 1<j_ 2<...<j_ k\). A length-k monotone subsequence of 1's in a (0,1)-matrix, denoted by \(\delta_ 1(k)\), is a subsequence of k 1's in cells \((i_ 1,j),(i_ 2,j+1),...,(i_ k,j+k-1)\) for some j and \(i_ 1<i_ 2<...<i_ k.\) In this paper the author proves that if M is an \(m\times m\) rectangular (0,1)-matrix with \(1\leq m\leq n\) whose largest k for a \(\delta_ 0(k)\) is \(k_ 0\leq m\), then M must have a \(\delta_ 1(k)\) with \(k\geq [m/(k_ 0+1)]\). Similarly, if M is an \(m\times m\) lower-triangular matrix whose largest k for a \(\delta_ 0(k)\) (in the cells on or below the main diagonal) is \(k_ 0\leq m\), then M has a \(\delta_ 1(k)\) with \(k\geq [m/(k_ 0+1)]\). Moreover, these results are best-possible.