A Study of Recognition and Enumeration for Decomposable Ordered Sets

Abstract

In this research, we consider mainly two repeatedly studied combinatorial problems in the theory of posets (partially ordered sets). The first one, known as the Recognition Problem, is to recognize those classes of posets that satisfy some common structural properties. Here, we give the recognitions of the most computationally tractable classes of posets, namely the decomposable posets. Well-known classes of the decomposable posets are the classes of P -graphs, P - series, and series-parallel posets. Also, we introduce the notions of the classes of factorable posets and composite posets. Due to many computational aspects of the incidence matrices, they have classical applications in recognizing various classes of posets and graphs. For this, we introduce the notion of poset matrix, an incidence matrix, to represent finite posets. Here, we define the order relation in a square (0,1)-matrix and give an association of this matrix to the posets. We show that every poset matrix can be relabeled to an upper (equivalently, lower) triangular matrix that represents a unique poset up to isomorphism. We introduce the notions of the ordinal sum, ordinal product, and composition of matrices. We establish the algebraic interpretations of the direct sum, ordinal sum, Kronecker product, ordinal product, and composition of matrices in the case of poset matrices. We give the matrix recognitions of the classes of P - graphs, P -series, series-parallel posets, factorable posets, and composite posets by using the poset matrix. Finally, we give a matrix recognition of the class of all decomposable posets that generalizes most of the above results regarding the matrix recognitions of posets. viiThe second problem, known as the Enumeration Problem, is to count the number of pairwise nonisomorphic posets with a certain number of elements be- longing to a particular class of posets. Among several methods for the enumera- tion of posets, here, we consider the exact enumeration method. The algorithmic methods for the enumerations of some classes of decomposable posets considered in the previous researches are of type generate-one and count-one. As a result, the running time of these algorithms grows more rapidly even though the posets are significantly small in size. It is mainly due to the recursions in generating pairwise nonisomorphic posets that make these algorithms highly time-complex. Therefore, it was always a great challenge to give polynomial-time algorithms to make some enumeration process time-efficient. Since the generating methods for the decomposable posets seem to consist of the recursive constructions, algorith- mic methods for the enumerations of such posets were ignored by some authors. Here, we give an exact enumeration method for the unlabeled P -series and series- parallel posets by using the poset matrix. In both cases, we give the enumeration of the unlabeled disconnected posets according to the number of connected direct terms of the posets. In the case of the unlabeled connected series-parallel posets, we give the enumeration of the posets according to the number of ordinal terms that are either the singleton or disconnected posets. For these, we use the results regarding the matrix recognitions of the classes of P -series and series-parallel posets. We also give some algorithms to determine the parameters involved in the enumeration formulae, and finally, compute the number of unlabeled posets. We show that these enumeration algorithms have polynomial-time complexities. Moreover, we implement these enumeration algorithms into the computer and obtain the numbers of unlabeled P -series up to 75 elements and the numbers of unlabeled series-parallel posets up to 33 elements.