论文标题
超模式和通用序列的下限
Lower bounds for superpatterns and universal sequences
论文作者
论文摘要
s_n $中的排列$σ\据说为$ k $ - $ - $ k $ -superpattern，如果对于s_k $中的每个$π\，则有一个$σ$的子序列，即订单 - 呈现量为$π$。一个简单的计数参数表明，只有$ n \ ge（1/e^2+o（1））k^2 $，$σ$才能是$ k $ -superpattern，并且Arratia猜想此下限最有可能。反对Arratia的猜想，我们改善了由小恒定因素的琐碎束缚。我们通过为出现在$σ$中的模式设计有效的编码方案来实现这一目标。这种方法非常灵活，适用于其他普遍类型的问题。例如，我们还提高了Engen的束缚，并在有关$（k+1）$ - ARY序列的问题上，该序列包含所有$ k $ - permutations。
A permutation $σ\in S_n$ is said to be $k$-universal or a $k$-superpattern if for every $π\in S_k$, there is a subsequence of $σ$ that is order-isomorphic to $π$. A simple counting argument shows that $σ$ can be a $k$-superpattern only if $n\ge (1/e^2+o(1))k^2$, and Arratia conjectured that this lower bound is best-possible. Disproving Arratia's conjecture, we improve the trivial bound by a small constant factor. We accomplish this by designing an efficient encoding scheme for the patterns that appear in $σ$. This approach is quite flexible and is applicable to other universality-type problems; for example, we also improve a bound by Engen and Vatter on a problem concerning $(k+1)$-ary sequences which contain all $k$-permutations.
