Bases: sage.categories.category.Category
The category of finite posets i.e. finite sets with a partial order structure.
EXAMPLES:
sage: FinitePosets()
Category of finite posets
sage: FinitePosets().super_categories()
[Category of posets, Category of finite enumerated sets]
sage: FinitePosets().example()
NotImplemented
TESTS:
sage: C = FinitePosets()
sage: TestSuite(C).run()
Returns all antichains of self.
EXAMPLES:
sage: A = Posets.PentagonPoset().antichains(); A
Set of antichains of Finite lattice containing 5 elements
sage: list(A)
[[], [0], [1], [1, 2], [1, 3], [2], [3], [4]]
Returns whether this poset is both a meet and a join semilattice.
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]])
sage: P.is_lattice()
True
sage: P = Poset([[1,2],[3],[3],[]])
sage: P.is_lattice()
True
sage: P = Poset({0:[2,3],1:[2,3]})
sage: P.is_lattice()
False
INPUT:
Returns whether is an isomorphism of posets form
self to codomain.
EXAMPLES:
We build the poset of divisors of 30, and check that
it is isomorphic to the boolean lattice
of the subsets
of
ordered by inclusion, via the reverse
function
:
sage: D = Poset((divisors(30), attrcall("divides")))
sage: B = Poset(([frozenset(s) for s in Subsets([2,3,5])], attrcall("issubset")))
sage: def f(b): return D(prod(b))
sage: B.is_poset_isomorphism(f, D)
True
On the other hand, is not an isomorphism to the chain
of divisors of 30, ordered by usual comparison:
sage: P = Poset((divisors(30), operator.le))
sage: def f(b): return P(prod(b))
sage: B.is_poset_isomorphism(f, P)
False
A non surjective case:
sage: B = Poset(([frozenset(s) for s in Subsets([2,3])], attrcall("issubset")))
sage: def f(b): return D(prod(b))
sage: B.is_poset_isomorphism(f, D)
False
A non injective case:
sage: B = Poset(([frozenset(s) for s in Subsets([2,3,5,6])], attrcall("issubset")))
sage: def f(b): return D(gcd(prod(b), 30))
sage: B.is_poset_isomorphism(f, D)
False
Note
since D and B are not facade posets, f is responsible for the conversions between integers and subsets to elements of D and B and back.
INPUT:
Returns whether is a morphism of posets form self
to codomain, that is
EXAMPLES:
We build the boolean lattice of the subsets of
and the lattice of divisors of
, and
check that the map
is a
morphism of posets:
sage: D = Poset((divisors(30), attrcall("divides")))
sage: B = Poset(([frozenset(s) for s in Subsets([2,3,5,6])], attrcall("issubset")))
sage: def f(b): return D(gcd(prod(b), 30))
sage: B.is_poset_morphism(f, D)
True
Note
since D and B are not facade posets, f is responsible for the conversions between integers and subsets to elements of D and B and back.
is also a morphism of posets to the chain of divisors
of 30, ordered by usual comparison:
sage: P = Poset((divisors(30), operator.le))
sage: def f(b): return P(gcd(prod(b), 30))
sage: B.is_poset_morphism(f, P)
True
FIXME: should this be is_order_preserving_morphism?
See also
TESTS:
Base cases:
sage: P = Posets.ChainPoset(2)
sage: Q = Posets.AntichainPoset(2)
sage: f = lambda x: 1-x
sage: P.is_poset_morphism(f, P)
False
sage: P.is_poset_morphism(f, Q)
False
sage: Q.is_poset_morphism(f, Q)
True
sage: Q.is_poset_morphism(f, P)
True
sage: P = Poset(); P
Finite poset containing 0 elements
sage: P.is_poset_morphism(f, P)
True
Returns whether this poset is self-dual, that is isomorphic to its dual poset.
EXAMPLE:
sage: P = Poset(([1,2,3],[[1,3],[2,3]]),cover_relations=True)
sage: P.is_selfdual()
False
sage: P = Poset(([1,2,3,4],[[1,3],[1,4],[2,3],[2,4]]),cover_relations=True)
sage: P.is_selfdual()
True
Generators for an order filter
INPUT:
EXAMPLES:
sage: P = Poset((Subsets([1,2,3]), attrcall("issubset")))
sage: I = P.order_filter([Set([1,2]), Set([2,3]), Set([1])]); I
[{1}, {1, 3}, {1, 2}, {2, 3}, {1, 2, 3}]
sage: P.order_filter_generators(I)
{{2, 3}, {1}}
See also
The generators of the complement of an order ideal.
INPUT:
Returns the minimal set of generators for the complement. It forms an antichain.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: P.order_ideal_complement_generators([1])
set([2])
sage: P.order_ideal_complement_generators([1,2])
set([3])
sage: P.order_ideal_complement_generators([1,2,3])
set([])
Generators for an order ideal (resp. filter)
INPUT:
Returns the minimal set of generators for the ideal
. It forms an antichain.
EXAMPLES:
We build the boolean lattice of all subsets of
ordered by inclusion, and compute an order ideal there:
sage: P = Poset((Subsets([1,2,3]), attrcall("issubset")))
sage: I = P.order_ideal([Set([1,2]), Set([2,3]), Set([1])]); I
[{}, {1}, {3}, {2}, {1, 2}, {2, 3}]
Then, we retrieve the generators of this ideal:
sage: P.order_ideal_generators(I)
{{1, 2}, {2, 3}}
If direction is ‘up’, then this instead computes the minimal generators for an upper ideal:
sage: I = P.order_filter([Set([1,2]), Set([2,3]), Set([1])]); I
[{1}, {1, 3}, {1, 2}, {2, 3}, {1, 2, 3}]
sage: P.order_ideal_generators(I, direction='up')
{{2, 3}, {1}}
Complexity: where
is the cardinality of
,
and
the number of upper covers of elements of
.
Returns the lattice of order ideals of a poset ,
ordered by inclusion. The usual notation is
.
EXAMPLES:
sage: P = Posets.PentagonPoset(facade = True)
sage: P.cover_relations()
[[0, 1], [0, 2], [1, 4], [2, 3], [3, 4]]
sage: J = P.order_ideals_lattice(); J
Finite lattice containing 8 elements
sage: list(J)
[{}, {0}, {0, 2}, {0, 1}, {0, 1, 2}, {0, 2, 3}, {0, 1, 2, 3}, {0, 1, 2, 3, 4}]
TESTS:
sage: J = Posets.DiamondPoset(4, facade = True).order_ideals_lattice(); J
Finite lattice containing 6 elements
sage: list(J)
[{}, {0}, {0, 2}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}]
sage: J.cover_relations()
[[{}, {0}], [{0}, {0, 2}], [{0}, {0, 1}], [{0, 2}, {0, 1, 2}], [{0, 1}, {0, 1, 2}], [{0, 1, 2}, {0, 1, 2, 3}]]
Note
we use facade posets in the examples above just to ensure a nicer ordering in the output.
The generators of the complement of an order ideal.
INPUT:
Returns the minimal set of generators for the complement. It forms an antichain.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: P.order_ideal_complement_generators([1])
set([2])
sage: P.order_ideal_complement_generators([1,2])
set([3])
sage: P.order_ideal_complement_generators([1,2,3])
set([])
Returns the Panyushev orbits of antichains in self
OUTPUT:
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: P.panyushev_orbits()
[[set([2]), set([1])], [set([]), set([1, 2]), set([3])]]
Returns a list of the (immediate) super categories of self, as per Category.super_categories().
EXAMPLES:
sage: FinitePosets().super_categories()
[Category of posets, Category of finite enumerated sets]