Cross-monotone subsequences |
| |
Authors: | F R K Chung P C Fishburn V K Wei |
| |
Institution: | (1) Bell Communications Research, 07974 Murray Hill, NJ, USA;(2) AT & T Bell Laboratories, 07974 Murray Hill, NJ, USA;(3) Bell Communications Research, 07974 Murray Hill, NJ, USA |
| |
Abstract: | Two finite real sequences (a
1,...,a
k
) and (b
1,...,b
k
) are cross-monotone if each is nondecreasing anda
i+1–a
i
b
i+1–b
i
for alli. A sequence ( 1,...,
n
) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing ( 1,...,
n
) is in CM(k), is bounded between aboutk
2/4 andk
2/2. It also shows thatg(k), the smallestn for which all ( 1,...,
n
) are in CM(k)and eithera
k
b
1 orb
k
a
1, equalsk(k–1)+2, and thath(k), the smallestn for which all ( 1,...,
n
) are in CM(k)and eithera
1 b
1 ... a
k
b
k
orb
1 a
1 ... b
k
a
k
, equals 2(k–1)2+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark
2×k
2 (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk
2 is replaced byk
2–1. |
| |
Keywords: | Primary: 06A99 secondary: 05A05 |
本文献已被 SpringerLink 等数据库收录! |
|