Cross-monotone subsequences
type: Item
instance of: scholarly article
title: Cross-monotone subsequences
zbMATH Open document ID: 0563.05003
DOI: 10.1007/BF00582741
author: Peter Fishburn
author: Fan Chung
author: Victor K. Wei
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: Two finite non-decreasing sequences \((a_ 1,...,a_ k)\) and \((b_ 1,...,b_ k)\) are cross-monotone if \(a_{i+1}-a_ i\geq b_{i+1}-b_ i\) for all i. A finite non-decreasing real sequence is in the class CM(k) if it has two disjoint k-term cross-monotone subsequences. The paper shows that f(k), the smallest n such that every non-decreasing real n- term sequence is in CM(k), is bounded between about \(k^ 2/4\) and \(k^ 2/2\). Known values for f(k) are \(f(2)=4\), \(f(3)=7\) and \(f(4)=11\), the bounds obtained in this paper giving \(7\leq f(4)\leq 48.\) Two more restricted classes than CM(k) are also defined and, in these cases, exact values for the functions that correspond to f(k) are found. The results rely on new theorems for regular patterns in (0,1)-matrices that may be of interest. For example: Every upper-triangular \(k^ 2\times k^ 2\) (0,1)-matrix has either k ones in consecutive columns, each below its predecessor, or k zeros in consecutive rows, each to the right of its predecessor, the same conclusion being false when \(k^ 2\) is replaced by \(k^ 2-1\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 06A99
zbMATH DE Number: 3896937
zbMATH Keywords: (0,1)-matrix patterns
zbMATH Keywords: cross-monotonicity
zbMATH Keywords: monotone subsequences
MaRDI profile type: Publication
cites work: On unimodal subsequences
cites work: Longest common subsequences of two random sequences
cites work: Q5759552
cites work: Periods in strings
cites work: String overlaps, pattern matching, and nontransitive games
cites work: \(\Delta\)-monotone arrangements of real numbers
cites work: Monotonic Subsequences
cites work: A Simple Proof of a Theorem of Erdös and Szekeres*
cites work: Long Common Subsequences and the Proximity of Two Random Strings
description: scientific article; zbMATH DE number 3896937