Fractional meanings of nonrepetitiveness
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00129835" target="_blank" >RIV/00216224:14330/22:00129835 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.jcta.2022.105598" target="_blank" >https://doi.org/10.1016/j.jcta.2022.105598</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jcta.2022.105598" target="_blank" >10.1016/j.jcta.2022.105598</a>
Alternative languages
Result language
angličtina
Original language name
Fractional meanings of nonrepetitiveness
Original language description
A sequence S is called r-nonrepetitive if no tau sequentially adjacent blocks in S are identical. By the classic results of Thue from the beginning of the 20th century, we know that there exist arbitrarily long binary 3-nonrepetitive sequences and ternary 2-nonrepetitive sequences. This discovery stimulated over the years intensive research leading to various generalizations and many exciting problems and results in combinatorics on words. In this paper, we study two fractional versions of nonrepetitive sequences.& nbsp;In the first one, we demand that all subsequences of a sequence S, with gaps bounded by a fixed integer j >= 1, are r-nonrepetitive. (This variant emerged from studying nonrepetitive colorings of the Euclidean plane.) Let pi(r)(r) denote the least size of an alphabet guaranteeing existence pi( j) 1 of arbitrarily long such sequences. We prove that [j/r-1]& nbsp; + 1 <= pi(j)(r) <=& nbsp; 2 [j/r + 1] + 1, for all r >= 3 and j >= 1. We also consider r-1 a more general situation with the gap bound j being a real number, and apply this to nonrepetitive coloring of the plane. The second variant allows for using a "fractional " alphabet, analogously as for the fractional coloring of graphs. More specifically, we look for sequences of b -element subsets B-1,B- B-2, ... of an a-element alphabet, with the ratio a/b as small as possible, such that every member of the Cartesian product B-1 x B-2 x . . . is r-nonrepetitive. By using the entropy compression argument, we prove that the corresponding parameter pi(f )(r) = inf a/b & nbsp;can be arbitrarily close to 1 for sufficiently large r. (C) 2022 Elsevier Inc. All rights reserved.& nbsp;
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Combinatorial Theory, Series A
ISSN
0097-3165
e-ISSN
—
Volume of the periodical
189
Issue of the periodical within the volume
105598
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
22
Pages from-to
1-22
UT code for WoS article
000793602100009
EID of the result in the Scopus database
2-s2.0-85125859521