论文标题
置换中双胞胎的变化
Variations on twins in permutations
论文作者
论文摘要
令$π$为集合$ [n] = \ {1,2，\ dots，n \} $的排列。 $π$的两个不相交的命令 - 同态子序列称为双胞胎。每个排列中包含多长时间的双胞胎？众所周知的Erdős-Szekeres定理意味着总是有一对长度为$ω（\ sqrt {n}）$的双胞胎。另一方面，通过一个简单的概率参数gawron证明，对于每个$ n \ geqslant 1 $都存在排列，所有双胞胎都有长度$ o（n^{2/3}）$。他猜想后者是在每个排列中保证的最长双胞胎的正确大小。我们通过证明几乎所有排列都包含长度$ω（n^{2/3}/\ log n^{1/3}）$的双胞胎来支持这一猜想。最近，Bukh和Rudenko调整了我们的证明并删除了原木因子。为了完整性，我们还介绍了他们的证明版本（请参见下面的注释1.2关于两个证明之间的相互关系）。 此外，我们研究了该问题的几种变体，对双胞胎施加的各种限制。例如，如果我们限制了避免固定排列$τ$的双胞胎的注意，则相应的极函数等于$θ（\ sqrt {n}）$，但前提是$τ$不是单调。如果块双胞胎（每个双胞胎都占据段），我们证明它是$（1+o（1））\ frac {\ log n} {\ log \ log \ log \ log n} $，而对于随机排列，它的大两倍。对于共同占据分段（紧密双胞胎）的双胞胎，我们证明，每$ n $都会避开所有长度大于$ 24 $的部分。
Let $π$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $π$ are called twins. How long twins are contained in every permutation? The well known Erdős-Szekeres theorem implies that there is always a pair of twins of length $Ω(\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 $Ω(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 $τ$, then the corresponding extremal function equals $Θ(\sqrt{n})$, provided that $τ$ 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$.
