European Journal of Combinatorics Volume 98 Article Number 103403 Published Dec 2021
es_ES
Identifier
dc.identifier.other
10.1016/j.ejc.2021.103403
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/183092
Abstract
dc.description.abstract
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] -> [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, Rath and Sampaio (Hoppen et al., 2013) establishing the existence of permutons.
es_ES
Patrocinador
dc.description.sponsorship
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
CONICYT FONDECYT 1191838
GrHyDy, France ANR-20-CE40-0002
ANID Doctoral scholarship, Chile ANID-PFCHA/Doctorado Nacional/2017-21171132
ANID, Chile PIA AFB170001
es_ES
Lenguage
dc.language.iso
en
es_ES
Publisher
dc.publisher
Elsevier
es_ES
Type of license
dc.rights
Attribution-NonCommercial-NoDerivs 3.0 United States