  Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint
order-isomorphic subsequences of $\pi$ are called twins. How long twins are
contained in every permutation? The well known Erd\H{o}s-Szekeres theorem
implies that there is always a pair of twins of length $\Omega(\sqrt{n})$. On
the other hand, by a simple probabilistic argument Gawron proved that for every
$n\geqslant 1$ there exist permutations with all twins having length
$O(n^{2/3})$. He conjectured that the latter bound is the correct size of the
longest twins guaranteed in every permutation. We support this conjecture by
showing that almost all permutations contain twins of length
$\Omega(n^{2/3}/\log n^{1/3})$. Recently, Bukh and Rudenko have tweaked our
proof and removed the log-factor. For completeness, we also present our version
of their proof (see Remark 1.2 below on the interrelation between the two
proofs).
  In addition, we study several variants of the problem with diverse
restrictions imposed on the twins. For instance, if we restrict attention to
twins avoiding a fixed permutation $\tau$, then the corresponding extremal
function equals $\Theta(\sqrt{n})$, provided that $\tau$ is not monotone. In
case of block twins (each twin occupies a segment) we prove that it is
$(1+o(1))\frac{\log n}{\log\log n}$, while for random permutations it is twice
as large. For twins that jointly occupy a segment (tight twins), we prove that
for every $n$ there are permutations avoiding them on all segments of length
greater than $24$.

Combinatorics