Macaulay2 » Documentation
Packages » Posets :: linearExtensions
next | previous | forward | backward | up | index | toc

# linearExtensions -- computes all linear extensions of a poset

- Usage:
    `L = linearExtensions P`
- Inputs:
  - P, an instance of the type Poset,
- Outputs:
  - L, a list, all possible linear extensions of $P$

## Description

A linear extension of the partial order on $P$ is a total order on the elements of $P$ that is compatible with the partial order.

    i1 : P = divisorPoset 12;

    i2 : L = linearExtensions P

    o2 = {{1, 2, 3, 6, 4, 12}, {1, 2, 3, 4, 6, 12}, {1, 2, 4, 3, 6, 12}, {1, 3,
         ------------------------------------------------------------------------
         2, 6, 4, 12}, {1, 3, 2, 4, 6, 12}}

    o2 : List

The flatten of the filtration of $P$ is always a linear extension. This approach is much faster, especially for posets with many linear extensions.

    i3 : F = flatten filtration P

    o3 = {1, 2, 3, 4, 6, 12}

    o3 : List

    i4 : member(F, L)

    o4 = true

The partial order of a chain is the total order of the elements.

    i5 : linearExtensions chain 10

    o5 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

    o5 : List

This method was ported from John Stembridge's Maple package available at http://www.math.lsa.umich.edu/~jrs/maple.html#posets.

## See also

- filtration -- generates the filtration of a poset

## Ways to use linearExtensions:

- `linearExtensions(Poset)`

## For the programmer

The object linearExtensions is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Posets.m2:4848:0.