论文标题
排列中的订单形态双胞胎
Order-isomorphic twins in permutations
论文作者
论文摘要
令$ a_1，\ dotsc，a_n $为$ [n] $的排列。两个不相交的订单 - 同态子序列称为\ emph {twins}。我们表明，$ [n] $的每个置换都包含长度$ω（n^{3/5}）$的双胞胎，改善了$ω（n^{1/2}）$的微不足道。我们还表明，随机排列包含长度$ω（n^{2/3}）$的双胞胎，这很尖锐。
Let $a_1,\dotsc,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 $Ω(n^{3/5})$ improving the trivial bound of $Ω(n^{1/2})$. We also show that a random permutation contains twins of length $Ω(n^{2/3})$, which is sharp.
