Collection of Maths Problems

Monotone subsequences

Task number: 4022

• Solution

  For a given sequence \( (a_1)_{i=1}^ n \) we color the edge \( (i, j) \), \( i < j \) of the graph \( K_n \) blue if \( a_i < a_j \) and otherwise red.

  If \( n > R (a + 1, b + 1) \), then the elements of the sequence corresponding to the vertices of the monochromatic complete subgraph form the sought monotone subsequence.

• Variant

  Show that such monotone subsequence exists in each sequence of length \( ab + 1 \).

• Hint

  By induction on \(a\).

• Solution

  If \( a = 0 \) or \( b = 0 \), then the one-element sequence is monotone.

  Assume the validity of the statement for \( a, b-1 \).

  For a given sequence \( X_0 \) of length \( ab + 1 \), repeat the following procedure \( (a + 1) \) times: Since the length of the sequence \( X_i \) is at least \( a (b-1) +1 \), then it either contains a non-increasing subsequence of length \( a + 1 \) or a non-decreasing subsequence of length \( b \). Without loss of generality, let us assume that the second case always occurs. The last element of the non-decreasing subsequence of length \( b \) found in the sequence \( X_i \) is denoted by \( x_i \). In the next iteration, we continue with the sequence \( X_{i + 1}: = X_i \setminus x_i \).

  We thus obtain a set of selected elements \( \{x_1,…, x_{a + 1} \} \) from the original sequence. Without loss of generality, again assume that these elements do not form a non-increasing subsequence, i.e. they contain a pair \( x_i, x_j \), where \( x_i < x_j \) and \( x_i \) occurs in the original sequence before \( x_j \). But then the non-decreasing subsequence of length \( b \) found in the \( i \) -th iteration extended by \( x_j \) is the desired subsequence of length \( b + 1 \) .