Here is some terminology used in this file:
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]]
Return the order filters (resp. order ideals) of self, as lists.
If direction is ‘up’, returns the order filters (upper sets).
If direction is ‘down’, returns the order ideals (lower sets).
INPUT:
EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides")), facade=True)
sage: A = P.directed_subsets('up')
sage: sorted(list(A))
[[], [1, 2, 4, 3, 6, 12], [2, 4, 3, 6, 12], [2, 4, 6, 12], [3, 6, 12], [4, 3, 6, 12], [4, 6, 12], [4, 12], [6, 12], [12]]
TESTS:
sage: list(Poset().directed_subsets('up'))
[[]]
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 (resp. order filter)
INPUT:
OUTPUT:
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([3])
set([])
sage: P.order_ideal_complement_generators([1,2])
set([3])
sage: P.order_ideal_complement_generators([1,2,3])
set([])
sage: P.order_ideal_complement_generators([1], direction="down")
set([2])
sage: P.order_ideal_complement_generators([3], direction="down")
set([1, 2])
sage: P.order_ideal_complement_generators([1,2], direction="down")
set([])
sage: P.order_ideal_complement_generators([1,2,3], direction="down")
set([])
Warning
This is a brute force implementation, building the order ideal generated by the antichain, and searching for order filter generators of its complement
Generators for an order ideal (resp. an order 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 order filter:
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
.
The underlying set is by default the set of order ideals
of . It can be alternatively chosen to be the set of
antichains of
.
INPUT:
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}]
As a lattice on antichains:
sage: J2 = P.order_ideals_lattice(False); J2
Finite lattice containing 8 elements
sage: list(J2)
[(0,), (1, 2), (1, 3), (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 (resp. order filter)
INPUT:
OUTPUT:
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([3])
set([])
sage: P.order_ideal_complement_generators([1,2])
set([3])
sage: P.order_ideal_complement_generators([1,2,3])
set([])
sage: P.order_ideal_complement_generators([1], direction="down")
set([2])
sage: P.order_ideal_complement_generators([3], direction="down")
set([1, 2])
sage: P.order_ideal_complement_generators([1,2], direction="down")
set([])
sage: P.order_ideal_complement_generators([1,2,3], direction="down")
set([])
Warning
This is a brute force implementation, building the order ideal generated by the antichain, and searching for order filter generators of its complement
Return the Panyushev orbits of antichains in self.
INPUT:
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])]]
sage: P.panyushev_orbits(element_constructor=list)
[[[2], [1]], [[], [1, 2], [3]]]
sage: P.panyushev_orbits(element_constructor=frozenset)
[[frozenset([2]), frozenset([1])],
[frozenset([]), frozenset([1, 2]), frozenset([3])]]
sage: P.panyushev_orbits(element_constructor=tuple)
[[(2,), (1,)], [(), (1, 2), (3,)]]
sage: P = Poset( {} )
sage: P.panyushev_orbits()
[[set([])]]
The image of the order ideal order_ideal under rowmotion in self.
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( {1: [2, 3], 2: [], 3: [], 4: [8], 5: [], 6: [5], 7: [1, 4], 8: []} )
sage: I = Set({2, 6, 1, 7})
sage: P.rowmotion(I)
{1, 3, 4, 5, 6, 7}
sage: P = Poset( {} )
sage: I = Set({})
sage: P.rowmotion(I)
Set of elements of {}
Return the rowmotion orbits of order ideals in self.
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( {1: [2, 3], 2: [], 3: [], 4: [2]} )
sage: sorted(len(o) for o in P.rowmotion_orbits())
[3, 5]
sage: sorted(P.rowmotion_orbits(element_constructor=list))
[[[1, 3], [4], [1], [4, 1, 3], [4, 1, 2]], [[4, 1], [4, 1, 2, 3], []]]
sage: sorted(P.rowmotion_orbits(element_constructor=tuple))
[[(1, 3), (4,), (1,), (4, 1, 3), (4, 1, 2)], [(4, 1), (4, 1, 2, 3), ()]]
sage: P = Poset({})
sage: sorted(P.rowmotion_orbits(element_constructor=tuple))
[[()]]
Returns the orbits of order ideals in self under the sequence of toggles given by vs.
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( {1: [2, 4], 2: [], 3: [4], 4: []} )
sage: sorted(len(o) for o in P.toggling_orbits([1, 2]))
[2, 3, 3]
sage: P = Poset( {1: [3], 2: [1, 4], 3: [], 4: [3]} )
sage: sorted(len(o) for o in P.toggling_orbits((1, 2, 4, 3)))
[3, 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]