# linearExtensions -- computes all linear extensions of a poset

## Synopsis

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