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

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