WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

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.
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.