PartiallyOrderedSets/PartiallyOrderedSet

All Products Maple MapleSim

Home : Support : Online Help : PartiallyOrderedSets/PartiallyOrderedSet

PartiallyOrderedSets

PartiallyOrderedSet

creates a poset

	Calling Sequence
	PartiallyOrderedSet(S,C) PartiallyOrderedSet(S,C,reflopts) PartiallyOrderedSet(S,M) PartiallyOrderedSet(S,M,inputopts,reflopts) PartiallyOrderedSet(S,L) PartiallyOrderedSet(S,L,inputopts,reflopts) PartiallyOrderedSet(G) PartiallyOrderedSet(G,inputopts,reflopts)

Parameters

S	-	set
C	-	binary comparison function that compares two elements and returns a boolean
M	-	Matrix
L	-	list
G	-	GraphTheory:-Graph
reflopts	-	(optional) option of the form reflexive = r, where r is checktrue, checkfalse, checkeither, or useclosure
inputopts	-	(optional) option of the form input = i, where i is transitiveclosure or transitivereduction

Options

•	reflexive = checktrue, checkfalse, checkeither (default), or useclosure

If the option reflexive = checktrue (resp. reflexive = checkfalse) is used, the poset will be checked for reflexivity (resp. antireflexivity) and return an error if the condition is unmet.

If the option reflexive = checkeither is used (the default), Maple will check if the poset meets either condition, and produce an error if neither is met.

If the option reflexive = useclosure is used, no checks are applied; the relation will be adjusted to make every element relate to itself.

In each case, the relation that is stored and used in computations is the reflexive closure of the relation given.

•	input = transitiveclosure (default) or transitivereduction

If the option input = transitiveclosure (resp. input = transitivereduction) is used, Maple will verify that the specified relation is the transitive closure (resp. transitive reduction) of a partial ordering, and issue an error if the condition is unmet.

Description

•	The command PartiallyOrderedSet(S,C) returns the partially ordered set P whose elements are the members of S and relations as defined by the function C.

•	The command PartiallyOrderedSet(S,M) returns the partially ordered set P whose elements are the members of S and relations as defined by the adjacency matrix M.

•	The command PartiallyOrderedSet(S,L) returns the partially ordered set P whose elements are the members of S and relations as defined by the adjacency list L.

•	The command PartiallyOrderedSet(G) returns the partially ordered set P whose elements are the vertices of G and relations as defined by the edges in G. Any such edges must be directed, otherwise an error is issued.

Assumptions

•	The elements of L must be members of S. Otherwise, an error is raised.

Remarks

•	A poset object encoding a poset P records two attributes: a list of the elements of P and a representation of the relation between elements of P. This representation can be stored as a binary relation, adjacency list, and/or adjacency matrix.

•	These relational representations are used to speedup certain computations such as those required by the commands MaximalChains and MaximalAntichains.

Terminology

•	A non-strict partial order, often simply termed partial order is a homogeneous binary relation <= on a set P that is reflexive, anti-symmetric, and transitive.

•	A strict partial order is a homogeneous binary relation < on a set P that is irreflexive, anti-symmetric, and transitive.

•	We observe that every non-strict partial order can be converted trivially into a strict partial order, and vice versa. In what follows, we use the term partial order refers to non-strict partial order.

•

A partially ordered set, or poset for short, is a pair (P, <=) where P is a set and <= is a partial order on P. The poset (P, <=) defines a directed graph whose vertices are the elements of P and (a,b) is a directed edge whenever a <= b holds. Conversely, a poset can be defined from a directed graph, assuming that the defined binary relation is anti-symmetric, and transitive, and, either reflexive, or irreflexive. Consequently, a poset can be given by an adjacency list or an adjacency matrix of a directed graph. In practice, it is also convenient to define its transitive reduction, see this latter term below.

•	We say that two posets are equal (resp. isomorphic) whenever they are equal (resp. isomorphic) as directed graphs.

•	The connected components of a poset are the connected components of its associated directed graph

•	From now on, we fix a poset (P, <=). Two elements a and b of P are said comparable if either a <= b or b <= a holds, otherwise a and b are said incomparable.

•	The partial order <= is said total whenever any two elements of P are comparable.

•	A subset C of P is called a chain if any two elements of C are comparable. A chain C of P is said maximal if P does not admit another chain D of which C would be a proper subset.

•	A subset C of P is called an antichain if any two distinct elements of C are incomparable. An antichain C of P is said maximal if P does not admit another antichain D of which C would be a proper subset. We note that any singleton of P is both a chain and an antichain.

•	The element a of P is strictly less than the element b of P if a <= b and a \342\211\240 b both hold.

•	The element b of P covers the element a of P if a is strictly less than b and for no element c of P, distinct from both a and b, both a <= c and c <= b hold.

•	The relation b covers a defines a homogeneous binary relation on P which is the transitive reduction of (P, <=). This is also a directed acyclic graph on P often refers as the Hasse diagram of (P, <=).

•	Let S be a subset of P and a be an element of S. We say that a is a greatest element (resp. least element) of S if for every element b of S we have b <= a (resp. a <= b). Observe that if S has a greatest element (resp. least element) then it is unique.

•

The element a of P is a maximal element of (P, <=) if for no element b of P the element a is strictly less than b. The element a of P is a minimal element of (P, <=) if no element b of P is strictly less than a. Observe that if P is not empty then it necessarily admits at least one maximal element and at least one minimal element. Observe also that if P admits a greatest (least) element, then this element is its unique maximal (resp. minimal) element.

•	Let S be a subset of P and a be an element of P. We say that a is an upper bound (resp. lower bound) of S if if for every element b of S we have b <= a (resp. a <= b). Observe that a need not be in S in order to be an upper bound (resp. lower bound) of S.

•	We say that a is the infimum of S, or the greatest lower bound of S, if a is the greatest element among all lower bounds of S.

•	We say that a is the supremum of S, or the lest upper bound of S, if a is the least element among all upper bounds of S.

•	From now on, we assume that P is finite.

•

A chain decomposition of the poset (P, <=) is a partition of P into disjoint chains. Dilworth's theorem states that the cardinality of an antichain with maximum cardinality is equal to the cardinality of a chain decomposition of minimum cardinality. This common number is by definition the width of the poset (P, <=).

•

An antichain decomposition of the poset (P, <=) is a partition of P into disjoint antichains. Mirsky's theorem states that the cardinality of a chain with maximum cardinality is equal to the cardinality of antichain decomposition of minimum cardinality. This common number is by definition the height of the poset (P, <=).

•	We call rank function on the poset (P, <=) any function r defined on P, taking integer values and so that for any two elements a and b of P, if b covers a then r(b) = r(a) + 1 holds.

•	The poset (P, <=) is said graded if it admits a rank function.

•	The poset (P, <=) is said ranked if all its maximal chains have the same cardinality.

•	We note that the terms graded poset and ranked poset have slightly different definitions in some textbooks, like the ones of Richard Stanley. We refer to the wikipedia pages of ranked poset and graded poset for a discussion on these terminology issues.

•	The poset (P, <=) is said a meet-semilattice if for any two elements a and b of P the {a, b} admits a greatest lower bound. The poset (P, <=) is said a join-semilattice if for any two elements a and b of P the {a, b} admits admits a least upper bound.

•	The poset (P, <=) is said a lattice if it is both a join- and a meet-semilattice. If (P, <=) is a lattice, then every non-empty subset S of P has a least upper bound and a greatest lower bound.

•

The faces of any polyhedral set Q, ordered by set theoretic inclusion, form a lattice L which enjoys three important properties (that are not true in general for an arbitrary lattice): (1) L is graded, (2) L is ranked, and (3) if the ranks of two faces a > b differ by 2, then there are exactly 2 faces that lie strictly between a and b.

•	The poset (P, <=) is said to be a face lattice if it is isomorphic to the lattice of the faces of a polyhedral set

Examples

>	$with (PartiallyOrderedSets) &colon;$

Create a poset from a set and a non-strict partial order

>	$V ≔ \emptyset &colon;$ $leq ≔ `<=` &colon;$ $empty_poset ≔ PartiallyOrderedSet (V, leq)$

$empty_poset ≔ < a poset with 0 elements >$

(1)

Create a poset from a set and a non-strict partial order

>	$S ≔ \{1, 2, 3, 4, 5\} &colon;$ $poset1 ≔ PartiallyOrderedSet (S, leq)$

$poset1 ≔ < a poset with 5 elements >$

(2)

Display this poset

>	$DrawGraph (poset1)$

Create a poset from a set and a strict partial order

>	$lneq ≔ `<` &colon;$ $poset1_1 ≔ PartiallyOrderedSet (S, lneq)$

$poset1_1 ≔ < a poset with 5 elements >$

(3)

Display this poset

>	$DrawGraph (poset1_1)$

Create a poset from a set and a non-strict partial order

>	$divisibility ≔ (x, y) \mapsto irem (y, x) = 0 &colon;$ $T ≔ \{3, 4, 5, 6, 7, 8, 9\} &colon;$

>	$poset2 ≔ PartiallyOrderedSet (T, divisibility, reflexive = checkeither)$

$poset2 ≔ < a poset with 7 elements >$

(4)

Display this poset

>	$DrawGraph (poset2)$

Create a poset from a set and a strict partial order

>	$divisibNE ≔ (x, y) \mapsto irem (y, x) = 0 and y \neq x &colon;$

>	$poset2_1 ≔ PartiallyOrderedSet (T, divisibNE, reflexive = checkfalse)$

$poset2_1 ≔ < a poset with 7 elements >$

(5)

Display this poset

>	$DrawGraph (poset2_1)$

Create a poset from a set and a non-strict partial order

>	$U ≔ \{1, 2, 3\} &colon;$

>	$poset3 ≔ PartiallyOrderedSet (U, leq, reflexive = checktrue)$

$poset3 ≔ < a poset with 3 elements >$

(6)

Display this poset

>	$DrawGraph (poset3)$

Create a poset from a set and a strict partial order

>	$poset3_1 ≔ PartiallyOrderedSet (U, lneq, reflexive = useclosure)$

$poset3_1 ≔ < a poset with 3 elements >$

(7)

Display this poset

>	$DrawGraph (poset3_1)$

Create a poset from a set and a non-strict partial order

>	$X ≔ \{4, 5, 6\} &colon;$ $poset3_2 ≔ PartiallyOrderedSet (X, leq, reflexive = checktrue)$

$poset3_2 ≔ < a poset with 3 elements >$

(8)

Display this poset

>	$DrawGraph (poset3_2)$

Create a poset from a set and an adjacency matrix of a partial order regarded as a directed graph

>	$adjMatrix4 ≔ Matrix ([[1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]])$

$adjMatrix4 ≔ [\begin{array}{c} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{array}]$

(9)

>	$poset4 ≔ PartiallyOrderedSet (convert (S,'list'), adjMatrix4)$

$poset4 ≔ < a poset with 5 elements >$

(10)

Display this poset

>	$DrawGraph (poset4)$

Create a poset from a set and an adjacency list of a partial order regarded as a directed graph

>	$adjList5 ≔ map2 (map, `+`, Array ([\{1, 4, 7\}, \{2, 6\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}]), 2)$

$adjList5 ≔ [\begin{array}{c} \{3, 6, 9\} & \{4, 8\} & \{5\} & \{6\} & \{7\} & \{8\} & \{9\} \end{array}]$

(11)

>	$poset5 ≔ PartiallyOrderedSet (convert (T,'list'), adjList5)$

$poset5 ≔ < a poset with 7 elements >$

(12)

Display this poset

>	$DrawGraph (poset5)$

Create a poset from a set and a directed graph

>	$G ≔ GraphTheory :- Graph (directed, [1, 2, 3, 4, 5, 6], \{[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 2], [2, 4], [2, 6], [3, 3], [3, 5], [3, 6], [4, 4], [4, 6], [5, 5], [5, 6], [6, 6]\})$

$G ≔ Graph 1: a directed graph with 6 vertices, 11 arcs, and 6 self-loops$

(13)

>	$poset6 ≔ PartiallyOrderedSet (G)$

$poset6 ≔ < a poset with 6 elements >$

(14)

Display this poset

>	$DrawGraph (poset6)$

Create a poset from a set an adjacency matrix of the transitive reduction of a partial order on that set

>	$poset7 ≔ PartiallyOrderedSet (convert (U,'list'), ⟨⟨1 \| 1 \| 0⟩, ⟨0 \| 1 \| 1⟩, ⟨0 \| 0 \| 1⟩⟩, input = transitivereduction)$

$poset7 ≔ < a poset with 3 elements >$

(15)

Display this poset

>	$DrawGraph (poset7)$

Create a poset from a set and an adjacency list of the transitive reduction of a partial order on that set

>	$poset8 ≔ PartiallyOrderedSet ([1, 2, 3, 4, 5, 6], Array ([\{1, 2, 3\}, \{2, 4\}, \{3, 5\}, \{4, 6\}, \{5, 6\}, \{6\}]), input = transitivereduction)$

$poset8 ≔ < a poset with 6 elements >$

(16)

Display this poset

>	$DrawGraph (poset8)$

Create a poset from a set and an adjacency list of the transitive closure of a partial order on that set

>	$poset8b ≔ PartiallyOrderedSet ([1, 2, 3, 4, 5, 6], Array ([\{1, 2, 3, 4, 5, 6\}, \{2, 4, 6\}, \{3, 5, 6\}, \{4, 6\}, \{5, 6\}, \{6\}]), input = transitiveclosure)$

$poset8b ≔ < a poset with 6 elements >$

(17)

Display this poset

>	$DrawGraph (poset8b)$

Define a polyhedral set and get its dimension

>	$t ≔ PolyhedralSets :- ExampleSets :- Octahedron ()$

$t ≔ {\begin{array}{l} Coordinates & &colon; & [x_{1}, x_{2}, x_{3}] \\ Relations & &colon; & [- x_{1} - x_{2} - x_{3} \leq 1, - x_{1} - x_{2} + x_{3} \leq 1, - x_{1} + x_{2} - x_{3} \leq 1, - x_{1} + x_{2} + x_{3} \leq 1, x_{1} - x_{2} - x_{3} \leq 1, x_{1} - x_{2} + x_{3} \leq 1, x_{1} + x_{2} - x_{3} \leq 1, x_{1} + x_{2} + x_{3} \leq 1] \end{array}$

(18)

>	$d ≔ PolyhedralSets :- Dimension (t)$

$d ≔ 3$

(19)

Collect the faces of this polyhedral set

>	$t_faces ≔ \{seq (op (PolyhedralSets :- Faces (t, dimension = i)), i = - 0 .. d)\} &colon;$

>	$t_faces ≔ t_faces union \{PolyhedralSets :- ExampleSets :- EmptySet (d)\} &colon;$

>	$FL ≔ convert (t_faces, list) &colon;$

Construct the face lattice of that polyhedral set

>	inclusion := proc(x,y) PolyhedralSets:-`subset`(FL[x],FL[y]) end proc:

>	$polyhedral_poset ≔ PartiallyOrderedSet (\{seq (i, i = 1 .. nops (FL))\}, inclusion)$

$polyhedral_poset ≔ < a poset with 28 elements >$

(20)

Display this poset

>	$DrawGraph (polyhedral_poset)$

Create a poset from a set and an adjacency matrix of a partial order regarded as a directed graph

>	$M ≔ Matrix ([[1, 1, 1, 1, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]) &colon;$

>	$poset9 ≔ PartiallyOrderedSet ([seq (1 .. 5)], M)$

$poset9 ≔ < a poset with 5 elements >$

(21)

Display this poset

>	$DrawGraph (poset9)$

Create a poset from a set and a non-strict partial order

>	$Z ≔ \{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}$

$Z ≔ \{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}$

(22)

>	$poset10 ≔ PartiallyOrderedSet (Z, divisibility)$

$poset10 ≔ < a poset with 12 elements >$

(23)

Display this poset

>	$DrawGraph (poset10)$

Create a poset from a set and a non-strict partial order

>	$ZZ ≔ \{1, 2, 3, 4, 5, 6, 12, 15, 60\}$

$ZZ ≔ \{1, 2, 3, 4, 5, 6, 12, 15, 60\}$

(24)

>	$poset11 ≔ PartiallyOrderedSet (ZZ, divisibility)$

$poset11 ≔ < a poset with 9 elements >$

(25)

Display this poset

>	$DrawGraph (poset11)$

References

Richard P. Stanley: Enumerative Combinatorics 1. 1997, Cambridge Studies in Advanced Mathematics. Vol. 49. Cambridge University Press.

Compatibility

•	The PartiallyOrderedSets[PartiallyOrderedSet] command was introduced in Maple 2025.

•	For more information on Maple 2025 changes, see Updates in Maple 2025.

Maple

Add-ons Maple

Student Success Platform

Améliorer les taux de retention

Maple Flow

MapleSim

Services-conseils

Produits d’enseignement en ligne

Enseignement

Industrie

Automobile et aéronautique

Robotique

Conception de machine & automatismes industriels

Autres

Domaines d’application

Prix et d'achats

Achats

Licences institutionnelles Etudiants

Vue d’ensemble du service EMP

Support

Formation produit

Aide en ligne Produit

Webinaires et évènements

Publications

Hubs de contenu

Exemples et applications

Communauté

A propos de Maplesoft

Ressources presse

Communauté

Contacts

Online Help

All Products Maple MapleSim

Maple

Logiciel de mathématiques puissant facile à utiliser

Add-ons Maple

Student Success Platform

Améliorer les taux de retention

Maple Flow

Engineering calculations & documentation

MapleSim

Modélisation avancée au niveau système

Services-conseils

Produits d’enseignement en ligne

Enseignement

Industrie

Automobile et aéronautique

Robotique

Conception de machine & automatismes industriels

Autres

Domaines d’application

Prix et d'achats

Achats

Licences institutionnelles Etudiants

Vue d’ensemble du service EMP

Support

Formation produit

Aide en ligne Produit

Webinaires et évènements

Publications

Hubs de contenu

Exemples et applications

Communauté

A propos de Maplesoft

Ressources presse

Communauté

Contacts

Online Help

All Products Maple MapleSim