Skip Letters for Short Supersequence of All Permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915089615945728 |
|---|---|
| author | Tan, Oliver |
| author_facet | Tan, Oliver |
| contents | A supersequence over a finite set is a sequence that contains as subsequence all permutations of the set. This paper defines an infinite array of methods to create supersequences of decreasing lengths. This yields the shortest known supersequences over larger sets. It also provides the best results asymptotically. It is based on a general proof using a new property called strong completeness. The same technique also can be used to prove existing supersequences which combines the old and new ones into an unified conceptual framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_06306 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Skip Letters for Short Supersequence of All Permutations Tan, Oliver Combinatorics Discrete Mathematics 68R15, 05A05 G.2.1 A supersequence over a finite set is a sequence that contains as subsequence all permutations of the set. This paper defines an infinite array of methods to create supersequences of decreasing lengths. This yields the shortest known supersequences over larger sets. It also provides the best results asymptotically. It is based on a general proof using a new property called strong completeness. The same technique also can be used to prove existing supersequences which combines the old and new ones into an unified conceptual framework. |
| title | Skip Letters for Short Supersequence of All Permutations |
| topic | Combinatorics Discrete Mathematics 68R15, 05A05 G.2.1 |
| url | https://arxiv.org/abs/2201.06306 |