Linear Extensions of Posets¶
This module defines two classes:
Classes and methods¶
-
class
sage.combinat.posets.linear_extensions.
LinearExtensionOfPoset
¶ Bases:
sage.structure.list_clone.ClonableArray
A linear extension of a finite poset \(P\) of size \(n\) is a total ordering \(\pi := \pi_0 \pi_1 \ldots \pi_{n-1}\) of its elements such that \(i<j\) whenever \(\pi_i < \pi_j\) in the poset \(P\).
When the elements of \(P\) are indexed by \(\{1,2,\ldots,n\}\), \(\pi\) denotes a permutation of the elements of \(P\) in one-line notation.
INPUT:
linear_extension
– a list of the elements of \(P\)poset
– the underlying poset \(P\)
See also
EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension=True, facade=False) sage: p = P.linear_extension([1,4,2,3]); p [1, 4, 2, 3] sage: p.parent() The set of all linear extensions of Finite poset containing 4 elements with distinguished linear extension sage: p[0], p[1], p[2], p[3] (1, 4, 2, 3)
Following Schützenberger and later Haiman and Malvenuto-Reutenauer, Stanley [Stan2009] defined a promotion and evacuation operator on any finite poset \(P\) using operators \(\tau_i\) on the linear extensions of \(P\):
sage: p.promotion() [1, 2, 3, 4] sage: Q = p.promotion().to_poset() sage: Q.cover_relations() [[1, 3], [1, 4], [2, 3]] sage: Q == P True sage: p.promotion(3) [1, 4, 2, 3] sage: Q = p.promotion(3).to_poset() sage: Q == P False sage: Q.cover_relations() [[1, 2], [1, 4], [3, 4]]
-
check
()¶ Checks whether
self
is indeed a linear extension of the underlying poset.TESTS:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]])) sage: P.linear_extension([1,4,2,3]) [1, 4, 2, 3] sage: P.linear_extension([4,3,2,1]) Traceback (most recent call last): ... ValueError: [4, 3, 2, 1] is not a linear extension of Finite poset containing 4 elements
-
evacuation
()¶ Computes evacuation on the linear extension of a poset.
Evacuation on a linear extension \(\pi\) of length \(n\) is defined as \(\pi (\tau_1 \cdots \tau_{n-1}) (\tau_1 \cdots \tau_{n-2}) \cdots (\tau_1)\). For more details see [Stan2009].
See also
EXAMPLES:
sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]])) sage: p = P.linear_extension([1,2,3,4,5,6,7]) sage: p.evacuation() [1, 4, 2, 3, 7, 5, 6] sage: p.evacuation().evacuation() == p True
-
poset
()¶ Returns the underlying original poset.
EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,2],[2,3],[1,4]])) sage: p = P.linear_extension([1,2,4,3]) sage: p.poset() Finite poset containing 4 elements
-
promotion
(i=1)¶ Computes the (generalized) promotion on the linear extension of a poset.
INPUT:
- \(i\) – an integer between \(1\) and \(n-1\), where \(n\) is the cardinality of the poset (default: \(1\))
The \(i\)-th generalized promotion operator \(\partial_i\) on a linear extension \(\pi\) is defined as \(\pi \tau_i \tau_{i+1} \cdots \tau_{n-1}\), where \(n\) is the size of the linear extension (or size of the underlying poset).
For more details see [Stan2009].
See also
EXAMPLES:
sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]])) sage: p = P.linear_extension([1,2,3,4,5,6,7]) sage: q = p.promotion(4); q [1, 2, 3, 5, 6, 4, 7] sage: p.to_poset() == q.to_poset() False sage: p.to_poset().is_isomorphic(q.to_poset()) True
-
tau
(i)¶ Returns the operator \(\tau_i\) on linear extensions
self
of a poset.INPUT:
- \(i\) – an integer between \(1\) and \(n-1\), where \(n\) is the cardinality of the poset.
The operator \(\tau_i\) on a linear extension \(\pi\) of a poset \(P\) interchanges positions \(i\) and \(i+1\) if the result is again a linear extension of \(P\), and otherwise acts trivially. For more details, see [Stan2009].
EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension=True) sage: L = P.linear_extensions() sage: l = L.an_element(); l [1, 2, 3, 4] sage: l.tau(1) [2, 1, 3, 4] sage: for p in L: ....: for i in range(1,4): ....: print("{} {} {}".format(i, p, p.tau(i))) 1 [1, 2, 3, 4] [2, 1, 3, 4] 2 [1, 2, 3, 4] [1, 2, 3, 4] 3 [1, 2, 3, 4] [1, 2, 4, 3] 1 [1, 2, 4, 3] [2, 1, 4, 3] 2 [1, 2, 4, 3] [1, 4, 2, 3] 3 [1, 2, 4, 3] [1, 2, 3, 4] 1 [1, 4, 2, 3] [1, 4, 2, 3] 2 [1, 4, 2, 3] [1, 2, 4, 3] 3 [1, 4, 2, 3] [1, 4, 2, 3] 1 [2, 1, 3, 4] [1, 2, 3, 4] 2 [2, 1, 3, 4] [2, 1, 3, 4] 3 [2, 1, 3, 4] [2, 1, 4, 3] 1 [2, 1, 4, 3] [1, 2, 4, 3] 2 [2, 1, 4, 3] [2, 1, 4, 3] 3 [2, 1, 4, 3] [2, 1, 3, 4]
TESTS:
sage: type(l.tau(1)) <class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category.element_class'> sage: l.tau(2) == l True
-
to_poset
()¶ Return the poset associated to the linear extension
self
.This method returns the poset obtained from the original poset \(P\) by relabelling the \(i\)-th element of
self
to the \(i\)-th element of the original poset, while keeping the linear extension of the original poset.For a poset with default linear extension \(1,\dots,n\),
self
can be interpreted as a permutation, and the relabelling is done according to the inverse of this permutation.EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,2],[1,3],[3,4]]), linear_extension=True, facade=False) sage: p = P.linear_extension([1,3,4,2]) sage: Q = p.to_poset(); Q Finite poset containing 4 elements with distinguished linear extension sage: P == Q False
The default linear extension remains the same:
sage: list(P) [1, 2, 3, 4] sage: list(Q) [1, 2, 3, 4]
But the relabelling can be seen on cover relations:
sage: P.cover_relations() [[1, 2], [1, 3], [3, 4]] sage: Q.cover_relations() [[1, 2], [1, 4], [2, 3]] sage: p = P.linear_extension([1,2,3,4]) sage: Q = p.to_poset() sage: P == Q True
-
class
sage.combinat.posets.linear_extensions.
LinearExtensionsOfPoset
(poset, facade)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The set of all linear extensions of a finite poset
INPUT:
poset
– a poset \(P\) of size \(n\)facade
– a boolean (default:False
)
See also
EXAMPLES:
sage: elms = [1,2,3,4] sage: rels = [[1,3],[1,4],[2,3]] sage: P = Poset((elms, rels), linear_extension=True) sage: L = P.linear_extensions(); L The set of all linear extensions of Finite poset containing 4 elements with distinguished linear extension sage: L.cardinality() 5 sage: L.list() [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: L.an_element() [1, 2, 3, 4] sage: L.poset() Finite poset containing 4 elements with distinguished linear extension
-
Element
¶ alias of
LinearExtensionOfPoset
-
cardinality
()¶ Return the number of linear extensions.
EXAMPLES:
sage: N = Poset({0: [2, 3], 1: [3]}) sage: N.linear_extensions().cardinality() 5
TESTS:
sage: Poset().linear_extensions().cardinality() 1 sage: Posets.ChainPoset(1).linear_extensions().cardinality() 1
-
markov_chain_digraph
(action='promotion', labeling='identity')¶ Returns the digraph of the action of generalized promotion or tau on
self
INPUT:
action
– ‘promotion’ or ‘tau’ (default: ‘promotion’)labeling
– ‘identity’ or ‘source’ (default: ‘identity’)
Todo
- generalize this feature by accepting a family of operators as input
- move up in some appropriate category
This method creates a graph with vertices being the linear extensions of a given finite poset and an edge from \(\pi\) to \(\pi'\) if \(\pi' = \pi \partial_i\) where \(\partial_i\) is the promotion operator (see
promotion()
) ifaction
is set topromotion
and \(\tau_i\) (seetau()
) ifaction
is set totau
. The label of the edge is \(i\) (resp. \(\pi_i\)) iflabeling
is set toidentity
(resp.source
).EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension = True) sage: L = P.linear_extensions() sage: G = L.markov_chain_digraph(); G Looped multi-digraph on 5 vertices sage: sorted(G.vertices(), key = repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: sorted(G.edges(), key = repr) [([1, 2, 3, 4], [1, 2, 3, 4], 4), ([1, 2, 3, 4], [1, 2, 4, 3], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3), ([1, 2, 3, 4], [2, 1, 4, 3], 1), ([1, 2, 4, 3], [1, 2, 3, 4], 3), ([1, 2, 4, 3], [1, 2, 4, 3], 4), ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 3), ([1, 4, 2, 3], [1, 4, 2, 3], 4), ([2, 1, 3, 4], [1, 2, 4, 3], 1), ([2, 1, 3, 4], [2, 1, 3, 4], 4), ([2, 1, 3, 4], [2, 1, 4, 3], 2), ([2, 1, 3, 4], [2, 1, 4, 3], 3), ([2, 1, 4, 3], [1, 4, 2, 3], 1), ([2, 1, 4, 3], [2, 1, 3, 4], 2), ([2, 1, 4, 3], [2, 1, 3, 4], 3), ([2, 1, 4, 3], [2, 1, 4, 3], 4)] sage: G = L.markov_chain_digraph(labeling = 'source') sage: sorted(G.vertices(), key = repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: sorted(G.edges(), key = repr) [([1, 2, 3, 4], [1, 2, 3, 4], 4), ([1, 2, 3, 4], [1, 2, 4, 3], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3), ([1, 2, 3, 4], [2, 1, 4, 3], 1), ([1, 2, 4, 3], [1, 2, 3, 4], 4), ([1, 2, 4, 3], [1, 2, 4, 3], 3), ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 4), ([1, 4, 2, 3], [1, 4, 2, 3], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 3), ([2, 1, 3, 4], [1, 2, 4, 3], 2), ([2, 1, 3, 4], [2, 1, 3, 4], 4), ([2, 1, 3, 4], [2, 1, 4, 3], 1), ([2, 1, 3, 4], [2, 1, 4, 3], 3), ([2, 1, 4, 3], [1, 4, 2, 3], 2), ([2, 1, 4, 3], [2, 1, 3, 4], 1), ([2, 1, 4, 3], [2, 1, 3, 4], 4), ([2, 1, 4, 3], [2, 1, 4, 3], 3)]
The edges of the graph are by default colored using blue for edge 1, red for edge 2, green for edge 3, and yellow for edge 4:
sage: view(G) # optional - dot2tex graphviz, not tested (opens external window)
Alternatively, one may get the graph of the action of the
tau
operator:sage: G = L.markov_chain_digraph(action='tau'); G Looped multi-digraph on 5 vertices sage: sorted(G.vertices(), key = repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: sorted(G.edges(), key = repr) [([1, 2, 3, 4], [1, 2, 3, 4], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3), ([1, 2, 3, 4], [2, 1, 3, 4], 1), ([1, 2, 4, 3], [1, 2, 3, 4], 3), ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 4, 3], 1), ([1, 4, 2, 3], [1, 2, 4, 3], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 1), ([1, 4, 2, 3], [1, 4, 2, 3], 3), ([2, 1, 3, 4], [1, 2, 3, 4], 1), ([2, 1, 3, 4], [2, 1, 3, 4], 2), ([2, 1, 3, 4], [2, 1, 4, 3], 3), ([2, 1, 4, 3], [1, 2, 4, 3], 1), ([2, 1, 4, 3], [2, 1, 3, 4], 3), ([2, 1, 4, 3], [2, 1, 4, 3], 2)] sage: view(G) # optional - dot2tex graphviz, not tested (opens external window)
See also
markov_chain_transition_matrix()
,promotion()
,tau()
TESTS:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension = True, facade = True) sage: L = P.linear_extensions() sage: G = L.markov_chain_digraph(labeling = 'source'); G Looped multi-digraph on 5 vertices
-
markov_chain_transition_matrix
(action='promotion', labeling='identity')¶ Returns the transition matrix of the Markov chain for the action of generalized promotion or tau on
self
INPUT:
action
– ‘promotion’ or ‘tau’ (default: ‘promotion’)labeling
– ‘identity’ or ‘source’ (default: ‘identity’)
This method yields the transition matrix of the Markov chain defined by the action of the generalized promotion operator \(\partial_i\) (resp. \(\tau_i\)) on the set of linear extensions of a finite poset. Here the transition from the linear extension \(\pi\) to \(\pi'\), where \(\pi' = \pi \partial_i\) (resp. \(\pi'= \pi \tau_i\)) is counted with weight \(x_i\) (resp. \(x_{\pi_i}\) if
labeling
is set tosource
).EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension = True) sage: L = P.linear_extensions() sage: L.markov_chain_transition_matrix() [-x0 - x1 - x2 x2 x0 + x1 0 0] [ x1 + x2 -x0 - x1 - x2 0 x0 0] [ 0 x1 -x0 - x1 0 x0] [ 0 x0 0 -x0 - x1 - x2 x1 + x2] [ x0 0 0 x1 + x2 -x0 - x1 - x2] sage: L.markov_chain_transition_matrix(labeling = 'source') [-x0 - x1 - x2 x3 x0 + x3 0 0] [ x1 + x2 -x0 - x1 - x3 0 x1 0] [ 0 x1 -x0 - x3 0 x1] [ 0 x0 0 -x0 - x1 - x2 x0 + x3] [ x0 0 0 x0 + x2 -x0 - x1 - x3] sage: L.markov_chain_transition_matrix(action = 'tau') [ -x0 - x2 x2 0 x0 0] [ x2 -x0 - x1 - x2 x1 0 x0] [ 0 x1 -x1 0 0] [ x0 0 0 -x0 - x2 x2] [ 0 x0 0 x2 -x0 - x2] sage: L.markov_chain_transition_matrix(action = 'tau', labeling = 'source') [ -x0 - x2 x3 0 x1 0] [ x2 -x0 - x1 - x3 x3 0 x1] [ 0 x1 -x3 0 0] [ x0 0 0 -x1 - x2 x3] [ 0 x0 0 x2 -x1 - x3]
See also
markov_chain_digraph()
,promotion()
,tau()
-
poset
()¶ Returns the underlying original poset.
EXAMPLES:
sage: P = Poset(([1,2,3,4], [[1,2],[2,3],[1,4]])) sage: L = P.linear_extensions() sage: L.poset() Finite poset containing 4 elements