Linear Extensions of Posets¶
This module defines two classes:
Classes and methods¶
-
sage.combinat.posets.linear_extensions.
LinearExtensionOfPoset
¶ 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]]
-
sage.combinat.posets.linear_extensions.
LinearExtensionsOfPoset
¶ 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
sage.combinat.posets.posets.FinitePoset.linear_extensions()
sage.graphs.linearextensions.LinearExtensions
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], [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