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


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


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

q-Analogues