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.
CHAPTER ONE
INTRODUCTION
1.1 Background of the Study
Mathematical structures are the means to model the way certain mathematical objects are related to each other in a given system. Ordered structures are present throughout mathematics. In view of wide practical applications of orders, numerous special kinds of ordered structures have been developed, some of which have grown into mathematical fields of their own. The origin of partially ordered sets can be traced back to the work: An Investigation of the Laws of Thought of George Boole in 1854 on which are founded the mathematical theories of logic and probabilities. Georg Cantor in 1883 proposed that it was a valid law of thought that every set could be well ordered. However, most mathematicians at the time found it difficult to visualize this fundamental concept. In 1904, Ernst Zermelo proved the well ordering theorem (also known as Zermelo’s theorem) using the axiom of choice. Today, it has come to occupy a central position in developing various other useful ordered structures in order to explicate complex application problems arising in probability theory, combinatorial theory of algorithms, and many algebraic theories. The well-ordering principle makes every set susceptible to the powerful technique of transfinite induction.
1.1.1 Partially ordered sets
Interest in finite partially ordered structures has been heightened in recent years by a steady stream of theorems combining brilliant ad hoc arguments with powerful techniques from other areas of Mathematics (Trotter, 1995).
Partial orders generalize the more familiar total orders. Most application problems are presented such that no relationship exists between some elements of a given system (incomparable elements), hence investigation via partial orders is a more practical approach in explicating real life application problems.
A partially ordered set (or ordered set or poset) is a structure consisting of a set and a binary relation contained in , called the order (or the partial order) on such that, is reflexive, antisymmetric and transitive..
The antisymmetry of the order relation ensures that there are no two-way ties ( and for distinct and ) in the relation. The transitivity (in conjunction with antisymmetry) ensures that no cyclic ties ( for distinct ) exist.
A tool used in describing the covering relation between elements of an ordered set is the order diagram also known as the Hasse diagram (named after the German algebraic number theorist Helmut Hasse, who used diagrams to picture the ordered sets of subfields or field extensions). Order diagrams provide good visual tools for translating real life problems into Mathematics. Such diagrams can represent many structures from everyday life, like public transportation, supply chain, road maps, computer networks, water supply systems, etc. Order diagrams are not canonical, the same ordered set can be drawn in different ways according to the investigator’s preferences or needs as shown in figure 1.1.
Figure 1.1 Three diagrams of the same ordered set (Schroder, 2003)
It is known that various characterizations of subsets of a finite set are the central tools to study combinatorial theory. Much of the combinatorial interest in ordered sets is inextricably linked to the combinatorial features of the diagrams associated with them. Aspects of combinatorics include counting the structures of a given kind and size, deciding when certain criteria can be met, constructing and analyzing objects that meet the criteria (as in combinatorial designs and matroid theory), finding largest, smallest, or optimal objects (extremal combinatorics and combinatorial optimization), and studying combinatorial structures that arise in an algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics). Significant notions of combinatorics are frequently used in many areas of computer science such as scheduling, systems controls, data mining and networking (Rival, 1983; Faigle and Schrader, 1984). A basic problem of combinatorics is to determine the number of possible configurations (for example, graphs, designs, and arrays) of a given type. Though the rules specifying the configuration may be relatively simple, enumeration on the other hand may present formidable difficulties. Finding a good upper and lower bound for a given problem usually gives the best possible solution.
There has been rapid growth in research activity centered on combinatorial problems for partially ordered sets, an evidence of this is the introduction of the AMS subject classification 06A07: Combinatorics of Partially Ordered Sets (Trotter, 1996).
Any partially ordered set can be sorted into a linear order maintaining all preexistent relations. Linear orders correspond to our intuition of sorted list of elements.
A linear extension of a finite partially ordered set is an order-preserving bijection { | |} such that in implies . The set of linear extensions of P can be viewed as a set of permutations of the elements of P. Many combinatorial objects can be represented by permutations subject to various restrictions. Following the fundamental results of Szpilrajn in Sur l’extension de l’ordre partiel, numerous works have appeared on linear extensions (also known as topological sorts) of partially ordered sets (Bouchitte and Habib, 1987; Bertet et al., 2003; Fernandez et al., 2013; Tella et al., 2014B). The concept of linear extensions of a partially ordered set has been employed in solving a wide class of application problems which includes the classical matroid secretary problem. This concept is also found useful in solving problems like the scheduling problem (or jump number problem) (Rival 1983; Faigle and Schrader, 1984; Ehrenborg et al., 2011) by providing an embedding of the partial order into a linear order. For optimization, different classes of linear extensions have been studied in the literature, this include, greedy linear extensions (Cogis and Habib, 1979; Rival and Zaguia, 1987; Syslo, 1995) and super greedy linear extensions (Kierstead et al., 1987; Kierstead and Trotter, 1989). This is achieved mainly by placing certain restrictions on the methods by which the linear extensions can be constructed. Figure 1.1 is an order diagram of an ordered set and some of its linear extensions. There has been a good deal of interest in the maximal sized antichains of a partially ordered set (Freese, 1974; Behrendt, 1988). Besides its theoretical
interest, the abstraction of maximal antichains of an ordered set has structural properties which gives it interesting practical behaviors. These substructures play a significant role in characterizing ordered sets.
Figure 1.2 A partially ordered set and its linear extensions.
Various algorithms have been developed for generating the linear extensions of partially ordered sets (Bianco et al., 1997; Korsh and Lafollete, 2002; Felsner et al., 2003; Chen, 2006). Figure 1.2 is an order diagram of a partially ordered set and some of its linear extensions. Algorithmically, every linear extension { } of a partially ordered set can be constructed through the following steps:
1. Choose a minimal element in .
2. Given , choose a minimal element from { } and call this element .
For any sequence of choices of the points , the above algorithm produces a linear extension of the partially ordered set . In his work, Szpilrajn (1930) also showed that every ordered set on a set is the intersection of a set of linear orders on . A family of such linear orders is called a realizer of . In figure 1.3, the linear orders on the right form a realizer for the order diagram on the left.
Figure 1.3 A partially ordered set and its realizer.
An interesting parameter of an ordered set is the minimum number of linear extensions needed to characterize it i.e., the dimension of an ordered set. Dushnik and Miller (1941) defined the dimension of an ordered set as the least positive integer for which has a realizer of size . As observed by Trotter (2017), it is arguably true that dimension is the single most widely studied combinatorial parameter for ordered sets. Dimension for partially ordered sets plays a role which in many instances is analogous to chromatic number for graphs. A natural extension of this concept arises if the linear orders which form a realizer of are required to have certain additional properties. The dimension of a partially ordered set is a comparability invariant i.e., two partially ordered sets with the same comparability graph have the same dimension. Several characterizations are known for the dimension of an ordered set (Kelly and Trotter, 1982; Kierstead and Trotter, 1985; Trotter and Wang 2015; Joret et al., 2016A, 2016B).
The standard example for is the height 2 partially ordered set consisting of minimal elements { } and maximal elements { } with in if and only if
. It is well known that dimension of for all . Furthermore, for , is irreducible, i.e., the removal of any point leaves a subposet whose dimension is (Trotter and Wang, 2015). The standard example plays a prominent role in many characterization problems for ordered sets. The presence of a large standard example as a subposet is enough to force the dimension to be large, but the converse need not be true. The standard example also shows that in general, a partially ordered set with large height does not necessarily have large dimension. Figure 1.4 is a diagram of the standard example .
In recent years, researchers have shown renewed interest in combinatorial properties of ordered sets determined by geometric properties of its order diagram and topological properties of its cover graph (Trotter and Wang, 2015). The roots for these problems can be traced back to the 1970’s (Trotter and Moore, 1977) and sometimes even earlier.
…
…
Figure 1.4 The standard example (Kelly and Trotter, 1982)
1.1.2 Partially ordered multisets
In a classical (or Cantorian) set, two mathematical objects are either equal or different. Howbeit, in real life applications mathematical objects are not necessarily distinct. For instance, repeated roots of a polynomial equation, repeated observations in a statistical sample and repeated
hydrogen atoms in a water molecule to mention a few. If repeated occurrences of any object is allowed in a set, then a mathematical structure known as a multiset (mset, for short) is obtained. This type of structure plays an important role in the area of applications. A multiset is considered to be a generalization of a set. Formally, a multiset over is a cardinal-valued function i.e., { }, also called a generalized characteristic function, where is a set called the ground or generic set of the class of all multisets containing objects from (Singh and Isah, 2016). In view of various applications of multisets in areas such as logic, linguistics, computer science, just to mention a few, it became a part of research problem to extend results already obtained in set theoretical context to multisets. The problem of extending various mathematical notions and results related to ordered sets to multisets has attracted serious attention during the last couple of decades (Singh and Singh, 2003; Kilibarda and Jovovic, 2004; Conder and Slinko, 2007; Singh et al., 2012; Thanh, 2013). A relatively early contribution in this line of research is the work of Dershowitz and Manna (1979). For two multisets in i.e., the class of all finite msets over a set , the Dershowitz-Manna multiset ordering is presented as follows:
if there exist two multisets in such that,
i.
ii. , and
iii. dominates , that is, for all , there is some such that .
The Dershowitz-Manna ordering otherwise known as the standard multiset ordering seems to form the basis of all other multiset orderings. Several definitions of multiset orderings have been proposed building on this ordering, each embodying certain limitations and advantages over others (Huet and Oppen, 1980; Jouannaud and Lescanne 1982; Martin 1989). Well-founded
partial orderings on the set of all finite multisets are employed in proving program termination (Bachmair et al., 1986; Dershowitz and Manna, 1979), also in the theory of partitions (Brandt, 1982).
The term partially ordered multisets (pomsets, for short) was proposed by Pratt (1984). A partially ordered multiset relation is a multiset relation that is reflexive, antisymmetric, and transitive. Intuitively, a partially ordered multiset can be viewed as a string in which the total order has been relaxed to be a partial order. As proposed by a number of researchers, partially ordered multisets can be used as mathematical representations of runs of a concurrent system (Pratt, 1986; Gischer, 1988).
1.2 Statement of the Problem
The theory of partially ordered structures is relatively well developed in the classical setting. Owing to applications of multisets in both hard and soft sciences, many researches have appeared on extending notions and results related to orders obtained on sets to multisets. This problem has attracted the attention of a large number of researchers during the last couple of decades (Dershowitz and Manna, 1979; Prat, 1986; Kilibarda and Jovovi, 2004; Girish and Sunil, 2009; Singh et al., 2012).
Nevertheless, a number of problems related to extending many applicable notions and results established on ordered sets to multisets, require further serious attention; for example, developing rich ordered multiset structures and identifying their characteristic properties, including their computational aspects for application, hence the need for a partially ordered multiset structure that is suitable for establishing these concepts.
1.3 Justification of the Study
The Cantorian set theory has provided a firm foundation for bivalent logic based mathematics in which all variables as well as relations between variables are crisp. However, this demand of the Cantorian set embodies certain limitations. Repetition of elements is significant in a multiset structure, hence a multiset can be viewed as an extended notion of the Cantorian set. The significance of allowing duplicates in a collection cannot be overemphasized. The concept of multiple-membership collections has found applications in various areas such as logic, linguistics, computer science, just to mention a few. Researchers have turned to partial orders in order to understand the semantics of parallel programs. Partially ordered structures have usages in ranking scenarios where certain pairs of elements are incomparable, such as ranking conference submissions, also, the combined use of duplicates with partial order is natural in practical data. Notably, partially ordered multisets have various applications in computer science ranging from database systems to distributed computing. Numerous advanced applications such as CAD/CAM, software engineering and text retrieval require such data types. Partially ordered multisets are also common in geographical information systems and linguistics.
1.4 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:
i. Develop a partially ordered multiset structure that admits hierarchy between the points of a multiset and establish properties satisfied by this structure.
ii. Construct substructures of the ordered multiset and investigate their properties.
iii. Extend combinatorial parameters of linear extensions, realizers, and dimension to multisets using the structure constructed in i above.
iv. Extend results on these parameters from the set theoretical context to multisets and obtain some new results that are peculiar to ordered multisets.
v. 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 structure.
1.5 Methodology
To develop the partially ordered multiset structure , the multiset i.e., the class of finite multisets over a set , is defined over a partially ordered base set such that the ordering on the base set induces an ordering on .
Substructures of are constructed by restricting the ordering to submsets of . Properties of these substructures are investigated through the defined suborder. Set-based partitioning studied in Jouannaud and Lescanne (1982) is exploited in establishing conditions for characterizing the width and height of the ordered multiset and hence partitioning into
minimum number of mset chains and mset antichains. Due to the well-ordering principle, the proofs follow using the method of transfinite induction.
Combinatorial parameters of mset linear extensions, mset realizers and dimension are established on the ordered multiset structure via the ordering induced by the partially ordered base set. Characterizations for these parameters are obtained by bounding them in terms of their corresponding classical parameters and other comparability invariants. Mset linear extensions are generated by sorting the ordered multiset into a linear order while maintaining all preexistent relations.
1.6 Organization of the Thesis
The thesis consists of six chapters organized as follows:
Besides chapter one, a comprehensive and up-to-date literature review of related works is presented in chapter two. In chapter three, fundamentals of partially ordered sets and multisets are discussed. A comprehensive review on multiset orderings is also presented in this chapter. In chapter four, a partially ordered multiset structure is constructed using a partially ordered base set and exploiting the ordering induced by the underlying generic set. Notions of comparability and incomparability are defined, also, properties satisfied by this ordered structure are presented. In the sequel, substructures are introduced, and some related results on ordered sets are established on the ordered multiset structure. In chapter five, combinatorial notions on partially ordered sets are extended to ordered multisets. A new heuristic algorithm and an exact algorithm for generating mset linear extensions are constructed and implemented on a randomly generated ordered multiset. In chapter six, summary, conclusions and recommendations for further study are presented.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
