论文标题
通用阵列
Universal arrays
论文作者
论文摘要
$ q $符号上的一个单词是来自尺寸$ q $的固定字母的一系列字母。对于整数$ k \ ge 1 $，我们说一个单词$ w $是$ k $ - 宇宙，如果给定长度$ k $的任意单词，可以通过从$ w $中删除条目来获得它。很容易看出，$ q $符号上的$ k $ - 上词的最小长度正好是$ qk $。我们证明，几乎每个大小$（1+o（1））C_QK $的单词是$ k $ - 宇宙，其中$ c_q $是一个明确的常数，其值约为$ q \ log q $。此外，我们表明，均匀选择的单词的$ k $ - 大学物业表现出鲜明的门槛。最后，通过扩展Alon的技术[几何和功能分析27（2017），第1期。 1，1--32]，我们为这个问题的每个较高维度类似物提供渐近的紧密界限。
A word on $q$ symbols is a sequence of letters from a fixed alphabet of size $q$. For an integer $k\ge 1$, we say that a word $w$ is $k$-universal if, given an arbitrary word of length $k$, one can obtain it by removing entries from $w$. It is easily seen that the minimum length of a $k$-universal word on $q$ symbols is exactly $qk$. We prove that almost every word of size $(1+o(1))c_qk$ is $k$-universal with high probability, where $c_q$ is an explicit constant whose value is roughly $q\log q$. Moreover, we show that the $k$-universality property for uniformly chosen words exhibits a sharp threshold. Finally, by extending techniques of Alon [Geometric and Functional Analysis 27 (2017), no. 1, 1--32], we give asymptotically tight bounds for every higher dimensional analogue of this problem.
