Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2405.06202 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929557758541824 |
|---|---|
| author | Anand Geneson, Jesse Kaustav, Suchir Tsai, Shen-Fu |
| author_facet | Anand Geneson, Jesse Kaustav, Suchir Tsai, Shen-Fu |
| contents | In this paper, we introduce saturation and semisaturation functions of sequences, and we prove a number of fundamental results about these functions. Given a forbidden sequence $u$ with $r$ distinct letters, we say that a sequence $s$ on a given alphabet is $u$-saturated if $s$ is $r$-sparse, $u$-free, and adding any letter from the alphabet to an arbitrary position in $s$ violates $r$-sparsity or induces a copy of $u$. We say that $s$ is $u$-semisaturated if $s$ is $r$-sparse and adding any letter from the alphabet to $s$ violates $r$-sparsity or induces a new copy of $u$. Let the saturation function $\operatorname{Sat}(u, n)$ denote the minimum possible length of a $u$-saturated sequence on an alphabet of size $n$, and let the semisaturation function $\operatorname{Ssat}(u, n)$ denote the minimum possible length of a $u$-semisaturated sequence on an alphabet of size $n$. For alternating sequences, we determine both the saturation function and the semisaturation function up to a constant multiplicative factor. We show for every sequence that the semisaturation function is always either $O(1)$ or $Θ(n)$. For the saturation function, we show that every sequence $u$ has either $\operatorname{Sat}(u, n) \ge n$ or $\operatorname{Sat}(u, n) = O(1)$. For every sequence with $2$ distinct letters, we show that the saturation function is always either $O(1)$ or $Θ(n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06202 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sequence saturation Anand Geneson, Jesse Kaustav, Suchir Tsai, Shen-Fu Combinatorics In this paper, we introduce saturation and semisaturation functions of sequences, and we prove a number of fundamental results about these functions. Given a forbidden sequence $u$ with $r$ distinct letters, we say that a sequence $s$ on a given alphabet is $u$-saturated if $s$ is $r$-sparse, $u$-free, and adding any letter from the alphabet to an arbitrary position in $s$ violates $r$-sparsity or induces a copy of $u$. We say that $s$ is $u$-semisaturated if $s$ is $r$-sparse and adding any letter from the alphabet to $s$ violates $r$-sparsity or induces a new copy of $u$. Let the saturation function $\operatorname{Sat}(u, n)$ denote the minimum possible length of a $u$-saturated sequence on an alphabet of size $n$, and let the semisaturation function $\operatorname{Ssat}(u, n)$ denote the minimum possible length of a $u$-semisaturated sequence on an alphabet of size $n$. For alternating sequences, we determine both the saturation function and the semisaturation function up to a constant multiplicative factor. We show for every sequence that the semisaturation function is always either $O(1)$ or $Θ(n)$. For the saturation function, we show that every sequence $u$ has either $\operatorname{Sat}(u, n) \ge n$ or $\operatorname{Sat}(u, n) = O(1)$. For every sequence with $2$ distinct letters, we show that the saturation function is always either $O(1)$ or $Θ(n)$. |
| title | Sequence saturation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.06202 |