Cross-monotone subsequences
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\).
- \(\Delta\)-monotone arrangements of real numbers
- A Simple Proof of a Theorem of Erdös and Szekeres*
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Long Common Subsequences and the Proximity of Two Random Strings
- Longest common subsequences of two random sequences
- Monotonic Subsequences
- On unimodal subsequences
- Periods in strings
- String overlaps, pattern matching, and nontransitive games
This page was built for publication: Cross-monotone subsequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057271)