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 is represented by
Posets(n)
:
sage: Posets(5)
Posets containing 5 vertices
Catalog of common posets:
AntichainPoset() |
Return an antichain on ![]() |
BooleanLattice() |
Return the Boolean lattice on ![]() |
ChainPoset() |
Return a chain on ![]() |
DiamondPoset() |
Return the lattice of rank two on ![]() |
IntegerCompositions() |
Return the poset of integer compositions of ![]() |
IntegerPartitions() |
Return the poset of integer partitions of n . |
PentagonPoset() |
Return the Pentagon poset. |
RandomPoset() |
Return a random poset on ![]() ![]() |
RestrictedIntegerPartitions() |
Return the poset of integer partitions of ![]() |
ShardPoset() |
Return the shard intersection order. |
SSTPoset() |
Return the poset on semistandard tableaux of shape ![]() ![]() |
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 ![]() |
TamariLattice() |
Return the Tamari 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
vertices, up to an isomorphism:
sage: Posets(3) Posets containing 3 vertices
See also
TESTS:
sage: P = Posets sage: TestSuite(P).run()
-
static
AntichainPoset
(n)¶ Returns an antichain (a poset with no comparable elements) containing
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 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)¶ Returns the Boolean lattice containing
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 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
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 (seesage.categories.facade_sets
). The default behaviour is the same as the default behaviour of thePoset()
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
is a list of positive integers that sum to
. The order is reverse refinement:
if
consists of an integer composition of
, followed by an integer composition of
, 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
is a non-increasing list of positive integers that sum to
. If
and
are integer partitions of
, then
covers
if and only if
is obtained from
by joining two parts of
(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 (seesage.categories.facade_sets
). The default behaviour is the same as the default behaviour of thePoset()
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 probabilityp
.INPUT:
n
- number of vertices, a non-negative integerp
- 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 probabilityp
, 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
.
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
ordered by restricted refinement. That is, if
and
are integer partitions of
, then
covers
if and only if
is obtained from
by joining two distinct parts of
(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 entryf
that is ordered by componentwise comparison of the entries.INPUT:
s
- shape of the tableauxf
- 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
ShardPoset
(n)¶ Return the shard intersection order on permutations of size
.
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
. 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
SymmetricGroupBruhatIntervalPoset
(start, end)¶ The poset of permutations with respect to Bruhat order.
INPUT:
start
- list permutationend
- 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
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. 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
-th Tamari lattice.
INPUT:
a nonnegative integer
OUTPUT:
- a finite lattice
The elements of the lattice are
Dyck paths
in the-rectangle.
See Tamari lattice for mathematical background.
EXAMPLES:
sage: posets.TamariLattice(3) Finite lattice containing 5 elements
-
static