Monotone subsequences in (0,1)-matrices
type: Item
instance of: scholarly article
title: Monotone subsequences in (0,1)-matrices
zbMATH Open document ID: 0593.05013
DOI: 10.1007/BF01788074
author: Peter Fishburn
author: Fan Chung
author: Victor K. Wei
published in: Graphs and Combinatorics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 3952781
zbMATH Keywords: rectangular matrix
zbMATH Keywords: monotone subsequence
reviewed by: S. S. Agayan
MaRDI profile type: Publication
cites work: Cross-monotone subsequences
cites work: Q5759552
cites work: Monotonic Subsequences
cites work: A Simple Proof of a Theorem of Erdös and Szekeres*
full work available at URL: https://doi.org/10.1007/bf01788074
OpenAlex ID: W1991567662
Recommended article: Monotonic subsequences in dimensions higher than one
Recommended article: Monotone subsequences in any dimension
Recommended article: On Monotone Subsequences
Recommended article: Q3209846
Recommended article: Monotone Subsequences in High-Dimensional Permutations
Recommended article: Cross-monotone subsequences
Recommended article: The minimum number of monotone subsequences
Recommended article: On certain completely monotonic sequences
Recommended article: On Three Different Notions of Monotone Subsequences
Recommended article: Monotone subsequence via ultrapower
description: scientific article; zbMATH DE number 3952781