Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2512.03670 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909941845983232 |
|---|---|
| author | Bui, Vuong Rosenfeld, Matthieu |
| author_facet | Bui, Vuong Rosenfeld, Matthieu |
| contents | We prove that for any sequence of binary alphabets $\mathcal{A}_1,\mathcal{A}_2,\dots$, there exists a cube-free word $c_1c_2\dots$ so that $c_1\in\mathcal{A}_1,c_2\in\mathcal{A}_2,\dots$. In particular, for every $n$, there are at least $1.35^n$ cube-free words in $\mathcal{A}_1\times\mathcal{A}_2\times\dots\times \mathcal{A}_n$. We also prove that if the list of alphabets is computable then one of these words is computable and its $n$th letter can be computed in time polynomial in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03670 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | There exist infinite cube-free words over any sequence of binary alphabets Bui, Vuong Rosenfeld, Matthieu Combinatorics We prove that for any sequence of binary alphabets $\mathcal{A}_1,\mathcal{A}_2,\dots$, there exists a cube-free word $c_1c_2\dots$ so that $c_1\in\mathcal{A}_1,c_2\in\mathcal{A}_2,\dots$. In particular, for every $n$, there are at least $1.35^n$ cube-free words in $\mathcal{A}_1\times\mathcal{A}_2\times\dots\times \mathcal{A}_n$. We also prove that if the list of alphabets is computable then one of these words is computable and its $n$th letter can be computed in time polynomial in $n$. |
| title | There exist infinite cube-free words over any sequence of binary alphabets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.03670 |