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: Reduced Decompositions of Matchings. | Reduced Decompositions of Matchings Lun Lv School of Sciences Hebei University of Science and Technology Shijiazhuang 050018 . China klunlv@ Sabrina . Pang College of Mathematics and Statistics Hebei University of Economics and Business Shijiazhuang 050061 . China stpangxingmei@ Submitted Dec 28 2010 Accepted Apr 30 2011 Published May 8 2011 Mathematics Subject Classifications 05A05 05A19 Abstract We give a characterization of matchings in terms of the canonical reduced decompositions. As an application the canonical reduced decompositions of 12312-avoiding matchings are obtained. Based on such decompositions we find a bijection between 12312-avoiding matchings and ternary paths. 1 Introduction A matching on a set 2n 1 2 . 2n is a graph on 2n in which every vertex has degree one. The set of matchings on 2n is denoted by Mn. Note that Mn 2n 1 1 3 5 2n 1 . The linear representation of a matching is obtained by drawing 2n points in the plane lying on a horizontal line and connecting them by n arcs such that each arc connects two of the points and lies above the points. Fig. 1 gives the linear representation of the matching 1 3 2 4 5 6 . In this paper we always use the canonical sequential form 13 of a matching on the set 2n which is a permutation of the multiset 1 1 2 2 . n n obtained in the following way. Draw the linear representation of the matching and label the arcs with the numbers Corresponding author THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P107 1 1 2 3 4 5 6 Figure 1 Linear representation. 1 2 . n ordered by their leftmost endpoints. Then label each endpoint with the label of the adjacent arc and read the labels of the endpoints from left to right. For example the matching in Fig. 1 can be also displayed by 121233. Let n and T be two sequences. We say n avoids T or is T-avoiding whenever n does not contain a subsequence with all of the same pairwise comparisons as T. For example the sequence 12342143 is 12123-avoiding but
