Reconstructing Permutations from Cycle Minors
The ith cycle minor of a permutation p of the set {1,2,…,n} is the permutation formed by deleting an entry i from the decomposition of p into disjoint cycles and reducing each remaining entry larger than i by 1. In this paper, we show that any permutation of {1,2,…,n} can be reconstructed from its s...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89803 |
| _version_ | 1826213897625927680 |
|---|---|
| author | Monks, Maria |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Monks, Maria |
| author_sort | Monks, Maria |
| collection | MIT |
| description | The ith cycle minor of a permutation p of the set {1,2,…,n} is the permutation formed by deleting an entry i from the decomposition of p into disjoint cycles and reducing each remaining entry larger than i by 1. In this paper, we show that any permutation of {1,2,…,n} can be reconstructed from its set of cycle minors if and only if n≥6. We then use this to provide an alternate proof of a known result on a related reconstruction problem. |
| first_indexed | 2024-09-23T15:56:35Z |
| format | Article |
| id | mit-1721.1/89803 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:56:35Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/898032022-09-29T17:10:51Z Reconstructing Permutations from Cycle Minors Monks, Maria Massachusetts Institute of Technology. Department of Mathematics Monks, Maria The ith cycle minor of a permutation p of the set {1,2,…,n} is the permutation formed by deleting an entry i from the decomposition of p into disjoint cycles and reducing each remaining entry larger than i by 1. In this paper, we show that any permutation of {1,2,…,n} can be reconstructed from its set of cycle minors if and only if n≥6. We then use this to provide an alternate proof of a known result on a related reconstruction problem. National Science Foundation (U.S.) (Grant DMS-0447070-001) United States. National Security Agency (Grant H98230-06-1-0013) 2014-09-18T16:13:50Z 2014-09-18T16:13:50Z 2009-02 2008-07 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89803 Monks, Maria. "Reconstructing Permutations from Cycle Minors." Electronic Journal of Combinatorics, Volume 16, Issue 1 (2009). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r19 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Monks, Maria Reconstructing Permutations from Cycle Minors |
| title | Reconstructing Permutations from Cycle Minors |
| title_full | Reconstructing Permutations from Cycle Minors |
| title_fullStr | Reconstructing Permutations from Cycle Minors |
| title_full_unstemmed | Reconstructing Permutations from Cycle Minors |
| title_short | Reconstructing Permutations from Cycle Minors |
| title_sort | reconstructing permutations from cycle minors |
| url | http://hdl.handle.net/1721.1/89803 |
| work_keys_str_mv | AT monksmaria reconstructingpermutationsfromcycleminors |