Bases: sage.structure.list_clone.ClonableArray
A linear extension of a finite poset of size
is a total
ordering
of its elements
such that
whenever
in the poset
.
When the elements of are indexed by
,
denotes a permutation of the elements of
in one-line notation.
INPUT:
See also
Poset, LinearExtensionsOfPosets
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
sage: p[0], p[1], p[2], p[3]
(1, 4, 2, 3)
Following Schützenberger and later Haiman and
Malvenuto-Reutenauer, Stanley [Stanley2009] defined a promotion
and evacuation operator on any finite poset using operators
on the linear extensions of
:
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]]
REFERENCES:
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
Computes evacuation on the linear extension of a poset.
Evacuation on a linear extension of length
is defined as
.
For more details see [Stanley2009].
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
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
Computes the (generalized) promotion on the linear extension of a poset.
INPUT:
The -th generalized promotion operator
on a linear extension
is defined as
, where
is the
size of the linear extension (or size of the underlying poset).
For more details see [Stanley2009].
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
Returns the operator on linear extensions self of a poset.
INPUT:
The operator on a linear extension
of a poset
interchanges positions
and
if the result is
again a linear extension of
, and otherwise acts
trivially. For more details, see [Stanley2009].
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 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
Returns the poset associated to the linear extension self.
This method returns the poset obtained from the original poset
by relabelling the ‘i’-th element of self to the
-th element of the original poset, while keeping the linear
extension of the original poset.
For a poset with default linear extension ,
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]]), facade = False)
sage: p = P.linear_extension([1,3,4,2])
sage: Q = p.to_poset(); Q
Finite poset containing 4 elements
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
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
The set of all linear extensions of a finite poset
INPUT:
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
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
alias of LinearExtensionOfPoset
Returns the digraph of the action of generalized promotion or tau on self
INPUT:
Todo
This method creates a graph with vertices being the linear extensions of a given finite
poset and an edge from to
if
where
is
the promotion operator (see promotion()) if action is set to promotion
and
(see tau()) if action is set to tau. The label of the edge
is
(resp.
) if labeling is set to identity (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
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
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
Returns the transition matrix of the Markov chain for the action of generalized promotion or tau on self
INPUT:
This method yields the transition matrix of the Markov chain defined by the action of the generalized
promotion operator (resp.
) on the set of linear extensions of a finite poset.
Here the transition from the linear extension
to
, where
(resp.
) is counted with weight
(resp.
if labeling is set to source).
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()
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