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\to0,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 and Rath (2011) establishing the existence of permutons.
%0 Generic
%1 han2020quasirandom
%A Hàn, Hiêp
%A Kiwi, Marcos
%A Pavez-Signé, Matías
%D 2020
%K Reem graph_limits words
%T Quasi-random words and limits of word sequences
%U http://arxiv.org/abs/2003.03664
%X 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\to0,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 and Rath (2011) establishing the existence of permutons.
@misc{han2020quasirandom,
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]\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 and Rath (2011) establishing the existence of permutons.},
added-at = {2020-03-12T22:54:12.000+0100},
author = {Hàn, Hiêp and Kiwi, Marcos and Pavez-Signé, Matías},
biburl = {https://www.bibsonomy.org/bibtex/2533bf40e377d9a5638cc403cdb1b9017/j.c.m.janssen},
description = {Quasi-random words and limits of word sequences},
interhash = {4e00941dbef0533702cc61dacf0a5163},
intrahash = {533bf40e377d9a5638cc403cdb1b9017},
keywords = {Reem graph_limits words},
note = {cite arxiv:2003.03664Comment: 30 pages},
timestamp = {2020-03-12T22:54:12.000+0100},
title = {Quasi-random words and limits of word sequences},
url = {http://arxiv.org/abs/2003.03664},
year = 2020
}