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.

$\mathrm{with}\left(\mathrm{PartiallyOrderedSets}\right)\:$

$\mathrm{leq}≔\mathrm{`<=`}\&colon;$

$S≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\right\}\&colon;$$\mathrm{poset1}≔\mathrm{PartiallyOrderedSet}\left(S\&comma;\mathrm{leq}\right)$

$\mathrm{poset1}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset1}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset1}\right)$

$\left[\left[1\&comma;2\&comma;3\&comma;4\&comma;5\right]\right]$

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

$\mathrm{poset2}≔\mathrm{PartiallyOrderedSet}\left(T\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset2}≔\mathrm{<\; a\; poset\; with\; 7\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset2}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset2}\right)$

$\left[\left[3\&comma;6\right]\&comma;\left[3\&comma;9\right]\&comma;\left[4\&comma;8\right]\&comma;\left[5\right]\&comma;\left[7\right]\right]$

$\mathrm{adjMatrix4}≔\mathrm{Matrix}\left(\left[\left[1\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;0\&comma;1\right]\right]\right)$

$\mathrm{adjMatrix4}≔\left[\begin{array}{ccccc}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}\right]$

$\mathrm{poset4}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{convert}\left(S\&comma;'\mathrm{list}'\right)\&comma;\mathrm{adjMatrix4}\right)$

$\mathrm{poset4}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset4}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset4}\right)$

$\left[\left[1\&comma;2\&comma;3\&comma;4\&comma;5\right]\right]$

$\mathrm{adjList5}≔\mathrm{map2}\left(\mathrm{map}\&comma;\mathrm{`+`}\&comma;\mathrm{Array}\left(\left[\left\{1\&comma;4\&comma;7\right\}\&comma;\left\{2\&comma;6\right\}\&comma;\left\{3\right\}\&comma;\left\{4\right\}\&comma;\left\{5\right\}\&comma;\left\{6\right\}\&comma;\left\{7\right\}\right]\right)\&comma;2\right)$

$\mathrm{adjList5}≔\left[\begin{array}{ccccccc}\left\{3\&comma;6\&comma;9\right\}& \left\{4\&comma;8\right\}& \left\{5\right\}& \left\{6\right\}& \left\{7\right\}& \left\{8\right\}& \left\{9\right\}\end{array}\right]$

$\mathrm{poset5}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{convert}\left(T\&comma;'\mathrm{list}'\right)\&comma;\mathrm{adjList5}\right)$

$\mathrm{poset5}≔\mathrm{<\; a\; poset\; with\; 7\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset5}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset5}\right)$

$\left[\left[3\&comma;6\right]\&comma;\left[3\&comma;9\right]\&comma;\left[4\&comma;8\right]\&comma;\left[5\right]\&comma;\left[7\right]\right]$

$G≔\mathrm{GraphTheory}:-\mathrm{Graph}\left(\mathrm{directed}\&comma;\left[1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\right]\&comma;\left\{\left[1\&comma;1\right]\&comma;\left[1\&comma;2\right]\&comma;\left[1\&comma;3\right]\&comma;\left[1\&comma;4\right]\&comma;\left[1\&comma;5\right]\&comma;\left[1\&comma;6\right]\&comma;\left[2\&comma;2\right]\&comma;\left[2\&comma;4\right]\&comma;\left[2\&comma;6\right]\&comma;\left[3\&comma;3\right]\&comma;\left[3\&comma;5\right]\&comma;\left[3\&comma;6\right]\&comma;\left[4\&comma;4\right]\&comma;\left[4\&comma;6\right]\&comma;\left[5\&comma;5\right]\&comma;\left[5\&comma;6\right]\&comma;\left[6\&comma;6\right]\right\}\right)$

$G≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 6\; vertices,\; 11\; arcs,\; and\; 6\; self-loops}$

$\mathrm{poset6}≔\mathrm{PartiallyOrderedSet}\left(G\right)$

$\mathrm{poset6}≔\mathrm{<\; a\; poset\; with\; 6\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset6}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset6}\right)$

$\left[\left[1\&comma;2\&comma;4\&comma;6\right]\&comma;\left[1\&comma;3\&comma;5\&comma;6\right]\right]$

$t≔\mathrm{PolyhedralSets}:-\mathrm{ExampleSets}:-\mathrm{Octahedron}\left(\right)$

$t≔\&lcub;\begin{array}{lll}\mathrm{Coordinates}& \&colon;& \left[x_1\&comma;x_2\&comma;x_3\right]\\ \mathrm{Relations}& \&colon;& \left[-x_1-x_2-x_3\le 1\&comma;-x_1-x_2+x_3\le 1\&comma;-x_1+x_2-x_3\le 1\&comma;-x_1+x_2+x_3\le 1\&comma;x_1-x_2-x_3\le 1\&comma;x_1-x_2+x_3\le 1\&comma;x_1+x_2-x_3\le 1\&comma;x_1+x_2+x_3\le 1\right]\end{array}$

$d≔\mathrm{PolyhedralSets}:-\mathrm{Dimension}\left(t\right)$

$d≔3$

$\mathrm{t\_faces}≔\left\{\mathrm{seq}\left(\mathrm{op}\left(\mathrm{PolyhedralSets}:-\mathrm{Faces}\left(t\&comma;\mathrm{dimension}=i\right)\right)\&comma;i=-0..d\right)\right\}\&colon;$

$\mathrm{t\_faces}≔\mathrm{t\_faces}\mathbf{union}\left\{\mathrm{PolyhedralSets}:-\mathrm{ExampleSets}:-\mathrm{EmptySet}\left(d\right)\right\}\&colon;$

$\mathrm{FL}≔\mathrm{convert}\left(\mathrm{t\_faces}\&comma;\mathrm{list}\right)\&colon;$

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

$\mathrm{polyhedral\_poset}≔\mathrm{PartiallyOrderedSet}\left(\left\{\mathrm{seq}\left(i\&comma;i=1..\mathrm{nops}\left(\mathrm{FL}\right)\right)\right\}\&comma;\mathrm{inclusion}\right)$

$\mathrm{polyhedral\_poset}≔\mathrm{<\; a\; poset\; with\; 28\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{polyhedral\_poset}\right)$

$\mathrm{MaximalChains}\left(\mathrm{polyhedral\_poset}\right)$

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

$M≔\mathrm{Matrix}\left(\left[\left[1\&comma;1\&comma;1\&comma;1\&comma;1\right]\&comma;\left[0\&comma;1\&comma;1\&comma;0\&comma;1\right]\&comma;\left[0\&comma;0\&comma;1\&comma;0\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;1\&comma;1\right]\&comma;\left[0\&comma;0\&comma;0\&comma;0\&comma;1\right]\right]\right)\&colon;$

$\mathrm{poset9}≔\mathrm{PartiallyOrderedSet}\left(\left[\mathrm{seq}\left(1..5\right)\right]\&comma;M\right)$

$\mathrm{poset9}≔\mathrm{<\; a\; poset\; with\; 5\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset9}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset9}\right)$

$\left[\left[1\&comma;2\&comma;3\&comma;5\right]\&comma;\left[1\&comma;4\&comma;5\right]\right]$

$$\begin{gathered} \mathbf{for}\mathrm{chain}\mathbf{in}\mathrm{MaximalChains}\left(\mathrm{poset9}\&comma;\mathrm{output}=\mathrm{iterator}\right)\mathbf{do} \\ \mathrm{printf}\left(''Chain\; of\; length\; \%d:\; \%a\backslash n''\&comma;\mathrm{numelems}\left(\mathrm{chain}\right)\&comma;\mathrm{chain}\right) \\ \mathbf{end}\mathbf{do}\&colon; \end{gathered}$$

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

$Z≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;10\&comma;12\&comma;15\&comma;20\&comma;30\&comma;60\right\}$

$Z≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;10\&comma;12\&comma;15\&comma;20\&comma;30\&comma;60\right\}$

$\mathrm{poset10}≔\mathrm{PartiallyOrderedSet}\left(Z\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset10}≔\mathrm{<\; a\; poset\; with\; 12\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset10}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset10}\right)$

$\left[\left[1\&comma;2\&comma;4\&comma;12\&comma;60\right]\&comma;\left[1\&comma;2\&comma;4\&comma;20\&comma;60\right]\&comma;\left[1\&comma;2\&comma;6\&comma;12\&comma;60\right]\&comma;\left[1\&comma;2\&comma;6\&comma;30\&comma;60\right]\&comma;\left[1\&comma;2\&comma;10\&comma;20\&comma;60\right]\&comma;\left[1\&comma;2\&comma;10\&comma;30\&comma;60\right]\&comma;\left[1\&comma;3\&comma;6\&comma;12\&comma;60\right]\&comma;\left[1\&comma;3\&comma;6\&comma;30\&comma;60\right]\&comma;\left[1\&comma;3\&comma;15\&comma;30\&comma;60\right]\&comma;\left[1\&comma;5\&comma;10\&comma;20\&comma;60\right]\&comma;\left[1\&comma;5\&comma;10\&comma;30\&comma;60\right]\&comma;\left[1\&comma;5\&comma;15\&comma;30\&comma;60\right]\right]$

$\mathrm{ZZ}≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;12\&comma;15\&comma;60\right\}$

$\mathrm{ZZ}≔\left\{1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;12\&comma;15\&comma;60\right\}$

$\mathrm{poset11}≔\mathrm{PartiallyOrderedSet}\left(\mathrm{ZZ}\&comma;\mathrm{divisibility}\right)$

$\mathrm{poset11}≔\mathrm{<\; a\; poset\; with\; 9\; elements\; >}$

$\mathrm{DrawGraph}\left(\mathrm{poset11}\right)$

$\mathrm{MaximalChains}\left(\mathrm{poset11}\right)$

$\left[\left[1\&comma;2\&comma;4\&comma;12\&comma;60\right]\&comma;\left[1\&comma;2\&comma;6\&comma;12\&comma;60\right]\&comma;\left[1\&comma;3\&comma;6\&comma;12\&comma;60\right]\&comma;\left[1\&comma;3\&comma;15\&comma;60\right]\&comma;\left[1\&comma;5\&comma;15\&comma;60\right]\right]$

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

The PartiallyOrderedSets[MaximalChains] command was introduced in Maple 2025.

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