Erdös-Szekeres Tableaux

length

3

4

5

6

7

8

permutation k

4254

label edges

Tableau	Poset	Lattice

The Erdös–Szekeres tableau

(σ)

of a permutation

σ=(

a

1

,…,

a

n

)

is the sequence of points

n

{(

x

i

,

y

i

)}

i=1

where

x

i

(respectively

y

i

) is the length of the longest increasing (respectively decreasing) subsequence ending at

a

i

. Since different permutations can have the same Erdös–Szekeres tableau (EST) (e.g.

(2,1,4,3)

and

(3,1,4,2)

both have the same "N-shaped" EST), there is an equivalence relation on permutations

[σ]={σ~τ|(σ)=(τ)}

. The poset is defined by taking the intersection over all orderings induced by elements of

[σ]

. Informally, the poset records those relations that can be recovered from the EST. The lattice is defined on

[σ]

, where

(τ,τ')

is in the covering relation if

τ

and

τ'

differ by an adjacent transposition (which can be viewed as an edge label) and

τ

precedes

τ'

lexicographically.