tailieunhanh - Báo cáo toán học: "Permutation Reconstruction from Minors"

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@ 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 .