Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Reconstructing permutations from cycle minors. | Reconstructing permutations from cycle minors Maria Monks c o Department of Mathematics Massachusetts Institute of Technology Cambridge MA 02139-4307 monks@ Submitted Jul 5 2008 Accepted Jan 27 2009 Published Feb 4 2009 Mathematics Subject Classification 05A05 Abstract 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. 1 Background and Notation For any positive integer n let n denote the set 1 2 3 . ng. Let Sn be the set of all permutations of n . Consider a permutation p 2 Sn and the corresponding sequence p 1 p 2 . p n which we abbreviate p1 p2 . . pn. Definition. Let n 2 p 2 Sn and i 2 n . The ith sequence reduction of p denoted p i is the permutation of n 1 formed by first deleting pk i from the p1 p2 . .pn and then decreasing any number greater than i in the resulting sequence by 1. For instance 13425 3 1324 because we first remove the 3 from 13425 leaving 1425 after which we decrease the 4 and the 5 by 1. We denote by R p the set of all sequence reductions of p and by M p the multiset of all sequence reductions of p. For example R 13425 2314 1234 1324 1342g and M 13425 2314 1234 1324 1324 1342g. Several reconstruction problems related to sequence reductions have been formulated. One such problem asks for which n can any permutation of length n be uniquely reconstructed from its set of sequence reductions. The analogous reconstruction problem for multisets of sequence reductions has also been investigated. Formally these problems are equivalent to asking for which n is the restriction of R or M respectively to Sn an injective map. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 .
