tailieunhanh - Báo cáo toán học: "Determining Lower Bounds for Packing Densities of Non-layered Patterns Using Weighted Templates"

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: Determining Lower Bounds for Packing Densities of Non-layered Patterns Using Weighted Templates. | Determining Lower Bounds for Packing Densities of Non-layered Patterns Using Weighted Templates Cathleen Battiste Presutti Department of Mathematics Bryn Mawr College Bryn Mawr Pennsylvania USA Ohio University - Lancaster Lancaster Ohio USA battiste@ Submitted Sep 24 2007 Accepted Mar 17 2008 Published Mar 27 2008 Mathematics Subject Classifications 05A16 Abstract The packing density of a permutation pattern is the limiting value n 1 of the maximum proportion of subsequences of Ơ 2 Sn that are order-isomorphic to . We generalize methods for obtaining lower bounds for the packing density of any pattern and demonstrate the methods usefulness when patterns are non-layered. 1 Introduction The permutation 52134 contains five subsequences 523 524 513 514 534 that are order-isomorphic . have the same relative order to the permutation 312. In this situation we can call the permutation 312 a pattern. In 1992 Herb Wilf first introduced the study of pattern containment during his address to the SIAM meeting on Discrete Mathematics. Since then there has been a great deal of published results on pattern containment that deal with pattern avoidance or the enumeration of permutations that do not contain any occurrences of a particular pattern. However there is significantly less research on pattern containment involving permutations that contain the greatest number of subsequences which are order-isomorphic to a given pattern commonly known as the packing density. Virtually all of this research has focused on a specific type of pattern known as layered patterns. Then in 2002 Albert Atkinson Handley Holton Stromquist hereafter referred to as AAHHS 1 determined a lower bound for the packing density of the non-layered pattern 2413 by using the permutation Ơ 35827146 which contains a relatively large number of 2413-occurrences. In this paper we will improve this lower bound and introduce a generalized method involving weighted templates as a way for computing lower bounds