Localisation-Resistant Random Words with Small Alphabets
Localisation-Resistant Random Words with Small Alphabets
复制标题
具有小字母的抗本地化随机单词
DOI：
10.1007/978-3-030-28796-2_15
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Zémor
中科院分区：
文献类型：
--
作者：
C. Gavoille;Ghazal Kachigar;G. Zémor
我们考虑颜色为q的单词，即\(\left\{ {{1},\dots ,{q}}\right\} \)上没有两个连续字母相等的单词。在非信号资源的多部着色游戏的激励下，我们对满足k-可定位性的随机q色单词感兴趣。更准确地说，包含任何给定单词对的子词的概率间隔至少为k个字母，只能取决于它们的长度。我们关注的是最小字母大小q的问题，这样的随机单词的概率分布可以存在。对于\(k = 1\)，我们证明了\(q \geqslant 4\)的下界。这个界是最优的，因为存在一个合适的随机4色分布，这个分布是由Holroyd和Liggett在2015年构建的。我们的下界可以推广到k个可定位的随机单词，其中\(k+1\)字母的每个子词的字母必须成对不同。我们表明，在这种情况下，字母表的大小必须至少为\((k+1) \cdot (1+1/k)^k\)。
We consider q-coloured words, that is words on \(\left\{ {{1},\dots ,{q}}\right\} \) where no two consecutive letters are equal. Motivated by multipartite colouring games with nonsignalling resources, we are interested in random q-coloured words satisfying a k-localisability property. More precisely, the probability of containing any given pair of words as subwords spaced at least k letters apart can depend only on their lengths. We focus on the issue of the smallest alphabet size q for which a probability distribution for such random words can exist. For \(k = 1\), we prove a lower bound of \(q \geqslant 4\). The bound is optimal because there exists a suitable distribution for random 4-colourings that was constructed by Holroyd and Liggett in 2015. Our lower bound can be generalized to k-localisable random words where the letters of each subword of \(k+1\) letters must be pairwise different. We show that the alphabet size in this case must be at least \((k+1) \cdot (1+1/k)^k\).