Erdős–Szekeres bound visualization

Given a permutation of {1,…,k}, let a and b be the lengths of the longest increasing and decreasing subsequences (LIS and LDS) of the permutation. The bound is that a·b ≥ k. This follows because every element gets a label (a_i,b_i) describing the lengths of the LIS and LDS ending at that element, and these labels are all distinct. The Erdős–Szekeres theorem generalises this: any sequence of length (a−1)(b−1)+1 has either an increasing subsequence of length a or a decreasing subsequence of length b.

Choose k (size of permutation): 6

In LIS

In LDS

In LIS & LDS

Other

Index	Value	LIS length (a_i)	LDS length (b_i)