The maximal length of a k-separator permutation
A permutation σ ∈ S[subscript n] is a k-separator if all of its patterns of length k are distinct. Let F(k) denote the maximal length of a k-separator. Hegarty (2013) showed that k + ⌊√2k − 1⌋ − 1 ≤ F(k) ≤ k + ⌊√2k − 3⌋, and conjectured that F(k) = k + ⌊√2k − 1⌋ − 1. This paper will strengthen the u...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91153 |
| _version_ | 1811074366936449024 |
|---|---|
| author | Gunby, Benjamin P. |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Gunby, Benjamin P. |
| author_sort | Gunby, Benjamin P. |
| collection | MIT |
| description | A permutation σ ∈ S[subscript n] is a k-separator if all of its patterns of length k are distinct. Let F(k) denote the maximal length of a k-separator. Hegarty (2013) showed that k + ⌊√2k − 1⌋ − 1 ≤ F(k) ≤ k + ⌊√2k − 3⌋, and conjectured that F(k) = k + ⌊√2k − 1⌋ − 1. This paper will strengthen the upper bound to prove the conjecture for all sufficiently large k (in particular, for all k ≥ 320801). |
| first_indexed | 2024-09-23T09:47:56Z |
| format | Article |
| id | mit-1721.1/91153 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:47:56Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/911532022-09-26T13:48:19Z The maximal length of a k-separator permutation Gunby, Benjamin P. Massachusetts Institute of Technology. Department of Mathematics Gunby, Benjamin P. A permutation σ ∈ S[subscript n] is a k-separator if all of its patterns of length k are distinct. Let F(k) denote the maximal length of a k-separator. Hegarty (2013) showed that k + ⌊√2k − 1⌋ − 1 ≤ F(k) ≤ k + ⌊√2k − 3⌋, and conjectured that F(k) = k + ⌊√2k − 1⌋ − 1. This paper will strengthen the upper bound to prove the conjecture for all sufficiently large k (in particular, for all k ≥ 320801). United States. Dept. of Energy. Division of Materials Sciences and Engineering (Grant 1062709) United States. National Security Agency (Grant H98230-11-1-0224) 2014-10-23T16:57:43Z 2014-10-23T16:57:43Z 2014-08 2013-09 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/91153 Gunby, Benjamin. "The maximal length of a k-separator permutation." The Electronic Journal of Combinatorics Volume 21, Issue 3 (2014). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p19 Electronic Journal of Combinatorics Creative Commons Attribution http://creativecommons.org/ application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Gunby, Benjamin P. The maximal length of a k-separator permutation |
| title | The maximal length of a k-separator permutation |
| title_full | The maximal length of a k-separator permutation |
| title_fullStr | The maximal length of a k-separator permutation |
| title_full_unstemmed | The maximal length of a k-separator permutation |
| title_short | The maximal length of a k-separator permutation |
| title_sort | maximal length of a k separator permutation |
| url | http://hdl.handle.net/1721.1/91153 |
| work_keys_str_mv | AT gunbybenjaminp themaximallengthofakseparatorpermutation AT gunbybenjaminp maximallengthofakseparatorpermutation |