Order-isomorphic twins in permutations

Abstract: Let

a_{1}, d o t s c, a_{n}

be a permutation of

[n]

. Two disjoint order-isomorphic subsequences are called emph{twins}. We show that every permutation of

[n]

contains twins of length

O m e g a (n^{3 / 5})

improving the trivial bound of

O m e g a (n^{1 / 2})

. We also show that a random permutation contains twins of length

O m e g a (n^{2 / 3})

, which is sharp.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Order-isomorphic twins in permutations