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()
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 #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()
[]
Returns the Boolean lattice containing elements.
EXAMPLES:
sage: Posets.BooleanLattice(5)
Finite lattice containing 32 elements
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]]
Return the lattice of rank two containing n elements.
INPUT:
EXAMPLES:
sage: Posets.DiamondPoset(7)
Finite lattice containing 7 elements
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
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
Returns the Pentagon poset.
INPUT:
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
Generate a random poset on n vertices according to a probability p.
INPUT:
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 .
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
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
The poset on semistandard tableaux of shape s and largest entry f that is ordered by componentwise comparison of the entries.
INPUT:
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]]]
The poset of permutations with respect to Bruhat order.
INPUT:
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]
The poset of permutations with respect to Bruhat order.
EXAMPLES:
sage: Posets.SymmetricGroupBruhatOrderPoset(4)
Finite poset containing 24 elements
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