Linear Extensions of Posets#
This module defines two classes:
Classes and methods#
- class sage.combinat.posets.linear_extensions.LinearExtensionOfPoset[source]#
Bases:
ClonableArrayA 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)
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(3)]]), ... linear_extension=True, facade=False) >>> p = P.linear_extension([Integer(1),Integer(4),Integer(2),Integer(3)]); p [1, 4, 2, 3] >>> p.parent() The set of all linear extensions of Finite poset containing 4 elements with distinguished linear extension >>> p[Integer(0)], p[Integer(1)], p[Integer(2)], p[Integer(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]]
>>> from sage.all import * >>> p.promotion() [1, 2, 3, 4] >>> Q = p.promotion().to_poset() >>> Q.cover_relations() [[1, 3], [1, 4], [2, 3]] >>> Q == P True >>> p.promotion(Integer(3)) [1, 4, 2, 3] >>> Q = p.promotion(Integer(3)).to_poset() >>> Q == P False >>> Q.cover_relations() [[1, 2], [1, 4], [3, 4]]
- evacuation()[source]#
Compute 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
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)], [[Integer(1),Integer(2)],[Integer(1),Integer(4)],[Integer(2),Integer(3)],[Integer(2),Integer(5)],[Integer(3),Integer(6)],[Integer(4),Integer(7)],[Integer(5),Integer(6)]])) >>> p = P.linear_extension([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)]) >>> p.evacuation() [1, 4, 2, 3, 7, 5, 6] >>> p.evacuation().evacuation() == p True
- is_greedy()[source]#
Return
Trueif the linear extension is greedy.A linear extension \([e_1, e_2, \ldots, e_n]\) is greedy if for every \(i\) either \(e_{i+1}\) covers \(e_i\) or all upper covers of \(e_i\) have at least one lower cover that is not in \([e_1, e_2, \ldots, e_i]\).
Informally said a linear extension is greedy if it “always goes up when possible” and so has no unnecessary jumps.
EXAMPLES:
sage: P = posets.PentagonPoset() # needs sage.modules sage: for l in P.linear_extensions(): # needs sage.modules ....: if not l.is_greedy(): ....: print(l) [0, 2, 1, 3, 4]
>>> from sage.all import * >>> P = posets.PentagonPoset() # needs sage.modules >>> for l in P.linear_extensions(): # needs sage.modules ... if not l.is_greedy(): ... print(l) [0, 2, 1, 3, 4]
- is_supergreedy()[source]#
Return
Trueif the linear extension is supergreedy.A linear extension of a poset \(P\) with elements \(\{x_1,x_2,...,x_t\}\) is super greedy, if it can be obtained using the following algorithm: choose \(x_1\) to be a minimal element of \(P\); suppose \(X = \{x_1,...,x_i\}\) have been chosen; let \(M\) be the set of minimal elements of \(P\setminus X\). If there is an element of \(M\) which covers an element \(x_j\) in \(X\), then let \(x_{i+1}\) be one of these such that \(j\) is maximal; otherwise, choose \(x_{i+1}\) to be any element of \(M\).
Informally, a linear extension is supergreedy if it “always goes up and receedes the least”; in other words, supergreedy linear extensions are depth-first linear extensions. For more details see [KTZ1987].
EXAMPLES:
sage: X = [0,1,2,3,4,5,6] sage: Y = [[0,5],[1,4],[1,5],[3,6],[4,3],[5,6],[6,2]] sage: P = Poset((X,Y), cover_relations=True, facade=False) sage: for l in P.linear_extensions(): # needs sage.modules ....: if l.is_supergreedy(): ....: print(l) [1, 4, 3, 0, 5, 6, 2] [0, 1, 4, 3, 5, 6, 2] [0, 1, 5, 4, 3, 6, 2] sage: Q = posets.PentagonPoset() # needs sage.modules sage: for l in Q.linear_extensions(): # needs sage.modules sage.rings.finite_rings ....: if not l.is_supergreedy(): ....: print(l) [0, 2, 1, 3, 4]
>>> from sage.all import * >>> X = [Integer(0),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)] >>> Y = [[Integer(0),Integer(5)],[Integer(1),Integer(4)],[Integer(1),Integer(5)],[Integer(3),Integer(6)],[Integer(4),Integer(3)],[Integer(5),Integer(6)],[Integer(6),Integer(2)]] >>> P = Poset((X,Y), cover_relations=True, facade=False) >>> for l in P.linear_extensions(): # needs sage.modules ... if l.is_supergreedy(): ... print(l) [1, 4, 3, 0, 5, 6, 2] [0, 1, 4, 3, 5, 6, 2] [0, 1, 5, 4, 3, 6, 2] >>> Q = posets.PentagonPoset() # needs sage.modules >>> for l in Q.linear_extensions(): # needs sage.modules sage.rings.finite_rings ... if not l.is_supergreedy(): ... print(l) [0, 2, 1, 3, 4]
- jump_count()[source]#
Return the number of jumps in the linear extension.
A jump in a linear extension \([e_1, e_2, \ldots, e_n]\) is a pair \((e_i, e_{i+1})\) such that \(e_{i+1}\) does not cover \(e_i\).
EXAMPLES:
sage: B3 = posets.BooleanLattice(3) sage: l1 = B3.linear_extension((0, 1, 2, 3, 4, 5, 6, 7)) sage: l1.jump_count() 3 sage: l2 = B3.linear_extension((0, 1, 2, 4, 3, 5, 6, 7)) sage: l2.jump_count() 5
>>> from sage.all import * >>> B3 = posets.BooleanLattice(Integer(3)) >>> l1 = B3.linear_extension((Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5), Integer(6), Integer(7))) >>> l1.jump_count() 3 >>> l2 = B3.linear_extension((Integer(0), Integer(1), Integer(2), Integer(4), Integer(3), Integer(5), Integer(6), Integer(7))) >>> l2.jump_count() 5
- poset()[source]#
Return 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
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(2)],[Integer(2),Integer(3)],[Integer(1),Integer(4)]])) >>> p = P.linear_extension([Integer(1),Integer(2),Integer(4),Integer(3)]) >>> p.poset() Finite poset containing 4 elements
- promotion(i=1)[source]#
Compute the (generalized) promotion on the linear extension of a poset.
INPUT:
i– (default: \(1\)) an integer between \(1\) and \(n-1\), where \(n\) is the cardinality of the poset
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
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)], [[Integer(1),Integer(2)],[Integer(1),Integer(4)],[Integer(2),Integer(3)],[Integer(2),Integer(5)],[Integer(3),Integer(6)],[Integer(4),Integer(7)],[Integer(5),Integer(6)]])) >>> p = P.linear_extension([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)]) >>> q = p.promotion(Integer(4)); q [1, 2, 3, 5, 6, 4, 7] >>> p.to_poset() == q.to_poset() False >>> p.to_poset().is_isomorphic(q.to_poset()) True
- tau(i)[source]#
Return the operator \(\tau_i\) on linear extensions
selfof 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: # needs sage.modules ....: 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 [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] 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 [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]
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(3)]]), linear_extension=True) >>> L = P.linear_extensions() >>> l = L.an_element(); l [1, 2, 3, 4] >>> l.tau(Integer(1)) [2, 1, 3, 4] >>> for p in L: # needs sage.modules ... for i in range(Integer(1),Integer(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 [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] 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 [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]
- to_poset()[source]#
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
selfto 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\),
selfcan 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
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(2)],[Integer(1),Integer(3)],[Integer(3),Integer(4)]]), linear_extension=True, facade=False) >>> p = P.linear_extension([Integer(1),Integer(3),Integer(4),Integer(2)]) >>> Q = p.to_poset(); Q Finite poset containing 4 elements with distinguished linear extension >>> P == Q False
The default linear extension remains the same:
sage: list(P) [1, 2, 3, 4] sage: list(Q) [1, 2, 3, 4]
>>> from sage.all import * >>> list(P) [1, 2, 3, 4] >>> 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
>>> from sage.all import * >>> P.cover_relations() [[1, 2], [1, 3], [3, 4]] >>> Q.cover_relations() [[1, 2], [1, 4], [2, 3]] >>> p = P.linear_extension([Integer(1),Integer(2),Integer(3),Integer(4)]) >>> Q = p.to_poset() >>> P == Q True
- class sage.combinat.posets.linear_extensions.LinearExtensionsOfForest(poset, facade)[source]#
Bases:
LinearExtensionsOfPosetLinear extensions such that the poset is a forest.
- cardinality()[source]#
Use Atkinson’s algorithm to compute the number of linear extensions.
EXAMPLES:
sage: from sage.combinat.posets.forest import ForestPoset sage: from sage.combinat.posets.poset_examples import Posets sage: P = Poset({0: [2], 1: [2], 2: [3, 4], 3: [], 4: []}) sage: P.linear_extensions().cardinality() # needs sage.modules 4 sage: Q = Poset({0: [1], 1: [2, 3], 2: [], 3: [], 4: [5, 6], 5: [], 6: []}) sage: Q.linear_extensions().cardinality() # needs sage.modules 140
>>> from sage.all import * >>> from sage.combinat.posets.forest import ForestPoset >>> from sage.combinat.posets.poset_examples import Posets >>> P = Poset({Integer(0): [Integer(2)], Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)], Integer(3): [], Integer(4): []}) >>> P.linear_extensions().cardinality() # needs sage.modules 4 >>> Q = Poset({Integer(0): [Integer(1)], Integer(1): [Integer(2), Integer(3)], Integer(2): [], Integer(3): [], Integer(4): [Integer(5), Integer(6)], Integer(5): [], Integer(6): []}) >>> Q.linear_extensions().cardinality() # needs sage.modules 140
- class sage.combinat.posets.linear_extensions.LinearExtensionsOfMobile(poset, facade)[source]#
Bases:
LinearExtensionsOfPosetLinear extensions for a mobile poset.
- cardinality()[source]#
Return the number of linear extensions by using the determinant formula for counting linear extensions of mobiles.
EXAMPLES:
sage: from sage.combinat.posets.mobile import MobilePoset sage: M = MobilePoset(DiGraph([[0,1,2,3,4,5,6,7,8], [(1,0),(3,0),(2,1),(2,3),(4, ....: 3), (5,4),(5,6),(7,4),(7,8)]])) sage: M.linear_extensions().cardinality() # needs sage.modules 1098 sage: M1 = posets.RibbonPoset(6, [1,3]) sage: M1.linear_extensions().cardinality() # needs sage.modules 61 sage: P = posets.MobilePoset(posets.RibbonPoset(7, [1,3]), # needs sage.combinat sage.modules ....: {1: [posets.YoungDiagramPoset([3, 2], dual=True)], ....: 3: [posets.DoubleTailedDiamond(6)]}, ....: anchor=(4, 2, posets.ChainPoset(6))) sage: P.linear_extensions().cardinality() # needs sage.combinat sage.modules 361628701868606400
>>> from sage.all import * >>> from sage.combinat.posets.mobile import MobilePoset >>> M = MobilePoset(DiGraph([[Integer(0),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7),Integer(8)], [(Integer(1),Integer(0)),(Integer(3),Integer(0)),(Integer(2),Integer(1)),(Integer(2),Integer(3)),(Integer(4), ... Integer(3)), (Integer(5),Integer(4)),(Integer(5),Integer(6)),(Integer(7),Integer(4)),(Integer(7),Integer(8))]])) >>> M.linear_extensions().cardinality() # needs sage.modules 1098 >>> M1 = posets.RibbonPoset(Integer(6), [Integer(1),Integer(3)]) >>> M1.linear_extensions().cardinality() # needs sage.modules 61 >>> P = posets.MobilePoset(posets.RibbonPoset(Integer(7), [Integer(1),Integer(3)]), # needs sage.combinat sage.modules ... {Integer(1): [posets.YoungDiagramPoset([Integer(3), Integer(2)], dual=True)], ... Integer(3): [posets.DoubleTailedDiamond(Integer(6))]}, ... anchor=(Integer(4), Integer(2), posets.ChainPoset(Integer(6)))) >>> P.linear_extensions().cardinality() # needs sage.combinat sage.modules 361628701868606400
- class sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset(poset, facade)[source]#
Bases:
UniqueRepresentation,ParentThe set of all linear extensions of a finite poset
INPUT:
poset– a poset \(P\) of size \(n\)facade– a boolean (default:False)
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() # needs sage.modules [[1, 2, 3, 4], [2, 1, 3, 4], [2, 1, 4, 3], [1, 4, 2, 3], [1, 2, 4, 3]] sage: L.an_element() [1, 2, 3, 4] sage: L.poset() Finite poset containing 4 elements with distinguished linear extension
>>> from sage.all import * >>> elms = [Integer(1),Integer(2),Integer(3),Integer(4)] >>> rels = [[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(3)]] >>> P = Poset((elms, rels), linear_extension=True) >>> L = P.linear_extensions(); L The set of all linear extensions of Finite poset containing 4 elements with distinguished linear extension >>> L.cardinality() 5 >>> L.list() # needs sage.modules [[1, 2, 3, 4], [2, 1, 3, 4], [2, 1, 4, 3], [1, 4, 2, 3], [1, 2, 4, 3]] >>> L.an_element() [1, 2, 3, 4] >>> L.poset() Finite poset containing 4 elements with distinguished linear extension
- Element[source]#
alias of
LinearExtensionOfPoset
- cardinality()[source]#
Return the number of linear extensions.
EXAMPLES:
sage: N = Poset({0: [2, 3], 1: [3]}) sage: N.linear_extensions().cardinality() 5
>>> from sage.all import * >>> N = Poset({Integer(0): [Integer(2), Integer(3)], Integer(1): [Integer(3)]}) >>> N.linear_extensions().cardinality() 5
- markov_chain_digraph(action='promotion', labeling='identity')[source]#
Return the digraph of the action of generalized promotion or tau on
selfINPUT:
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()) ifactionis set topromotionand \(\tau_i\) (seetau()) ifactionis set totau. The label of the edge is \(i\) (resp. \(\pi_i\)) iflabelingis 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: G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: G.edges(sort=True, 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: G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: G.edges(sort=True, 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)]
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(3)]]), linear_extension=True) >>> L = P.linear_extensions() >>> G = L.markov_chain_digraph(); G Looped multi-digraph on 5 vertices >>> G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] >>> G.edges(sort=True, 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)] >>> G = L.markov_chain_digraph(labeling='source') >>> G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] >>> G.edges(sort=True, 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)
>>> from sage.all import * >>> view(G) # optional - dot2tex graphviz, not tested (opens external window)
Alternatively, one may get the graph of the action of the
tauoperator:sage: G = L.markov_chain_digraph(action='tau'); G Looped multi-digraph on 5 vertices sage: G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] sage: G.edges(sort=True, 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)
>>> from sage.all import * >>> G = L.markov_chain_digraph(action='tau'); G Looped multi-digraph on 5 vertices >>> G.vertices(sort=True, key=repr) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]] >>> G.edges(sort=True, 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)] >>> view(G) # optional - dot2tex graphviz, not tested (opens external window)
See also
markov_chain_transition_matrix(),promotion(),tau()
- markov_chain_transition_matrix(action='promotion', labeling='identity')[source]#
Return the transition matrix of the Markov chain for the action of generalized promotion or tau on
selfINPUT:
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
labelingis 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() # needs sage.modules [-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') # needs sage.modules [-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') # needs sage.modules [ -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') # needs sage.modules [ -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]
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(3)]]), linear_extension=True) >>> L = P.linear_extensions() >>> L.markov_chain_transition_matrix() # needs sage.modules [-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] >>> L.markov_chain_transition_matrix(labeling='source') # needs sage.modules [-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] >>> L.markov_chain_transition_matrix(action='tau') # needs sage.modules [ -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] >>> L.markov_chain_transition_matrix(action='tau', labeling='source') # needs sage.modules [ -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()[source]#
Return 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
>>> from sage.all import * >>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(2)],[Integer(2),Integer(3)],[Integer(1),Integer(4)]])) >>> L = P.linear_extensions() >>> L.poset() Finite poset containing 4 elements
- class sage.combinat.posets.linear_extensions.LinearExtensionsOfPosetWithHooks(poset, facade)[source]#
Bases:
LinearExtensionsOfPosetLinear extensions such that the poset has well-defined hook lengths (i.e., d-complete).
- cardinality()[source]#
Count the number of linear extensions using a hook-length formula.
EXAMPLES:
sage: from sage.combinat.posets.poset_examples import Posets sage: P = Posets.YoungDiagramPoset(Partition([3,2]), dual=True) # needs sage.combinat sage.modules sage: P.linear_extensions().cardinality() # needs sage.combinat sage.modules 5
>>> from sage.all import * >>> from sage.combinat.posets.poset_examples import Posets >>> P = Posets.YoungDiagramPoset(Partition([Integer(3),Integer(2)]), dual=True) # needs sage.combinat sage.modules >>> P.linear_extensions().cardinality() # needs sage.combinat sage.modules 5