Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Permutation Reconstruction from Minors. | Permutation Reconstruction from Minors Mariana Raykova Bard College Annandale-on-Hudson NY 12504 USA mr892@bard.edu Submitted Aug 19 2005 Accepted Jul 29 2006 Published Aug 3 2006 Mathematics Subject Classification 05A05 Abstract We consider the problem of permutation reconstruction which is a variant of graph reconstruction. Given a permutation p of length n we delete k of its entries in each possible way to obtain n subsequences. We renumber the sequences from 1 to n k preserving the relative size of the elements to form n k -minors. These minors form a multiset Mk p with an underlying set M k p . We study the question of when we can reconstruct p from its multiset or its set of minors. We prove there exists an Nk for every k such that any permutation with length at least Nk is reconstructible from its multiset of n k -minors. We find the bounds Nk k log2 k and Nk A 2k 4. For the number Nk giving the minimal length for permutations to be reconstructible from their sets of n k -minors we have the bound Nk 2k. We work towards analogous bounds in the case when we restrict ourselves to layered permutations. 1 Introduction The problem of graph reconstruction arose from an unsolved conjecture of Ulam 5 . Consider any two unlabeled simple graphs A and B each with n 3 vertices. Deleting one vertex from A together with its incident edges in each possible way we obtain the minors A1 . An. Similarly obtain minors B1 . Bn of B. Then Ulam s conjecture says that if there exists a bijection a 1 . ng 1 . ng such that Ai is isomorphic to Ba i then A is isomorphic to B. We consider a variation of graph reconstruction introduced by Smith 4 . We apply the construction from the approach in graph reconstruction to permutations. Consider a permutation p with n entries. Delete k of the entries in each possible way to obtain n subsequences of the starting permutation and then renumber them with respect to order so that they become permutations of the numbers from 1 to n k. These .