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 vertices

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.
IntegerCompositions()	Return the poset of integer compositions of \(n\).
IntegerPartitions()	Return the poset of integer partitions of n.
PentagonPoset()	Return the Pentagon poset.
RandomPoset()	Return a random poset on \(n\) vertices according to a probability \(p\).
RestrictedIntegerPartitions()	Return the poset of integer partitions of \(n\), ordered by restricted refinement.
SSTPoset()	Return the poset on semistandard tableaux of shape \(s\) and largest entry \(f\) that is ordered by componentwise comparison.
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.

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\) vertices, up to an isomorphism:

sage: Posets(3)
Posets containing 3 vertices

See also

Posets, FinitePosets, Poset()

TESTS:

sage: P = Posets
sage: TestSuite(P).run()

static AntichainPoset(n)

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

EXAMPLES:

sage: A = Posets.AntichainPoset(6); A
Finite poset containing 6 elements
sage: for i in range(5):
...       for j in range(5):
...           if A.covers(A(i),A(j)):
...              print "TEST FAILED"

TESTS:

Check that #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)

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

EXAMPLES:

sage: Posets.BooleanLattice(5)
Finite lattice containing 32 elements

static ChainPoset(n)

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

EXAMPLES:

sage: C = Posets.ChainPoset(6); C
Finite lattice containing 6 elements
sage: C.linear_extension()
[0, 1, 2, 3, 4, 5]
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"

TESTS:

Check that #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 DiamondPoset(n, facade=None)

Return the lattice of rank two containing n elements.

INPUT:

• n - number of vertices, 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 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 PentagonPoset(facade=None)

Returns 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 RandomPoset(n, p)

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

INPUT:

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

OUTPUT:

A poset on n vertices. The construction decides to make an ordered pair of vertices comparable in the poset with probability p, however a pair is not made comparable if it would violate the defining properties of a poset, such as transitivity.

So in practice, once the probability exceeds a small number the generated posets may be very similar to a chain. So to create interesting examples, keep the probability small, perhaps on the order of \(1/n\).

EXAMPLES:

sage: Posets.RandomPoset(17,.15)
Finite poset containing 17 elements

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

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

sage.combinat.posets.poset_examples.posets

alias of Posets