Fractional meanings of nonrepetitiveness

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Fractional meanings of nonrepetitiveness

Popis výsledku v původním jazyce

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.&amp; nbsp;In the first one, we demand that all subsequences of a sequence S, with gaps bounded by a fixed integer j &gt;= 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]&amp; nbsp; + 1 &lt;= pi(j)(r) &lt;=&amp; nbsp; 2 [j/r + 1] + 1, for all r &gt;= 3 and j &gt;= 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 &amp; nbsp;can be arbitrarily close to 1 for sufficiently large r. (C) 2022 Elsevier Inc. All rights reserved.&amp; nbsp;

Název v anglickém jazyce

Fractional meanings of nonrepetitiveness

Popis výsledku anglicky

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.&amp; nbsp;In the first one, we demand that all subsequences of a sequence S, with gaps bounded by a fixed integer j &gt;= 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]&amp; nbsp; + 1 &lt;= pi(j)(r) &lt;=&amp; nbsp; 2 [j/r + 1] + 1, for all r &gt;= 3 and j &gt;= 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 &amp; nbsp;can be arbitrarily close to 1 for sufficiently large r. (C) 2022 Elsevier Inc. All rights reserved.&amp; nbsp;

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Combinatorial Theory, Series A

ISSN

0097-3165

e-ISSN

—

Svazek periodika

189

Číslo periodika v rámci svazku

105598

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

1-22

Kód UT WoS článku

000793602100009

EID výsledku v databázi Scopus

2-s2.0-85125859521