TAILIEUCHUNG - Báo cáo toán học: "The M¨bius function of the o consecutive pattern poset"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The M¨bius function of the o consecutive pattern poset. | The Mobius function of the consecutive pattern poset Antonio Bernini Luca Ferrari Dipartimento di Sistemi e Informatica Dipartimento di Sistemi e Informatica University of Firenze Italy University of Firenze Italy bernini@ ferrari@ Einar Steingrimsson Department of Computer and Information Sciences University of Strathclyde Glasgow G1 1XH UK Submitted Feb 28 2011 Accepted Jun 23 2011 Published Jul 15 2011 Mathematics Subject Classification 05A05 06A07. Abstract An occurrence of a consecutive permutation pattern p in a permutation n is a segment of consecutive letters of n whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the Mobius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases we give a polynomial time algorithm to compute the Mobius function. In particular we show that the Mobius function only takes the values -1 0 and 1. 1 Preliminaries and introduction For the poset of classical permutation patterns the first results about its Mobius function were obtained in SV . Further results appear in ST and BJJS . The general problem in this case of classical patterns seems quite hard. In contrast the poset of consecutive pattern containment has a much simpler structure. In this paper we compute the Mobius function of that poset. In most cases our results give an immediate answer. In the remaining cases we give a polynomial time recursive algorithm to compute the Steingrimsson was supported by grant no. 090038012 from the Icelandic Research Fund. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P146 1 Mobius function. In particular we show that the Mobius function only takes the values 1 0 and 1. An interesting result to note in connection to this is Bjorner s paper Bj on the Mobius function of factor order. Although .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học