A collection of posets and lattices.

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

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=False)

Returns the lattice of rank two containing n elements.

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=False)

Returns the “pentagon poset”.

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 lattice and the diamond poset on 5 elements 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

Previous topic

Linear Extensions of Posets

Next topic

Rigged Configurations

This Page