Exploring Partially Ordered Multisets: Definitions, Applications, and Combinatorial Parameters

Abstract

Study’s Excerpt/Novelty

• This paper surveyed comparatively analysed existing orderings on multiset structures, with a particular focus on definitions that result in partial orders, such as those consistent with the Dershowitz-Manna multiset ordering.
• By highlighting the strengths and limitations of these orderings, the study offers critical insights into their applicability in real-world scenarios, including computer programming.
• Additionally, the paper explores generalized combinatorial parameters on ordered multiset structures, providing recommendations for their use in further studies.

Full Abstract

A partially ordered set (S,≼) is a nonempty set S equipped with a partial order ≼. Ordered structures are useful for representing application problems that involve comparable and incomparable parameters or inputs. Ordered sets are studied based on classical set theory, where objects in a collection are assumed to be distinct. However, mathematical objects are not always distinguishable, especially in applications. Multisets are mathematical models of entities with repetition. Multiset theory is distinguished from a set by carrying information on the number of times an element appears in a given collection, making it suitable for modeling real-life situations. A multiset M over S can be formally defined as a cardinal-valued function, M:S→N such that x∈Dom (M) implies M(x) is a cardinal number and M(x)=m_M (x)>0, where m_M (x) denotes the number of times x occurs in M. Multisets generalize the classical sets and are apt for representing partial orders. There has been a growing interest in extending results on ordered sets to multisets. Unlike in classical set theory, there is still no unanimous way of studying foundational concepts in multisets. For instance, different approaches have been proposed for studying orderings on multisets due to the multiplicity parameter that is peculiar to multisets. This paper surveys studies on ordered multisets and compares existing orderings proposed on multiset structures. In particular, cases where the definition results in a partial order are of great interest in this exposition; their properties and theoretical implications make them suitable for application. We focus on definitions consistent with the Dershowitz-Manna multiset ordering, usually the standard multiset ordering, due to their relevance in applications, e.g., in computer programming. The strengths and possible limitations of the multiset orderings presented in this work are highlighted. This would aid in identifying potentially suitable definitions when dealing with studies that involve ordered multisets. Combinatorial parameters that have been studied on ordered multiset structures are also presented in this paper. The generalized notions of these parameters are investigated with some recommendations.