Lower bounds for superpatterns and universal sequences
Lower bounds for superpatterns and universal sequences
复制标题
超级模式和通用序列的下界
DOI：
10.1016/j.jcta.2021.105467
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Singhal, Mihir
中科院分区：
文献类型：
--
作者：
Chroman, Zachary;Kwan, Matthew;Singhal, Mihir
一个置换σ ∈ Sn称为k-泛置换或k-超模式置换，如果对每个π ∈ Sn，都有σ的一个子序列与π序同构。一个简单的计数证明了σ是k-超模式的唯一条件是n ≥（1/e2 + o（1））k2，Arratia证明了这个下界是最佳可能的.我们通过一个小的常数因子来改进平凡界，从而反驳了Arratia猜想。我们通过为σ中出现的模式设计一个有效的编码方案来实现这一点。这种方法是相当灵活的，是适用于其他的普遍性类型的问题，例如，我们还改进了一个约束Engen和Vatter的问题有关（k +1）元序列，其中包含所有的k-置换。
A permutation σ∈ S n is said to be k-universal or a k-superpattern if for every π∈ 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≥(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.
登录
查看更多内容
关于避免给定模式的排列数的斯坦利-威尔夫猜想
影响因子：
0.7
作者：
R. Arratia
通讯作者：
R. Arratia
关于排列模式的一些未决问题
DOI：
--
发表时间：
2012
期刊：
Surveys in Combinatorics
影响因子：
--
作者：
E. Steingrímsson
通讯作者：
E. Steingrímsson
包含所有排列作为子序列的序列长度的下界
DOI：
--
发表时间：
1976
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
D. Kleitman;D. J. Kwiatkowski
通讯作者：
D. J. Kwiatkowski
包含所有排列
DOI：
--
发表时间：
2018
期刊：
The American mathematical monthly
影响因子：
--
作者：
Michael Engen;Vincent Vatter
通讯作者：
Vincent Vatter
DOI：
--
发表时间：
2014
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Stephen Alstrup;Haim Kaplan;M. Thorup;Uri Zwick
通讯作者：
Uri Zwick