Monotone Sequence Game (2008)

Originator(s): D.B. West (presented by West - REGS 2008)

Background: The Erdös-Szekeres Theorem states that any list of length n distinct values contains a monotone subsequence (increasing or decreasing) with at least √n elements. Two players Max and Min play a game to create a sequence that is a permutation of {1,...,n}. Players alternate choosing the next element of the sequence from the remaining unchosen values. Max tries to make the maximum length of a monotone sequence in the resulting permutation as large as possible. Min tries to minimize it.

Question 1: With best play by both players, what is the maximum length of a monotone subsequence in the resulting permutation, as a function of n?

Comments: The value resulting from any instance of the game is at least √n. By always choosing the least remaining element, Max can ensure an increasing sublist of length at least ⌈(n+1)/2⌉; can Max make use of the flexibility of making decreasing lists to ensure a longer monotone list?

A monotone subsequence can be viewed as an increasing chain or a decreasing chain in the poset that is a chain of size n. More generally, the "board of available pieces" may be any poset P, and again Max tries to ensure the longest possible increasing or decreasing chain in the resulting permutation. Of course, Max does at least as well as in a chain whose size is the height of P by ignoring the elements outside such a chain.

Question 2: What can be said about the result of the game for more complicated posets?
In particular, what is the result of playing on the subset poset 2ⁿ?

The posing of these questions was stimulated by a much different game that also arises by players alternately selecting elements from a poset, such as the n-element chain. It is a positional game in which the "winner" is the first player to create a montone sequence of a specified length (in an alternative game, that is the loser). See [AAAHHMS] for a discussion of what is known about such games.

References:
[AAAHHMS] M.H. Albert, R.E.L. Aldred, M.D. Atkinson, C.C. Handley, D.A. Holton, D.J. McCaughan, and B.E. Sagan; Monotonic Sequence Games, preprint.