Abstract :

The quantity N_5(n) is the maximum length of a finite sequence over n symbols which has no two identical consecutive elements and no 5-term alternating subsequence. Improving the constant factor in the previous bounds of Hart and Sharir, and of Sharir and Agarwal, we prove that

N_5(n) <  2n.alpha(n)+O(n.alpha(n)^{1/2}),
where alpha(n) is the inverse to the Ackermann function. Quantities N_s(n) can be generalized and any finite sequence, not just an alternating one, can be assigned extremal function. We present a sequence  with no 5-term alternating subsequence and with an extremal function >> n2^{alpha(n)}.