A catalog of posets and lattices.

Some common posets can be accessed through the posets.<tab> object:

sage: posets.PentagonPoset()
Finite lattice containing 5 elements

Moreover, the set of all posets of order \(n\) is represented by Posets(n):

sage: Posets(5)
Posets containing 5 elements

Catalog of common posets:

AntichainPoset() Return an antichain on \(n\) elements.
BooleanLattice() Return the Boolean lattice on \(2^n\) elements.
ChainPoset() Return a chain on \(n\) elements.
DiamondPoset() Return the lattice of rank two on \(n\) elements.
DivisorLattice() Return the divisor lattice of an integer.
IntegerCompositions() Return the poset of integer compositions of \(n\).
IntegerPartitions() Return the poset of integer partitions of n.
IntegerPartitionsDominanceOrder() Return the poset of integer partitions on the integer \(n\) ordered by dominance.
PentagonPoset() Return the Pentagon poset.
RandomLattice() Return a random lattice on \(n\) elements.
RandomPoset() Return a random poset on \(n\) elements.
RestrictedIntegerPartitions() Return the poset of integer partitions of \(n\), ordered by restricted refinement.
SetPartitions() Return the poset of set partitions of the set \(\{1,\dots,n\}\).
ShardPoset() Return the shard intersection order.
SSTPoset() Return the poset on semistandard tableaux of shape \(s\) and largest entry \(f\) that is ordered by componentwise comparison.
StandardExample() Return the standard example of a poset with dimension \(n\).
SymmetricGroupAbsoluteOrderPoset() The poset of permutations with respect to absolute order.
SymmetricGroupBruhatIntervalPoset() The poset of permutations with respect to Bruhat order.
SymmetricGroupBruhatOrderPoset() The poset of permutations with respect to Bruhat order.
SymmetricGroupWeakOrderPoset() The poset of permutations of \(\{ 1, 2, \ldots, n \}\) with respect to the weak order.
TamariLattice() Return the Tamari lattice.
TetrahedralPoset() Return the Tetrahedral poset with \(n-1\) layers based on the input colors.
UpDownPoset() Return the up-down poset on \(n\) elements.
YoungDiagramPoset() Return the poset of cells in the Young diagram of a partition.
YoungsLattice() Return Young’s Lattice up to rank \(n\).
YoungsLatticePrincipalOrderIdeal() Return the principal order ideal of the partition \(lam\) in Young’s Lattice.

Constructions

class sage.combinat.posets.poset_examples.Posets

Bases: object

A collection of posets and lattices.

EXAMPLES:

sage: Posets.BooleanLattice(3)
Finite lattice containing 8 elements
sage: Posets.ChainPoset(3)
Finite lattice containing 3 elements
sage: Posets.RandomPoset(17,.15)
Finite poset containing 17 elements

The category of all posets:

sage: Posets()
Category of posets

The enumerated set of all posets on \(3\) elements, up to an isomorphism:

sage: Posets(3)
Posets containing 3 elements

TESTS:

sage: P = Posets
sage: TestSuite(P).run()
static AntichainPoset(n, facade=None)

Return an antichain (a poset with no comparable elements) containing \(n\) elements.

INPUT:

  • n (an integer) – number of elements
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: A = Posets.AntichainPoset(6); A
Finite poset containing 6 elements

TESTS:

sage: for i in range(5):
....:     for j in range(5):
....:         if A.covers(A(i),A(j)):
....:             print("TEST FAILED")

TESTS:

Check that trac ticket #8422 is solved:

sage: Posets.AntichainPoset(0)
Finite poset containing 0 elements
sage: C = Posets.AntichainPoset(1); C
Finite poset containing 1 elements
sage: C.cover_relations()
[]
sage: C = Posets.AntichainPoset(2); C
Finite poset containing 2 elements
sage: C.cover_relations()
[]
static BooleanLattice(n, facade=None)

Return the Boolean lattice containing \(2^n\) elements.

  • n (an integer) – number of elements will be \(2^n\)
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: Posets.BooleanLattice(5)
Finite lattice containing 32 elements
static ChainPoset(n, facade=None)

Return a chain (a totally ordered poset) containing n elements.

  • n (an integer) – number of elements.
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: C = Posets.ChainPoset(6); C
Finite lattice containing 6 elements
sage: C.linear_extension()
[0, 1, 2, 3, 4, 5]

TESTS:

sage: for i in range(5):
....:     for j in range(5):
....:         if C.covers(C(i),C(j)) and j != i+1:
....:             print("TEST FAILED")

Check that trac ticket #8422 is solved:

sage: Posets.ChainPoset(0)
Finite lattice containing 0 elements
sage: C = Posets.ChainPoset(1); C
Finite lattice containing 1 elements
sage: C.cover_relations()
[]
sage: C = Posets.ChainPoset(2); C
Finite lattice containing 2 elements
sage: C.cover_relations()
[[0, 1]]
static CoxeterGroupAbsoluteOrderPoset(W, use_reduced_words=True)

Return the poset of elements of a Coxeter group with respect to absolute order.

INPUT:

  • W – a Coxeter group
  • use_reduced_words – boolean (default: True); if True, then the elements are labeled by their lexicographically minimal reduced word

EXAMPLES:

sage: W = CoxeterGroup(['B', 3])
sage: Posets.CoxeterGroupAbsoluteOrderPoset(W)
Finite poset containing 48 elements

sage: W = WeylGroup(['B', 2], prefix='s')
sage: Posets.CoxeterGroupAbsoluteOrderPoset(W, False)
Finite poset containing 8 elements
static DiamondPoset(n, facade=None)

Return the lattice of rank two containing n elements.

INPUT:

  • n – number of elements, an integer at least 3
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: Posets.DiamondPoset(7)
Finite lattice containing 7 elements
static DivisorLattice(n, facade=None)

Return the divisor lattice of an integer.

Elements of the lattice are divisors of \(n\) and \(x < y\) in the lattice if \(x\) divides \(y\).

INPUT:

  • n – an integer
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: P = Posets.DivisorLattice(12)
sage: sorted(P.cover_relations())
[[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]]

sage: P = Posets.DivisorLattice(10, facade=False)
sage: P(2) < P(5)
False

TESTS:

sage: Posets.DivisorLattice(1)
Finite lattice containing 1 elements
static IntegerCompositions(n)

Returns the poset of integer compositions of the integer n.

A composition of a positive integer \(n\) is a list of positive integers that sum to \(n\). The order is reverse refinement: \([p_1,p_2,...,p_l] < [q_1,q_2,...,q_m]\) if \(q\) consists of an integer composition of \(p_1\), followed by an integer composition of \(p_2\), and so on.

EXAMPLES:

sage: P = Posets.IntegerCompositions(7); P
Finite poset containing 64 elements
sage: len(P.cover_relations())
192
static IntegerPartitions(n)

Returns the poset of integer partitions on the integer n.

A partition of a positive integer \(n\) is a non-increasing list of positive integers that sum to \(n\). If \(p\) and \(q\) are integer partitions of \(n\), then \(p\) covers \(q\) if and only if \(q\) is obtained from \(p\) by joining two parts of \(p\) (and sorting, if necessary).

EXAMPLES:

sage: P = Posets.IntegerPartitions(7); P
Finite poset containing 15 elements
sage: len(P.cover_relations())
28
static IntegerPartitionsDominanceOrder(n)

Return the poset of integer partitions on the integer \(n\) ordered by dominance.

That is, if \(p=(p_1,\ldots,p_i)\) and \(q=(q_1,\ldots,q_j)\) are integer partitions of \(n\), then \(p\) is greater than \(q\) if and only if \(p_1+\cdots+p_k > q_1+\cdots+q_k\) for all \(k\).

INPUT:

  • n – a positive integer

EXAMPLES:

sage: P = Posets.IntegerPartitionsDominanceOrder(6); P
Finite lattice containing 11 elements
sage: P.cover_relations()
[[[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1]],
 [[2, 1, 1, 1, 1], [2, 2, 1, 1]],
 [[2, 2, 1, 1], [2, 2, 2]],
 [[2, 2, 1, 1], [3, 1, 1, 1]],
 [[2, 2, 2], [3, 2, 1]],
 [[3, 1, 1, 1], [3, 2, 1]],
 [[3, 2, 1], [3, 3]],
 [[3, 2, 1], [4, 1, 1]],
 [[3, 3], [4, 2]],
 [[4, 1, 1], [4, 2]],
 [[4, 2], [5, 1]],
 [[5, 1], [6]]]
static PentagonPoset(facade=None)

Return the Pentagon poset.

INPUT:

  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

EXAMPLES:

sage: P = Posets.PentagonPoset(); P
Finite lattice containing 5 elements
sage: P.cover_relations()
[[0, 1], [0, 2], [1, 4], [2, 3], [3, 4]]

This is smallest lattice that is not modular:

sage: P.is_modular()
False

This poset and the DiamondPoset() are the two smallest lattices which are not distributive:

sage: P.is_distributive()
False
sage: Posets.DiamondPoset(5).is_distributive()
False
static RandomLattice(n, p, properties=None)

Return a random lattice on n elements.

INPUT:

  • n – number of elements, a non-negative integer
  • p – a probability, a positive real number less than one
  • properties – a list of properties for the lattice. Currently implemented:
    • None, no restrictions for lattices to create
    • 'planar', the lattice has an upward planar drawing
    • 'dismantlable' (implicated by 'planar')
    • 'distributive'

OUTPUT:

A lattice on \(n\) elements. When properties is None, the probability \(p\) roughly measures number of covering relations of the lattice. To create interesting examples, make the probability near one, something like \(0.98..0.999\).

Currently parameter p has no effect only when properties is not None.

Note

Results are reproducible in same Sage version only. Underlying algorithm may change in future versions.

EXAMPLES:

sage: set_random_seed(0)  # Results are reproducible
sage: L = Posets.RandomLattice(8, 0.995); L
Finite lattice containing 8 elements
sage: L.cover_relations()
[[8, 7], [8, 4], [8, 2], ..., [6, 5], [3, 5], [2, 5], [1, 5]]
sage: L = Posets.RandomLattice(10, 0, properties=['dismantlable'])
sage: L.is_dismantlable()
True

TESTS:

sage: Posets.RandomLattice('junk', 0.5)
Traceback (most recent call last):
...
TypeError: number of elements must be an integer, not junk

sage: Posets.RandomLattice(-6, 0.5)
Traceback (most recent call last):
...
ValueError: number of elements must be non-negative, not -6

sage: Posets.RandomLattice(6, 'garbage')
Traceback (most recent call last):
...
TypeError: probability must be a real number, not garbage

sage: Posets.RandomLattice(6, -0.5)
Traceback (most recent call last):
...
ValueError: probability must be a positive real number and below 1, not -0.5

sage: Posets.RandomLattice(10, 0.5, properties=['junk'])
Traceback (most recent call last):
...
ValueError: unknown value junk for 'properties'

sage: Posets.RandomLattice(0, 0.5)
Finite lattice containing 0 elements
static RandomPoset(n, p)

Generate a random poset on n elements according to a probability p.

INPUT:

  • n - number of elements, a non-negative integer
  • p - a probability, a real number between 0 and 1 (inclusive)

OUTPUT:

A poset on \(n\) elements. The probability \(p\) roughly measures width/height of the output: \(p=0\) always generates an antichain, \(p=1\) will return a chain. To create interesting examples, keep the probability small, perhaps on the order of \(1/n\).

EXAMPLES:

sage: set_random_seed(0)  # Results are reproducible
sage: P = Posets.RandomPoset(5, 0.3)
sage: P.cover_relations()
[[5, 4], [4, 2], [1, 2]]

TESTS:

sage: Posets.RandomPoset('junk', 0.5)
Traceback (most recent call last):
...
TypeError: number of elements must be an integer, not junk

sage: Posets.RandomPoset(-6, 0.5)
Traceback (most recent call last):
...
ValueError: number of elements must be non-negative, not -6

sage: Posets.RandomPoset(6, 'garbage')
Traceback (most recent call last):
...
TypeError: probability must be a real number, not garbage

sage: Posets.RandomPoset(6, -0.5)
Traceback (most recent call last):
...
ValueError: probability must be between 0 and 1, not -0.5

sage: Posets.RandomPoset(0, 0.5)
Finite poset containing 0 elements
static RestrictedIntegerPartitions(n)

Returns the poset of integer partitions on the integer \(n\) ordered by restricted refinement. That is, if \(p\) and \(q\) are integer partitions of \(n\), then \(p\) covers \(q\) if and only if \(q\) is obtained from \(p\) by joining two distinct parts of \(p\) (and sorting, if necessary).

EXAMPLES:

sage: P = Posets.RestrictedIntegerPartitions(7); P
Finite poset containing 15 elements
sage: len(P.cover_relations())
17
static SSTPoset(s, f=None)

The poset on semistandard tableaux of shape s and largest entry f that is ordered by componentwise comparison of the entries.

INPUT:

  • s - shape of the tableaux
  • f - maximum fill number. This is an optional argument. If no maximal number is given, it will use the number of cells in the shape.

NOTE: This is a basic implementation and most certainly not the most efficient.

EXAMPLES:

sage: Posets.SSTPoset([2,1])
Finite poset containing 8 elements

sage: Posets.SSTPoset([2,1],4)
Finite poset containing 20 elements

sage: Posets.SSTPoset([2,1],2).cover_relations()
[[[[1, 1], [2]], [[1, 2], [2]]]]

sage: Posets.SSTPoset([3,2]).bottom()  # long time (6s on sage.math, 2012)
[[1, 1, 1], [2, 2]]

sage: Posets.SSTPoset([3,2],4).maximal_elements()
[[[3, 3, 4], [4, 4]]]
static SetPartitions(n)

Return the lattice of set partitions of the set \(\{1,\ldots,n\}\) ordered by refinement.

INPUT:

  • n – a positive integer

EXAMPLES:

sage: Posets.SetPartitions(4)
Finite lattice containing 15 elements
static ShardPoset(n)

Return the shard intersection order on permutations of size \(n\).

This is defined on the set of permutations. To every permutation, one can attach a pre-order, using the descending runs and their relative positions.

The shard intersection order is given by the implication (or refinement) order on the set of pre-orders defined from all permutations.

This can also be seen in a geometrical way. Every pre-order defines a cone in a vector space of dimension \(n\). The shard poset is given by the inclusion of these cones.

See also

shard_preorder_graph()

EXAMPLES:

sage: P = posets.ShardPoset(4); P  # indirect doctest
Finite poset containing 24 elements
sage: P.chain_polynomial()
34*q^4 + 90*q^3 + 79*q^2 + 24*q + 1
sage: P.characteristic_polynomial()
q^3 - 11*q^2 + 23*q - 13
sage: P.zeta_polynomial()
17/3*q^3 - 6*q^2 + 4/3*q
sage: P.is_selfdual()
False
static StandardExample(n, facade=None)

Return the partially ordered set on 2n elements with dimension n.

Let \(P\) be the poset on \(\{0, 1, 2, \ldots, 2n-1\}\) whose defining relations are that \(i < j\) for every \(0 \leq i < n \leq j < 2n\) except when \(i + n = j\). The poset \(P\) is the so-called standard example of a poset with dimension \(n\).

INPUT:

  • n – an integer \(\ge 2\), dimension of the constructed poset
  • facade (boolean) – whether to make the returned poset a facade poset (see sage.categories.facade_sets); the default behaviour is the same as the default behaviour of the Poset() constructor

OUTPUT:

The standard example of a poset of dimension \(n\).

EXAMPLES:

sage: A = Posets.StandardExample(3); A
Finite poset containing 6 elements
sage: A.dimension()
3

REFERENCES:

[Rosen]K. Rosen Handbook of Discrete and Combinatorial Mathematics (1999), Chapman and Hall.
[Garg]V. Garg Introduction to Lattice Theory with Computer Science Applications (2015), Wiley.

TESTS:

sage: A = Posets.StandardExample(10); A
Finite poset containing 20 elements
sage: len(A.cover_relations())
90

sage: P = Posets.StandardExample(5, facade=False)
sage: P(4) < P(3), P(4) > P(3)
(False, False)
static SymmetricGroupAbsoluteOrderPoset(n, labels='permutations')

Return the poset of permutations with respect to absolute order.

INPUT:

  • n – a positive integer
  • label – (default: 'permutations') a label for the elements of the poset returned by the function; the options are
    • 'permutations' - labels the elements are given by their one-line notation
    • 'reduced_words' - labels the elements by the lexicographically minimal reduced word
    • 'cycles' - labels the elements by their expression as a product of cycles

EXAMPLES:

sage: Posets.SymmetricGroupAbsoluteOrderPoset(4)
Finite poset containing 24 elements
sage: Posets.SymmetricGroupAbsoluteOrderPoset(3, labels="cycles")
Finite poset containing 6 elements
sage: Posets.SymmetricGroupAbsoluteOrderPoset(3, labels="reduced_words")
Finite poset containing 6 elements
static SymmetricGroupBruhatIntervalPoset(start, end)

The poset of permutations with respect to Bruhat order.

INPUT:

  • start - list permutation
  • end - list permutation (same n, of course)

Note

Must have start <= end.

EXAMPLES:

Any interval is rank symmetric if and only if it avoids these permutations:

sage: P1 = Posets.SymmetricGroupBruhatIntervalPoset([1,2,3,4], [3,4,1,2])
sage: P2 = Posets.SymmetricGroupBruhatIntervalPoset([1,2,3,4], [4,2,3,1])
sage: ranks1 = [P1.rank(v) for v in P1]
sage: ranks2 = [P2.rank(v) for v in P2]
sage: [ranks1.count(i) for i in uniq(ranks1)]
[1, 3, 5, 4, 1]
sage: [ranks2.count(i) for i in uniq(ranks2)]
[1, 3, 5, 6, 4, 1]
static SymmetricGroupBruhatOrderPoset(n)

The poset of permutations with respect to Bruhat order.

EXAMPLES:

sage: Posets.SymmetricGroupBruhatOrderPoset(4)
Finite poset containing 24 elements
static SymmetricGroupWeakOrderPoset(n, labels='permutations', side='right')

The poset of permutations of \(\{ 1, 2, \ldots, n \}\) with respect to the weak order (also known as the permutohedron order, cf. permutohedron_lequal()).

The optional variable labels (default: "permutations") determines the labelling of the elements if \(n < 10\). The optional variable side (default: "right") determines whether the right or the left permutohedron order is to be used.

EXAMPLES:

sage: Posets.SymmetricGroupWeakOrderPoset(4)
Finite poset containing 24 elements
static TamariLattice(n)

Return the \(n\)-th Tamari lattice.

INPUT:

  • \(n\) a nonnegative integer

OUTPUT:

  • a finite lattice

The elements of the lattice are Dyck paths in the \((n+1 \times n)\)-rectangle.

See Tamari lattice for mathematical background.

EXAMPLES:

sage: posets.TamariLattice(3)
Finite lattice containing 5 elements
static TetrahedralPoset(n, *colors, **labels)

Return the tetrahedral poset based on the input colors.

This method will return the tetrahedral poset with n-1 layers and covering relations based on the input colors of ‘green’, ‘red’, ‘orange’, ‘silver’, ‘yellow’ and ‘blue’ as defined in [Striker2011]. For particular color choices, the order ideals of the resulting tetrahedral poset will be isomorphic to known combinatorial objects.

For example, for the colors ‘blue’, ‘yellow’, ‘orange’, and ‘green’, the order ideals will be in bijection with alternating sign matrices. For the colors ‘yellow’, ‘orange’, and ‘green’, the order ideals will be in bijection with semistandard Young tableaux of staircase shape. For the colors ‘red’, ‘orange’, ‘green’, and optionally ‘yellow’, the order ideals will be in bijection with totally symmetric self-complementary plane partitions in a \(2n \times 2n \times 2n\) box.

INPUT:

  • n - Defines the number (n-1) of layers in the poset.
  • colors - The colors that define the covering relations of the poset. Colors used are ‘green’, ‘red’, ‘yellow’, ‘orange’, ‘silver’, and ‘blue’.
  • labels - Keyword variable used to determine whether the poset is labeled with integers or tuples. To label with integers, the method should be called with labels='integers'. Otherwise, the labeling will default to tuples.

EXAMPLES:

sage: Posets.TetrahedralPoset(4,'green','red','yellow','silver','blue','orange')
Finite poset containing 10 elements

sage: Posets.TetrahedralPoset(4,'green','red','yellow','silver','blue','orange', labels='integers')
Finite poset containing 10 elements

sage: A = AlternatingSignMatrices(3)
sage: p = A.lattice()
sage: ji = p.join_irreducibles_poset()
sage: tet = Posets.TetrahedralPoset(3, 'green','yellow','blue','orange')
sage: ji.is_isomorphic(tet)
True

REFERENCES:

[Striker2011]J. Striker. A unifying poset perpective on alternating sign matrices, plane partitions, Catalan objects, tournaments, and tableaux, Advances in Applied Mathematics 46 (2011), no. 4, 583-609. Arxiv 1408.5391
static UpDownPoset(n, m=1)

Return the up-down poset on \(n\) elements where every \((m+1)\) step is down and the rest are up.

The case where \(m=1\) is sometimes referred to as the zig-zag poset or the fence.

INPUT:

  • n - nonnegative integer, number of elements in the poset
  • m - nonnegative integer (default 1), how frequently down steps occur

OUTPUT:

The partially ordered set on \(\{ 0, 1, \ldots, n-1 \}\) where \(i\) covers \(i+1\) if \(m\) divides \(i+1\), and \(i+1\) covers \(i\) otherwise.

EXAMPLES:

sage: P = Posets.UpDownPoset(7, 2); P
Finite poset containing 7 elements
sage: sorted(P.cover_relations())
[[0, 1], [1, 2], [3, 2], [3, 4], [4, 5], [6, 5]]

Fibonacci numbers as the number of antichains of a poset:

sage: [len(Posets.UpDownPoset(n).antichains().list()) for n in range(0, 6)]
[1, 2, 3, 5, 8, 13]

TESTS:

sage: P = Posets.UpDownPoset(0); P
Finite poset containing 0 elements
static YoungDiagramPoset(lam)

Return the poset of cells in the Young diagram of a partition.

INPUT:

  • lam – a partition

EXAMPLES:

sage: P = Posets.YoungDiagramPoset(Partition([2,2])); P
Finite meet-semilattice containing 4 elements
sage: P.cover_relations()
[[(0, 0), (0, 1)], [(0, 0), (1, 0)], [(0, 1), (1, 1)], [(1, 0),
(1, 1)]]
static YoungsLattice(n)

Return Young’s Lattice up to rank \(n\).

In other words, the poset of partitions of size less than or equal to \(n\) ordered by inclusion.

INPUT:

  • n – a positive integer

EXAMPLES:

sage: P = Posets.YoungsLattice(3); P
Finite meet-semilattice containing 7 elements
sage: P.cover_relations()
[[[], [1]],
 [[1], [1, 1]],
 [[1], [2]],
 [[1, 1], [1, 1, 1]],
 [[1, 1], [2, 1]],
 [[2], [2, 1]],
 [[2], [3]]]
static YoungsLatticePrincipalOrderIdeal(lam)

Return the principal order ideal of the partition \(lam\) in Young’s Lattice.

INPUT:

  • lam – a partition

EXAMPLES:

sage: P = Posets.YoungsLatticePrincipalOrderIdeal(Partition([2,2]))
sage: P
Finite lattice containing 6 elements
sage: P.cover_relations()
[[[], [1]],
 [[1], [1, 1]],
 [[1], [2]],
 [[1, 1], [2, 1]],
 [[2], [2, 1]],
 [[2, 1], [2, 2]]]
sage.combinat.posets.poset_examples.posets

alias of Posets