Decomposing sequences into monotonic subsequences

Melvyn B. Nathanson, Rohit Parikh, Samer Salame

The function f:X -> Y is called k-monotonically increasing if there is a partition X = X_1 U ... U X_k such that f|X_i : X_i -> Y is monotonically increasing for i=1,...,k. It is p…