A STUDY OF THEORY OF PARTIALLY ORDERED MULTI SETS

Author (s) : Dr. D. Moganraj & V. Vimala

---

Abstract :
During the last three decades, researchers have made significant contributions to the theory of partially ordered sets (posets). In this thesis, partially ordered multisets (pomsets) are studied. These structures generalize sets, bags, list, trees, and other ordered types and therefore provide a uniform representation for them. A study of multiset orderings on the class of finite multisets defined over a set is presented. In order to introduce hierarchies between the points of a finite multiset , a new partial multiset ordering, , is defined via the ordering induced by the partially ordered base set. Properties of the structure , called a partially ordered multiset, are investigated. By restricting the ordering to submsets of , substructures of are constructed. Notions and results on chains and antichains are extended from set theoretical context to multisets. In particular, by exploiting set-based partitioning, a set of necessary and sufficient conditions is proved for characterizing the width and height of a partially ordered multiset, which are extensions of the classical theorem of Dilworth and its dual on partially ordered sets. Also, combinatorial parameters are studied on the ordered multiset structure using a partially ordered base set. The concepts of linear extensions, realizers and dimension of a partially ordered set are extended to the case where the ordered structure is a multiset. It is shown that if are incomparable points in then, there exists a pomset extending such that . This result generalizes Szpilrajn’s extension theorem for partially ordered sets. In the sequel, a heuristic algorithm for generating mset linear extensions is constructed and implemented on a randomly generated ordered multiset. It is also shown that the notion of realizers is well-defined on the ordered multiset structure and ⋂ , where each is an mset linear order on .Finally, the concept of dimension for ordered multisets is defined using the ordering . The relationship between the dimension of a partially ordered multiset and that of the underlying generic set is investigated. Among other results, it is shown that the dimension of an ordered multiset is monotonic and bounded in terms of the dimension of the base set. A multiset can be viewed as an extended notion of a set, hence, establishing these concepts and results on the new partially ordered multiset structure leads to generalizations in the theory of partially ordered sets.

Keywords : partially ordered multisets (pomsets), classical theorem of Dilworth

Conference Date : 30/08/2019

Pages : 344

Paper ID : 19335