TAILIEUCHUNG - Báo cáo toán học: "Matchings and Partial Patterns"

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: Matchings and Partial Patterns. | Matchings and Partial Patterns Vit Jelinek Fakultat fur Mathematik Universitat Wien Garnisongasse 3 1090 Vienna Austria jelinek@ Toufik Mansour Department of Mathematics Haifa University 31905 Haifa Israel toufik@ Submitted May 21 2010 Accepted Nov 14 2010 Published Nov 26 2010 Mathematics Subject Classification Primary 05A18 Secondary 05A05 05A15 Abstract A matching of size 2n is a partition of the set 2n 1 2 . 2n into n disjoint pairs. A matching may be identified with a canonical sequence which is a sequence of integers in which each integer i E n occurs exactly twice and the first occurrence of i precedes the first occurrence of i 1. A partial pattern with k symbols is a sequence of integers from the set k in which each i E k appears at least once and at most twice and the first occurrence of i always precedes the first occurrence of i 1. Given a partial pattern Ơ and a matching p we say that p avoids Ơ if the canonical sequence of p has no subsequence order-isomorphic to Ơ. Two partial patterns T and Ơ are equivalent if there is a size-preserving bijection between T-avoiding and Ơ-avoiding matchings. In this paper we describe several families of equivalent pairs of patterns most of them involving infinitely many equivalent pairs. We verify by computer enumeration that these families contain all the equivalences among patterns of length at most six. Many of our arguments exploit a close connection between partial patterns and fillings of diagrams. 1 Introduction A matching on a vertex set 2n 1 2 . 2n is a partition of 2n into disjoint blocks of size two or equivalently a graph on 2n in which every vertex has degree one. The Supported by grant no. 090038011 from the Icelandic Research Fund and by grant Z130-N13 from the Austrian Science Foundation FWF . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R158 1 number of edges of a matching ụ will be referred to as the order of ụ. The set of matchings on 2n is denoted by Mn. In this .

• 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