# Linear Extensions of Posets#

This module defines two classes:

## Classes and methods#

class sage.combinat.posets.linear_extensions.LinearExtensionOfPoset[source]#

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

EXAMPLES:

sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]),
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)]]),
>>> 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]]

check()[source]#

Checks whether self is indeed a linear extension of the underlying poset.

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

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 True if 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 True if 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].

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 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:                                                           # 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 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

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


Linear 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


Linear 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


The 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 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()) if action is set to promotion and $$\tau_i$$ (see tau()) if action is set to tau. The label of the edge is $$i$$ (resp. $$\pi_i$$) 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: 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 tau operator:

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)


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 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 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()                                    # 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]


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


Linear 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