论文标题
准随机单词和单词序列的限制
Quasi-random words and limits of word sequences
论文作者
论文摘要
单词是有限字母上字母的序列。我们研究了这个对象的两个密切相关的主题：准随机性和极限理论。关于第一个主题，我们调查了在间隔上和著名的钟（Graham-graham-wilson-wilson Therorem for Graphs for Graphs of Grapers of Graphs of Graphers of Graphers of Lord属性列表）的概念。特别是，我们表明统一性等于计算3个字母的子序列。 受图形限制理论的启发，我们然后研究了收敛单词序列的限制，其中所有子序列都会收敛。我们表明，收敛的单词序列具有自然限制，即表格$ f的可测量功能：[0,1] \ to [0,1] $。通过该理论，我们表明，每个遗传单词属性都是可检验的，解决了单词限制有限的强制性问题，并将其确立为副产品的一个随机单词序列的新模型。 沿着单词限制存在的证据的路线，我们还可以确定较高维度结构的限制的存在。特别是，我们获得了Hoppen，Kohayakawa，Moreira，Ráth和Sampaio的替代证明[{\ IT J. Combin。理论ser。 B 103（1）：93---113，2013}]建立了Permuton的存在。
Words are sequences of letters over a finite alphabet. We study two intimately related topics for this object: quasi-randomness and limit theory. With respect to the first topic we investigate the notion of uniform distribution of letters over intervals, and in the spirit of the famous Chung--Graham--Wilson theorem for graphs we provide a list of word properties which are equivalent to uniformity. In particular, we show that uniformity is equivalent to counting 3-letter subsequences. Inspired by graph limit theory we then investigate limits of convergent word sequences, those in which all subsequence densities converge. We show that convergent word sequences have a natural limit, namely Lebesgue measurable functions of the form $f:[0,1]\to[0,1]$. Via this theory we show that every hereditary word property is testable, address the problem of finite forcibility for word limits and establish as a byproduct a new model of random word sequences. Along the lines of the proof of the existence of word limits, we can also establish the existence of limits for higher dimensional structures. In particular, we obtain an alternative proof of the result by Hoppen, Kohayakawa, Moreira, Ráth and Sampaio [{\it J. Combin. Theory Ser. B 103(1):93--113, 2013}] establishing the existence of permutons.
