PartiallyOrderedSets/MaximalChains

All Products Maple MapleSim

Home : Support : Online Help : PartiallyOrderedSets/MaximalChains

PartiallyOrderedSets

MaximalChains

returns all the maximal chains of a poset

	Calling Sequence
	MaximalChains(P) MaximalChains(P,opts)

Parameters

P	-	PartiallyOrderedSet
opts	-	(optional) option of the form output = o, where o is list or iterator

Description

•	The command MaximalChains(P) returns the maximal chains of the partially ordered set P.

•

By default, the chains are returned as a list of lists. If the option output = iterator is passed to the MaximalChains command, the chains are returned as an iterator; that is, an object that can be used in a for loop or a seq command. Each iteration yields a chain as a list. This can be more efficient than returning a list of all chains if there are very, very many of them. The default list of lists can be explicitly selected by using the option output = list.

Remarks

•	MaximalAntichains will generate and store the transitive closure and adjacency list of P.

Terminology

•	A partially ordered set, or poset for short, is a pair (P, <=) where P is a set and <= is a partial order on P.

•	From now on, we fix a poset (P, <=).

•	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.

Examples

>	$with (PartiallyOrderedSets) &colon;$

>	$leq ≔ `<=` &colon;$

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 >$

(1)

Display this poset

>	$DrawGraph (poset1)$

Compute the maximal chains of this poset

>	$MaximalChains (poset1)$

$[[1, 2, 3, 4, 5]]$

(2)

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)$

$poset2 ≔ < a poset with 7 elements >$

(3)

Display this poset

>	$DrawGraph (poset2)$

Compute the maximal chains of this poset

>	$MaximalChains (poset2)$

$[[3, 6], [3, 9], [4, 8], [5], [7]]$

(4)

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}]$

(5)

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

$poset4 ≔ < a poset with 5 elements >$

(6)

Display this poset

>	$DrawGraph (poset4)$

Compute the maximal chains of this poset

>	$MaximalChains (poset4)$

$[[1, 2, 3, 4, 5]]$

(7)

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}]$

(8)

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

$poset5 ≔ < a poset with 7 elements >$

(9)

Display this poset

>	$DrawGraph (poset5)$

Compute the maximal chains of this poset

>	$MaximalChains (poset5)$

$[[3, 6], [3, 9], [4, 8], [5], [7]]$

(10)

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$

(11)

>	$poset6 ≔ PartiallyOrderedSet (G)$

$poset6 ≔ < a poset with 6 elements >$

(12)

Display this poset

>	$DrawGraph (poset6)$

Compute the maximal chains of this poset

>	$MaximalChains (poset6)$

$[[1, 2, 4, 6], [1, 3, 5, 6]]$

(13)

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}$

(14)

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

$d ≔ 3$

(15)

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 >$

(16)

Display this poset

>	$DrawGraph (polyhedral_poset)$

Compute the maximal chains of this poset

>	$MaximalChains (polyhedral_poset)$

$[[1, 5, 3, 13, 26], [1, 5, 3, 24, 26], [1, 5, 4, 17, 26], [1, 5, 4, 24, 26], [1, 5, 6, 11, 26], [1, 5, 6, 13, 26], [1, 5, 7, 11, 26], [1, 5, 7, 17, 26], [1, 9, 2, 8, 26], [1, 9, 2, 24, 26], [1, 9, 4, 17, 26], [1, 9, 4, 24, 26], [1, 9, 10, 8, 26], [1, 9, 10, 28, 26], [1, 9, 12, 17, 26], [1, 9, 12, 28, 26], [1, 14, 2, 8, 26], [1, 14, 2, 24, 26], [1, 14, 3, 13, 26], [1, 14, 3, 24, 26], [1, 14, 15, 8, 26], [1, 14, 15, 27, 26], [1, 14, 16, 13, 26], [1, 14, 16, 27, 26], [1, 18, 10, 8, 26], [1, 18, 10, 28, 26], [1, 18, 15, 8, 26], [1, 18, 15, 27, 26], [1, 18, 21, 25, 26], [1, 18, 21, 27, 26], [1, 18, 22, 25, 26], [1, 18, 22, 28, 26], [1, 19, 6, 11, 26], [1, 19, 6, 13, 26], [1, 19, 16, 13, 26], [1, 19, 16, 27, 26], [1, 19, 21, 25, 26], [1, 19, 21, 27, 26], [1, 19, 23, 11, 26], [1, 19, 23, 25, 26], [1, 20, 7, 11, 26], [1, 20, 7, 17, 26], [1, 20, 12, 17, 26], [1, 20, 12, 28, 26], [1, 20, 22, 25, 26], [1, 20, 22, 28, 26], [1, 20, 23, 11, 26], [1, 20, 23, 25, 26]]$

(17)

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 >$

(18)

Display this poset

>	$DrawGraph (poset9)$

Compute the maximal chains of this poset

>	$MaximalChains (poset9)$

$[[1, 2, 3, 5], [1, 4, 5]]$

(19)

We can examine these chains one by one by using the iterator output:

>	$for chain in MaximalChains (poset9, output = iterator) do printf (Chain of length %d: %a\n, numelems (chain), chain) end do &colon;$

Chain of length 4: [1, 2, 3, 5]
Chain of length 3: [1, 4, 5]

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\}$

(20)

>	$poset10 ≔ PartiallyOrderedSet (Z, divisibility)$

$poset10 ≔ < a poset with 12 elements >$

(21)

Display this poset

>	$DrawGraph (poset10)$

Compute the maximal chains of this poset

>	$MaximalChains (poset10)$

$[[1, 2, 4, 12, 60], [1, 2, 4, 20, 60], [1, 2, 6, 12, 60], [1, 2, 6, 30, 60], [1, 2, 10, 20, 60], [1, 2, 10, 30, 60], [1, 3, 6, 12, 60], [1, 3, 6, 30, 60], [1, 3, 15, 30, 60], [1, 5, 10, 20, 60], [1, 5, 10, 30, 60], [1, 5, 15, 30, 60]]$

(22)

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\}$

(23)

>	$poset11 ≔ PartiallyOrderedSet (ZZ, divisibility)$

$poset11 ≔ < a poset with 9 elements >$

(24)

Display this poset

>	$DrawGraph (poset11)$

Compute the maximal chains of this poset

>	$MaximalChains (poset11)$

$[[1, 2, 4, 12, 60], [1, 2, 6, 12, 60], [1, 3, 6, 12, 60], [1, 3, 15, 60], [1, 5, 15, 60]]$

(25)

References

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

Compatibility

•	The PartiallyOrderedSets[MaximalChains] 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