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()
Return 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
Return whether is an isomorphism of posets from
self to codomain.
INPUT:
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.
Return whether is a morphism of posets from self
to codomain, that is
for all and
in self.
INPUT:
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.
EXAMPLES:
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
sage: P = Poset( {} )
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
Return the Panyushev complement of the antichain antichain.
Given an antichain of a poset
, the Panyushev
complement of
is defined to be the antichain consisting
of the minimal elements of the order filter
, where
is the (set-theoretic) complement of the order ideal of
generated by
.
Setting the optional keyword variable direction to
'down' leads to the inverse Panyushev complement being
computed instead of the Panyushev complement. The inverse
Panyushev complement of an antichain is the antichain
whose Panyushev complement is
. It can be found as the
antichain consisting of the maximal elements of the order
ideal
, where
is the (set-theoretic) complement of
the order filter of
generated by
.
panyushev_complement() is an alias for this method.
Panyushev complementation is related (actually, isomorphic) to rowmotion (rowmotion()).
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 antichain of (minimal) generators of the order ideal (resp. order filter) ideal.
INPUT:
The antichain of (minimal) generators of an order ideal
in a poset
is the set of all minimal elements of
. In the case of an order filter, the definition is
similar, but with “maximal” used instead of “minimal”.
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
.
Return the lattice of order ideals of a poset self, ordered by inclusion.
The lattice of order ideals of a poset is usually
denoted by
. Its underlying set is the set of order
ideals of
, and its partial order is given by
inclusion.
The order ideals of are in a canonical bijection
with the antichains of
. The bijection maps every
order ideal to the antichain formed by its maximal
elements. By setting the as_ideals keyword variable to
False, one can make this method apply this bijection
before returning the lattice.
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.
Return the Panyushev complement of the antichain antichain.
Given an antichain of a poset
, the Panyushev
complement of
is defined to be the antichain consisting
of the minimal elements of the order filter
, where
is the (set-theoretic) complement of the order ideal of
generated by
.
Setting the optional keyword variable direction to
'down' leads to the inverse Panyushev complement being
computed instead of the Panyushev complement. The inverse
Panyushev complement of an antichain is the antichain
whose Panyushev complement is
. It can be found as the
antichain consisting of the maximal elements of the order
ideal
, where
is the (set-theoretic) complement of
the order filter of
generated by
.
panyushev_complement() is an alias for this method.
Panyushev complementation is related (actually, isomorphic) to rowmotion (rowmotion()).
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
Iterate over the Panyushev orbit of an antichain antichain of self.
The Panyushev orbit of an antichain is its orbit under Panyushev complementation (see panyushev_complement()).
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: list(P.panyushev_orbit_iter(set([1, 2])))
[set([1, 2]), set([3]), set([])]
sage: list(P.panyushev_orbit_iter([1, 2]))
[set([1, 2]), set([3]), set([])]
sage: list(P.panyushev_orbit_iter([2, 1]))
[set([1, 2]), set([3]), set([])]
sage: list(P.panyushev_orbit_iter(set([1, 2]), element_constructor=list))
[[1, 2], [3], []]
sage: list(P.panyushev_orbit_iter(set([1, 2]), element_constructor=frozenset))
[frozenset([1, 2]), frozenset([3]), frozenset([])]
sage: list(P.panyushev_orbit_iter(set([1, 2]), element_constructor=tuple))
[(1, 2), (3,), ()]
sage: P = Poset( {} )
sage: list(P.panyushev_orbit_iter([]))
[set([])]
sage: P = Poset({ 1: [2, 3], 2: [4], 3: [4], 4: [] })
sage: Piter = P.panyushev_orbit_iter([2], stop=False)
sage: Piter.next()
set([2])
sage: Piter.next()
set([3])
sage: Piter.next()
set([2])
sage: Piter.next()
set([3])
Return the Panyushev orbits of antichains in self.
The Panyushev orbit of an antichain is its orbit under Panyushev complementation (see panyushev_complement()).
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.
Rowmotion on a finite poset is an automorphism of the set
of all order ideals of
. One way to define it is as
follows: Given an order ideal
, we let
be the
set-theoretic complement of
in
. Furthermore we let
be the antichain consisting of all minimal elements of
. Then, the rowmotion of
is defined to be the order
ideal of
generated by the antichain
(that is, the
order ideal consisting of each element of
which has some
element of
above it).
Rowmotion is related (actually, isomorphic) to Panyushev complementation (panyushev_complement()).
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 {}
Iterate over the rowmotion orbit of an order ideal oideal of self.
The rowmotion orbit of an order ideal is its orbit under rowmotion (see rowmotion()).
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: list(P.rowmotion_orbit_iter(set([1, 2])))
[set([1, 2]), set([1, 2, 3]), set([])]
sage: list(P.rowmotion_orbit_iter([1, 2]))
[set([1, 2]), set([1, 2, 3]), set([])]
sage: list(P.rowmotion_orbit_iter([2, 1]))
[set([1, 2]), set([1, 2, 3]), set([])]
sage: list(P.rowmotion_orbit_iter(set([1, 2]), element_constructor=list))
[[1, 2], [1, 2, 3], []]
sage: list(P.rowmotion_orbit_iter(set([1, 2]), element_constructor=frozenset))
[frozenset([1, 2]), frozenset([1, 2, 3]), frozenset([])]
sage: list(P.rowmotion_orbit_iter(set([1, 2]), element_constructor=tuple))
[(1, 2), (1, 2, 3), ()]
sage: P = Poset( {} )
sage: list(P.rowmotion_orbit_iter([]))
[set([])]
sage: P = Poset({ 1: [2, 3], 2: [4], 3: [4], 4: [] })
sage: Piter = P.rowmotion_orbit_iter([1, 2, 3], stop=False)
sage: Piter.next()
set([1, 2, 3])
sage: Piter.next()
set([1, 2, 3, 4])
sage: Piter.next()
set([])
sage: Piter.next()
set([1])
sage: Piter.next()
set([1, 2, 3])
sage: P = Poset({ 1: [4], 2: [4, 5], 3: [5] })
sage: list(P.rowmotion_orbit_iter([1, 2], element_constructor=list))
[[1, 2], [1, 2, 3, 4], [2, 3, 5], [1], [2, 3], [1, 2, 3, 5], [1, 2, 4], [3]]
Return the rowmotion orbits of order ideals in self.
The rowmotion orbit of an order ideal is its orbit under rowmotion (see rowmotion()).
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))
[[()]]
Iterate over the orbit of an order ideal oideal of self under the operation of toggling the vertices vs[0], vs[1], ... in this order.
See order_ideal_toggle() for a definition of toggling.
Warning
The orbit is that under the composition of toggles,
not under the single toggles themselves. Thus, for
example, if vs == [1,2], then the orbit has the
form
(where
denotes oideal and
means
toggling at
) rather than
.
INPUT:
OUTPUT:
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) )
sage: list(P.toggling_orbit_iter([1, 3, 1], set([1, 2])))
[set([1, 2])]
sage: list(P.toggling_orbit_iter([1, 2, 3], set([1, 2])))
[set([1, 2]), set([]), set([1, 2, 3])]
sage: list(P.toggling_orbit_iter([3, 2, 1], set([1, 2])))
[set([1, 2]), set([1, 2, 3]), set([])]
sage: list(P.toggling_orbit_iter([3, 2, 1], set([1, 2]), element_constructor=list))
[[1, 2], [1, 2, 3], []]
sage: list(P.toggling_orbit_iter([3, 2, 1], set([1, 2]), element_constructor=frozenset))
[frozenset([1, 2]), frozenset([1, 2, 3]), frozenset([])]
sage: list(P.toggling_orbit_iter([3, 2, 1], set([1, 2]), element_constructor=tuple))
[(1, 2), (1, 2, 3), ()]
sage: list(P.toggling_orbit_iter([3, 2, 1], [2, 1], element_constructor=tuple))
[(1, 2), (1, 2, 3), ()]
sage: P = Poset( {} )
sage: list(P.toggling_orbit_iter([], []))
[set([])]
sage: P = Poset({ 1: [2, 3], 2: [4], 3: [4], 4: [] })
sage: Piter = P.toggling_orbit_iter([1, 2, 4, 3], [1, 2, 3], stop=False)
sage: Piter.next()
set([1, 2, 3])
sage: Piter.next()
set([1])
sage: Piter.next()
set([])
sage: Piter.next()
set([1, 2, 3])
sage: Piter.next()
set([1])
Return the orbits of order ideals in self under the operation of toggling the vertices vs[0], vs[1], ... in this order.
See order_ideal_toggle() for a definition of toggling.
Warning
The orbits are those under the composition of toggles,
not under the single toggles themselves. Thus, for
example, if vs == [1,2], then the orbits have the
form
(where
denotes an order ideal and
means
toggling at
) rather than
.
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]