Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS₀(k) if it has 0-cells (i, j₁), (i + 1,j₂),..., (i + k – 1,j_k) for somei andj₁ < ... < j_k, and it contains anS₁(k) if it has 1-cells (i₁,j), (i₂,j + 1),...,(i_k,j + k – 1) for somej andi₁ < ... <i_k. We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS₀(k) isk₀ m, thenM must have anS₁(k) withk m/(k₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS₀(k) (in the cells on or below the main diagonal) isk₀ m, thenM has anS₁(k) withk m/(k₀ + 1). Moreover, these results are best-possible.