论文标题
在虚弱的双胞胎和上下的子渗透
On weak twins and up-and-down sub-permutations
论文作者
论文摘要
两个排列$（x_1，\ dots，x_w）$和$（y_1，\ dots，y_w）$如果$ x_i <x_ <x_ {i+1} $在＆y y_i <y_i <y__ {y_i+1} $时，$ 1 \ y_i+1} $在所有$ 1 \ leqslant i \ leqslant i \ leqslant i \ leqslant w $中。令$π$为套装$ [n] = \ {1,2，\ dots，n \} $的排列，让$ wt（π）$表示最大的整数$ w $，这样$π$包含一对弱相似的相似的子permutations（称为弱的双胞胎）长度$ w $ w $。最后，让$ wt（n）$表示所有排列$π$ of $ [n] $的最低$ wt（π）$。显然，$ wt（n）\ le n/2 $。在本文中，我们表明$ \ tfrac n {12} \ le wt（n）\ le \ tfrac n2-ω（n^{1/3}）$。 我们还研究了这个问题的变体。让我们说$π'=（π（i_1），...，π（i_j））$，$ i_1 <\ cdots <i_j $，是$π$（I_1）>π（i_2）>π（I_2）<π（i_3）> ... $或π（i_3）> ... $π（i_1）<π（i_2）>π（i_3）<... $。令$π_n$为从所有$ n！$ [n] $的所有$ n！$排列中均匀选择的随机排列。众所周知，$π_n$中最长的交替排列的长度几乎肯定是渐近的（A.A.S.）接近$ 2N/3 $。我们研究了一对不相交的子permutations $π_n$的最大长度$α（n）$，并表明有两个常数$ 1/3 <c_1 <c_1 <c_2 <1/2 $ $ c_1n \leα（n）\ le c_2n $。 此外，我们表明交替形状在给定长度的所有排列中最受欢迎。
Two permutations $(x_1,\dots,x_w)$ and $(y_1,\dots,y_w)$ are weakly similar if $x_i<x_{i+1}$ if and only if $y_i<y_{i+1}$ for all $1\leqslant i \leqslant w$. Let $π$ be a permutation of the set $[n]=\{1,2,\dots, n\}$ and let $wt(π)$ denote the largest integer $w$ such that $π$ contains a pair of disjoint weakly similar sub-permutations (called weak twins) of length $w$. Finally, let $wt(n)$ denote the minimum of $wt(π)$ over all permutations $π$ of $[n]$. Clearly, $wt(n)\le n/2$. In this paper we show that $\tfrac n{12}\le wt(n)\le\tfrac n2-Ω(n^{1/3})$. We also study a variant of this problem. Let us say that $π'=(π(i_1),...,π(i_j))$, $i_1<\cdots<i_j$, is an alternating (or up-and-down) sub-permutation of $π$ if $π(i_1)>π(i_2)<π(i_3)>...$ or $π(i_1)<π(i_2)>π(i_3)<...$. Let $Π_n$ be a random permutation selected uniformly from all $n!$ permutations of $[n]$. It is known that the length of a longest alternating permutation in $Π_n$ is asymptotically almost surely (a.a.s.) close to $2n/3$. We study the maximum length $α(n)$ of a pair of disjoint alternating sub-permutations in $Π_n$ and show that there are two constants $1/3<c_1<c_2<1/2$ such that a.a.s. $c_1n\le α(n)\le c_2n$. In addition, we show that the alternating shape is the most popular among all permutations of a given length.
