Cross-monotone subsequences (Q1057271)

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\).