The Erdos-Szekeres monotone subsequence theorem

Any sequence of \((r-1)(s-1) + 1\) distinct reals contains an increasing subsequence of length \(r\) or a decreasing one of length \(s\). The bound is tight: \(s-1\) descending blocks of \(r-1\) ascending values escape at length \((r-1)(s-1)\), and the tests build that sequence.

Usage

morie_erdos_szekeres_check(sequence, r = NULL, s = NULL)

Arguments

sequence

Distinct numeric values.

r, s

Target lengths, both at least 2; omit both to just get the longest monotone lengths.

Value

A list with longest_increasing, longest_decreasing, threshold, applies, guarantee_met.

References

Erdos P, Szekeres G (1935) Compositio Math 2:463-470.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
morie_erdos_szekeres_check(V)
#> $longest_increasing
#> [1] 8
#> 
#> $longest_decreasing
#> [1] 1
#> 
#> $threshold
#> NULL
#> 
#> $applies
#> NULL
#> 
#> $guarantee_met
#> NULL
#> 
#> $estimate
#> [1] 8
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Erdos-Szekeres theorem (1935)"
#>