The aim of this research is to study the theory of partially ordered structures and develop an ordered multiset structure with the intent of extending existing notions and results particularly on certain combinatorial parameters studied for sets, to multisets.

Aim and Objectives of the Study

The aim of this research is to study the theory of partially ordered structures and develop an ordered multiset structure with the intent of extending existing notions and results particularly on certain combinatorial parameters studied for sets, to multisets.

In order to achieve this aim, our main objectives are to:

1. Develop a partially ordered multiset structure that admits hierarchy between the points of a multiset and establish properties satisfied by this
2. Construct substructures of the ordered multiset and investigate their
3. Extend combinatorial parameters of linear extensions, realizers, and dimension to multisets using the structure constructed in i
4. Extend results on these parameters from the set theoretical context to multisets and obtain some new results that are peculiar to ordered
5. Investigate algorithms for constructing linear extensions of a partially ordered set and develop a heuristic algorithm for generating multiset linear extensions to be implemented on a partially ordered multiset

CHAPTER TWO

LITERATURE REVIEW

Partially Ordered Sets and Combinatorial Theory

The theory of ordered sets lies at the confluence of several branches of Mathematics which includes in particular, set theory, lattice theory, combinatorial theory and some aspects of modern operational research. Over the last thirty years, researchers have made considerable efforts towards developing the theory of ordered sets. Partially ordered sets can be said to have their origin in the work of George Boole (1854), An investigation of the laws of thought, while developing an axiomatic theory of propositional logic. In 1883, George Cantor, founder of set theory, envisaged that every set could be well ordered. This well ordering principle for which Cantor could not provide a proof, remained at the heart of the theory of ordinal and cardinal numbers. In 1904, Ernst Zermelo using the axiom of choice, provided a proof of the well ordering theorem.

In 1930, Szpilrajn established a fundamental result in ordered set theory: Every ordering on a set can be extended to a linear ordering. He proved that any order on an ordered set P has at least one linear extension. He also proved a stronger result:  Let  be an order on P and let  be  elements of P such that ||  i.e.,  and  are  incomparable,  then  there  exist  two  linear  extensions of such that and .

Building on Szpilrajn’s results, Dushnik and Miller (1941) showed that every partial order is the intersection of a collection of linear orders. They also defined the dimension of an ordered set P as the minimum cardinality of a realizer of P. Their results showed that there exist partially ordered sets of arbitrarily large dimensions.

Dilworth (1950) established that in a finite ordered set P, the minimum number of chains whose set union is P equals the maximum number of pairwise incomparable elements of P. This classical theorem of Dilworth has played a significant role in motivating research in ordered set theory. Like a number of other results in combinatorics, Dilworth’s theorem is equivalent to Hall’s Marriage theorem, Konig-Egervary theorem, Menger’s theorem and the maxflow-mincut theorem for network flows. Dilworth’s theorem has been extended and modified through deep and detailed investigations by a number of researchers.

Hiraguchi (1951) used Dilworth’s theorem to prove that the dimension of an order never exceeds its width. This results showed that if P is a poset on     points with           , then              ⌊     ⌋.  An analogue of Dilworth’s theorem in the infinite setting was presented by Perles (1963). However, the theorem does not extend so simply to ordered sets with infinite width. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be different from each other. In particular, for every infinite cardinal number there is an infinite ordered set with width whose partition into  the  fewest  chains  has  chains (Harzheim, 2005).

Hansson (1968), proved an analogue of Szpilrajn’s theorem for