tailieunhanh - Báo cáo khoa học:Dominance Order and Graphical Partitions

We gave a new criterion for graphical partitions. We derive a new recursion formula, which allows the computation of the number g(n) of graphical partitions of weight n for up to n partition of weight n is a nonincreasing sequence of nonnegative integers (1, 2, . . . , k, . . .) whose sum is n. The weight is denoted by ||. The number of nonzero elements in the sequence is the length of the partition denoted by l( ). The set of all partitions of weight n is denoted by P(n). | Dominance Order and Graphical Partitions Axel Kohnert Lehrstuhl Mathematik II University of Bayreuth 95440 Bayreuth Germany Submitted Mar 5 2003 Accepted Aug 18 2003 Published Mar 5 2004. MR Subject Classifications 05A17 05C07 Abstract We gave a new criterion for graphical partitions. We derive a new recursion formula which allows the computation of the number g n of graphical partitions of weight n for up to n 900. 1 Introduction A partition X of weight n is a nonincreasing sequence of nonnegative integers Al X2 . Xk . whose sum is n. The weight is denoted by A . The number of nonzero elements in the sequence is the length of the partition denoted by l X . The set of all partitions of weight n is denoted by P n . The number of partitions of weight n is denoted by p n . There is one partition of weight 0 it is the partition of length 0. A partition is called graphical if it is the degree sequence of an undirected simple graph. As each edge is the graph is counted twice a graphical partition must be of even weight. The partition of weight 0 is graphical as it corresponds to a graph without edges. The set of graphical partitions of weight n is denoted by G n . The number of graphical partitions is denoted by g n . A partition X is visualized using the Ferrer s diagram Fx . an array of Xi left justified boxes in the i-th row of the first quadrant of the plane. The number of boxes on the main diagonal of the Ferrer s diagram Fx is the Durfee size of the partition and denoted by d X . The subpartition built from the d X X d X boxes is called the Durfee square of the partition X. If we count the number of boxes in each column of the Ferrer s diagram Fx we get again a partition which is THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N4 1 called the conjugate partition and is denoted by X . There are several partial orders on the set of all partitions. We are interested in the dominance order. A partition X is dominated by the partition g .