Finite posets¶
Here is some terminology used in this file:
- An order filter (or upper set) of a poset
is a subset
of
such that if
and
then
.
- An order ideal (or lower set) of a poset
is a subset
of
such that if
and
then
.
-
class
sage.categories.finite_posets.
FinitePosets
(base_category)¶ Bases:
sage.categories.category_with_axiom.CategoryWithAxiom
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 sets] sage: FinitePosets().example() NotImplemented
TESTS:
sage: C = FinitePosets() sage: C is Posets().Finite() True sage: TestSuite(C).run()
-
class
ParentMethods
¶ -
antichains
()¶ 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]]
-
birational_free_labelling
(linear_extension=None, prefix='x', base_field=None, reduced=False, addvars=None)¶ Return the birational free labelling of
self
.Let us hold back defining this, and introduce birational toggles and birational rowmotion first. These notions have been introduced in [EP13] as generalizations of the notions of toggles (
order_ideal_toggle()
) androwmotion
on order ideals of a finite poset. They have been studied further in [GR13].Let
be a field, and
be a finite poset. Let
denote the poset obtained from
by adding a new element
which is greater than all existing elements of
, and a new element
which is smaller than all existing elements of
and
. Now, a
-labelling of
will mean any function from
to
. The image of an element
of
under this labelling will be called the label of this labelling at
. The set of all
-labellings of
is clearly
.
For any
, we now define a rational map
as follows: For every
, the image
should send every element
distinct from
to
(so the labels at all
don’t change), while
is sent to
(both sums are over all
satisfying the respectively given conditions). Here,
and
mean (respectively) “covered by” and “covers”, interpreted with respect to the poset
. This rational map
is an involution and is called the (birational)
-toggle; see
birational_toggle()
for its implementation.Now, birational rowmotion is defined as the composition
, where
is a linear extension of
(written as a linear ordering of the elements of
). This is a rational map
which does not depend on the choice of the linear extension; it is denoted by
. See
birational_rowmotion()
for its implementation.The definitions of birational toggles and birational rowmotion extend to the case of
being any semifield rather than necessarily a field (although it becomes less clear what constitutes a rational map in this generality). The most useful case is that of the
tropical semiring
, in which case birational rowmotion relates to classical constructions such as promotion of rectangular semistandard Young tableaux (page 5 of [EP13b] and future work, via the related notion of birational promotion) and rowmotion on order ideals of the poset ([EP13]).The birational free labelling is a special labelling defined for every finite poset
and every linear extension
of
. It is given by sending every element
in
to
, sending the element
of
to
, and sending the element
of
to
, where the ground field
is the field of rational functions in
indeterminates
over
.
In Sage, a labelling
of a poset
is encoded as a
-tuple
, where
is the ground field of the labelling (i. e., its target),
is the dictionary containing the values of
at the elements of
(the keys being the respective elements of
),
is the label of
at
, and
is the label of
at
.
Warning
The dictionary
is labelled by the elements of
. If
is a poset with
facade
option set toFalse
, these might not be what they seem to be! (For instance, ifP == Poset({1: [2, 3]}, facade=False)
, then the value ofat
has to be accessed by
d[P(1)]
, not byd[1]
.)Warning
Dictionaries are mutable. They do compare correctly, but are not hashable and need to be cloned to avoid spooky action at a distance. Be careful!
INPUT:
linear_extension
– (default: the default linear extension ofself
) a linear extension ofself
(as a linear extension or as a list), or more generally a list of all elements of all elements ofself
each occurring exactly onceprefix
– (default:'x'
) the prefix to name the indeterminates corresponding to the elements ofself
in the labelling (so, setting it to'frog'
will result in these indeterminates being calledfrog1, frog2, ..., frogn
rather thanx1, x2, ..., xn
).base_field
– (default:QQ
) the base field to be used instead ofto define the rational function field over; this is not going to be the base field of the labelling, because the latter will have indeterminates adjoined!
reduced
– (default:False
) if set toTrue
, the result will be the reduced birational free labelling, which differs from the regular one by havingand
both sent to
instead of
and
(the indeterminates
and
then also won’t appear in the ground field)
addvars
– (default:''
) a string containing names of extra variables to be adjoined to the ground field (these don’t have an effect on the labels)
OUTPUT:
The birational free labelling of the poset
self
and the linear extensionlinear_extension
. Or, ifreduced
is set toTrue
, the reduced birational free labelling.REFERENCES:
[EP13] (1, 2) David Einstein, James Propp. Combinatorial, piecewise-linear, and birational homomesy for products of two chains. Arxiv 1310.5294v1. [EP13b] David Einstein, James Propp. Piecewise-linear and birational toggling. Extended abstract for FPSAC 2014. http://faculty.uml.edu/jpropp/fpsac14.pdf [GR13] (1, 2) Darij Grinberg, Tom Roby. Iterative properties of birational rowmotion I. http://web.mit.edu/~darij/www/algebra/skeletal.pdf EXAMPLES:
We construct the birational free labelling on a simple poset:
sage: P = Poset({1: [2, 3]}) sage: l = P.birational_free_labelling(); l (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(l[1].items()) [(1, x1), (2, x2), (3, x3)] sage: l = P.birational_free_labelling(linear_extension=[1, 3, 2]); l (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(l[1].items()) [(1, x1), (2, x3), (3, x2)] sage: l = P.birational_free_labelling(linear_extension=[1, 3, 2], reduced=True, addvars="spam, eggs"); l (Fraction Field of Multivariate Polynomial Ring in x1, x2, x3, spam, eggs over Rational Field, {...}, 1, 1) sage: sorted(l[1].items()) [(1, x1), (2, x3), (3, x2)] sage: l = P.birational_free_labelling(linear_extension=[1, 3, 2], prefix="wut", reduced=True, addvars="spam, eggs"); l (Fraction Field of Multivariate Polynomial Ring in wut1, wut2, wut3, spam, eggs over Rational Field, {...}, 1, 1) sage: sorted(l[1].items()) [(1, wut1), (2, wut3), (3, wut2)] sage: l = P.birational_free_labelling(linear_extension=[1, 3, 2], reduced=False, addvars="spam, eggs"); l (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b, spam, eggs over Rational Field, {...}, a, b) sage: sorted(l[1].items()) [(1, x1), (2, x3), (3, x2)] sage: l[1][2] x3
Illustrating the warning about facade:
sage: P = Poset({1: [2, 3]}, facade=False) sage: l = P.birational_free_labelling(linear_extension=[1, 3, 2], reduced=False, addvars="spam, eggs"); l (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b, spam, eggs over Rational Field, {...}, a, b) sage: l[1][2] Traceback (most recent call last): ... KeyError: 2 sage: l[1][P(2)] x3
Another poset:
sage: P = Posets.SSTPoset([2,1]) sage: lext = sorted(P) sage: l = P.birational_free_labelling(linear_extension=lext, addvars="ohai") sage: l (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, x5, x6, x7, x8, b, ohai over Rational Field, {...}, a, b) sage: sorted(l[1].items()) [([[1, 1], [2]], x1), ([[1, 1], [3]], x2), ([[1, 2], [2]], x3), ([[1, 2], [3]], x4), ([[1, 3], [2]], x5), ([[1, 3], [3]], x6), ([[2, 2], [3]], x7), ([[2, 3], [3]], x8)]
See
birational_rowmotion()
,birational_toggle()
andbirational_toggles()
for more substantial examples of what one can do with the birational free labelling.TESTS:
The
linear_extension
keyword does not have to be given an actual linear extension:sage: P = Posets.ChainPoset(2).product(Posets.ChainPoset(3)) sage: P Finite lattice containing 6 elements sage: lex = [(1,0),(0,0),(1,1),(0,1),(1,2),(0,2)] sage: l = P.birational_free_labelling(linear_extension=lex, ....: prefix="u", reduced=True) sage: l (Fraction Field of Multivariate Polynomial Ring in u1, u2, u3, u4, u5, u6 over Rational Field, {...}, 1, 1) sage: sorted(l[1].items()) [((0, 0), u2), ((0, 1), u4), ((0, 2), u6), ((1, 0), u1), ((1, 1), u3), ((1, 2), u5)]
For comparison, the standard linear extension:
sage: l = P.birational_free_labelling(prefix="u", reduced=True); l (Fraction Field of Multivariate Polynomial Ring in u1, u2, u3, u4, u5, u6 over Rational Field, {...}, 1, 1) sage: sorted(l[1].items()) [((0, 0), u1), ((0, 1), u2), ((0, 2), u3), ((1, 0), u4), ((1, 1), u5), ((1, 2), u6)]
If you want your linear extension to be tested for being a linear extension, just call the
linear_extension
method on the poset:sage: lex = [(0,0),(0,1),(1,0),(1,1),(0,2),(1,2)] sage: l = P.birational_free_labelling(linear_extension=P.linear_extension(lex), ....: prefix="u", reduced=True) sage: l (Fraction Field of Multivariate Polynomial Ring in u1, u2, u3, u4, u5, u6 over Rational Field, {...}, 1, 1) sage: sorted(l[1].items()) [((0, 0), u1), ((0, 1), u2), ((0, 2), u5), ((1, 0), u3), ((1, 1), u4), ((1, 2), u6)]
Nonstandard base field:
sage: P = Poset({1: [3], 2: [3,4]}) sage: lex = [1, 2, 4, 3] sage: l = P.birational_free_labelling(linear_extension=lex, ....: prefix="aaa", ....: base_field=Zmod(13)) sage: l (Fraction Field of Multivariate Polynomial Ring in a, aaa1, aaa2, aaa3, aaa4, b over Ring of integers modulo 13, {...}, a, b) sage: l[1][4] aaa3
The empty poset:
sage: P = Poset({}) sage: P.birational_free_labelling(reduced=False, addvars="spam, eggs") (Fraction Field of Multivariate Polynomial Ring in a, b, spam, eggs over Rational Field, {}, a, b) sage: P.birational_free_labelling(reduced=True, addvars="spam, eggs") (Fraction Field of Multivariate Polynomial Ring in spam, eggs over Rational Field, {}, 1, 1) sage: P.birational_free_labelling(reduced=True) (Multivariate Polynomial Ring in no variables over Rational Field, {}, 1, 1) sage: P.birational_free_labelling(prefix="zzz") (Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field, {}, a, b)
-
birational_rowmotion
(labelling)¶ Return the result of applying birational rowmotion to the
-labelling
labelling
of the posetself
.See the documentation of
birational_free_labelling()
for a definition of birational rowmotion and-labellings and for an explanation of how
-labellings are to be encoded to be understood by Sage. This implementation allows
to be a semifield, not just a field. Birational rowmotion is only a rational map, so an exception (most likely,
ZeroDivisionError
) will be thrown if the denominator is zero.INPUT:
labelling
– a-labelling of
self
in the sense as defined in the documentation ofbirational_free_labelling()
OUTPUT:
The image of the
-labelling
under birational rowmotion.
EXAMPLES:
sage: P = Poset({1: [2, 3], 2: [4], 3: [4]}) sage: lex = [1, 2, 3, 4] sage: t = P.birational_free_labelling(linear_extension=lex); t (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, b over Rational Field, {...}, a, b) sage: sorted(t[1].items()) [(1, x1), (2, x2), (3, x3), (4, x4)] sage: t = P.birational_rowmotion(t); t (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, b over Rational Field, {...}, a, b) sage: sorted(t[1].items()) [(1, a*b/x4), (2, (x1*x2*b + x1*x3*b)/(x2*x4)), (3, (x1*x2*b + x1*x3*b)/(x3*x4)), (4, (x2*b + x3*b)/x4)]
A result of [GR13] states that applying birational rowmotion
times to a
-labelling
of the poset
gives back
. Let us check this:
sage: def test_rectangle_periodicity(n, m, k): ....: P = Posets.ChainPoset(n).product(Posets.ChainPoset(m)) ....: t0 = P.birational_free_labelling(P) ....: t = t0 ....: for i in range(k): ....: t = P.birational_rowmotion(t) ....: return t == t0 sage: test_rectangle_periodicity(2, 2, 4) True sage: test_rectangle_periodicity(2, 2, 2) False sage: test_rectangle_periodicity(2, 3, 5) # long time True
While computations with the birational free labelling quickly run out of memory due to the complexity of the rational functions involved, it is computationally cheap to check properties of birational rowmotion on examples in the tropical semiring:
sage: def test_rectangle_periodicity_tropical(n, m, k): ....: P = Posets.ChainPoset(n).product(Posets.ChainPoset(m)) ....: TT = TropicalSemiring(ZZ) ....: t0 = (TT, {v: TT(floor(random()*100)) for v in P}, TT(0), TT(124)) ....: t = t0 ....: for i in range(k): ....: t = P.birational_rowmotion(t) ....: return t == t0 sage: test_rectangle_periodicity_tropical(7, 6, 13) True
Tropicalization is also what relates birational rowmotion to classical rowmotion on order ideals. In fact, if
denotes the
tropical semiring
ofand
is a finite poset, then we can define an embedding
from the set
of all order ideals of
into the set
of all
-labellings of
by sending every
to the indicator function of
extended by the value
at the element
and the value
at the element
. This map
has the property that
, where
denotes birational rowmotion, and
denotes
classical rowmotion
on. An example:
sage: P = Posets.IntegerPartitions(5) sage: TT = TropicalSemiring(ZZ) sage: def indicator_labelling(I): ....: # send order ideal `I` to a `T`-labelling of `P`. ....: dct = {v: TT(v in I) for v in P} ....: return (TT, dct, TT(1), TT(0)) sage: all(indicator_labelling(P.rowmotion(I)) ....: == P.birational_rowmotion(indicator_labelling(I)) ....: for I in P.order_ideals_lattice(facade=True)) True
TESTS:
Facade set to false works:
sage: P = Poset({1: [2, 3], 2: [4], 3: [4]}, facade=False) sage: lex = [1, 2, 3, 4] sage: t = P.birational_free_labelling(linear_extension=lex); t (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, b over Rational Field, {...}, a, b) sage: t = P.birational_rowmotion(t); t (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, b over Rational Field, {...}, a, b) sage: t[1][P(2)] (x1*x2*b + x1*x3*b)/(x2*x4) sage: t = P.birational_rowmotion(t) sage: t[1][P(2)] a*b/x3
-
birational_toggle
(v, labelling)¶ Return the result of applying the birational
-toggle
to the
-labelling
labelling
of the posetself
.See the documentation of
birational_free_labelling()
for a definition of this toggle and of-labellings as well as an explanation of how
-labellings are to be encoded to be understood by Sage. This implementation allows
to be a semifield, not just a field. The birational
-toggle is only a rational map, so an exception (most likely,
ZeroDivisionError
) will be thrown if the denominator is zero.INPUT:
v
– an element ofself
(must haveself
as parent ifself
is afacade=False
poset)labelling
– a-labelling of
self
in the sense as defined in the documentation ofbirational_free_labelling()
OUTPUT:
The
-labelling
of
self
, whereis
labelling
.EXAMPLES:
Let us start with the birational free labelling of the “V”-poset (the three-element poset with Hasse diagram looking like a “V”):
sage: V = Poset({1: [2, 3]}) sage: s = V.birational_free_labelling(); s (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(s[1].items()) [(1, x1), (2, x2), (3, x3)]
The image of
under the
-toggle
is:
sage: s1 = V.birational_toggle(1, s); s1 (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(s1[1].items()) [(1, a*x2*x3/(x1*x2 + x1*x3)), (2, x2), (3, x3)]
Now let us apply the
-toggle
(to the old
s
):sage: s2 = V.birational_toggle(2, s); s2 (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(s2[1].items()) [(1, x1), (2, x1*b/x2), (3, x3)]
On the other hand, we can also apply
to the image of
under
:
sage: s12 = V.birational_toggle(2, s1); s12 (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, b over Rational Field, {...}, a, b) sage: sorted(s12[1].items()) [(1, a*x2*x3/(x1*x2 + x1*x3)), (2, a*x3*b/(x1*x2 + x1*x3)), (3, x3)]
Each toggle is an involution:
sage: all( V.birational_toggle(i, V.birational_toggle(i, s)) == s ....: for i in V ) True
We can also start with a less generic labelling:
sage: t = (QQ, {1: 3, 2: 6, 3: 7}, 2, 10) sage: t1 = V.birational_toggle(1, t); t1 (Rational Field, {...}, 2, 10) sage: sorted(t1[1].items()) [(1, 28/13), (2, 6), (3, 7)] sage: t13 = V.birational_toggle(3, t1); t13 (Rational Field, {...}, 2, 10) sage: sorted(t13[1].items()) [(1, 28/13), (2, 6), (3, 40/13)]
However, labellings have to be sufficiently generic, lest denominators vanish:
sage: t = (QQ, {1: 3, 2: 5, 3: -5}, 1, 15) sage: t1 = V.birational_toggle(1, t) Traceback (most recent call last): ... ZeroDivisionError: Rational division by zero
We don’t get into zero-division issues in the tropical semiring (unless the zero of the tropical semiring appears in the labelling):
sage: TT = TropicalSemiring(QQ) sage: t = (TT, {1: TT(2), 2: TT(4), 3: TT(1)}, TT(6), TT(0)) sage: t1 = V.birational_toggle(1, t); t1 (Tropical semiring over Rational Field, {...}, 6, 0) sage: sorted(t1[1].items()) [(1, 8), (2, 4), (3, 1)] sage: t12 = V.birational_toggle(2, t1); t12 (Tropical semiring over Rational Field, {...}, 6, 0) sage: sorted(t12[1].items()) [(1, 8), (2, 4), (3, 1)] sage: t123 = V.birational_toggle(3, t12); t123 (Tropical semiring over Rational Field, {...}, 6, 0) sage: sorted(t123[1].items()) [(1, 8), (2, 4), (3, 7)]
We turn to more interesting posets. Here is the
-element poset arising from the weak order on
:
sage: P = Posets.SymmetricGroupWeakOrderPoset(3) sage: sorted(list(P)) ['123', '132', '213', '231', '312', '321'] sage: t = (TT, {'123': TT(4), '132': TT(2), '213': TT(3), '231': TT(1), '321': TT(1), '312': TT(2)}, TT(7), TT(1)) sage: t1 = P.birational_toggle('123', t); t1 (Tropical semiring over Rational Field, {...}, 7, 1) sage: sorted(t1[1].items()) [('123', 6), ('132', 2), ('213', 3), ('231', 1), ('312', 2), ('321', 1)] sage: t13 = P.birational_toggle('213', t1); t13 (Tropical semiring over Rational Field, {...}, 7, 1) sage: sorted(t13[1].items()) [('123', 6), ('132', 2), ('213', 4), ('231', 1), ('312', 2), ('321', 1)]
Let us verify on this example some basic properties of toggles. First of all, again let us check that
is an involution for every
:
sage: all( P.birational_toggle(v, P.birational_toggle(v, t)) == t ....: for v in P ) True
Furthermore, two toggles
and
commute unless one of
or
covers the other:
sage: all( P.covers(v, w) or P.covers(w, v) ....: or P.birational_toggle(v, P.birational_toggle(w, t)) ....: == P.birational_toggle(w, P.birational_toggle(v, t)) ....: for v in P for w in P ) True
TESTS:
Setting
facade
toFalse
does not breakbirational_toggle
:sage: P = Poset({'x': ['y', 'w'], 'y': ['z'], 'w': ['z']}, facade=False) sage: lex = ['x', 'y', 'w', 'z'] sage: t = P.birational_free_labelling(linear_extension=lex) sage: all( P.birational_toggle(v, P.birational_toggle(v, t)) == t ....: for v in P ) True sage: t4 = P.birational_toggle(P('z'), t); t4 (Fraction Field of Multivariate Polynomial Ring in a, x1, x2, x3, x4, b over Rational Field, {...}, a, b) sage: t4[1][P('x')] x1 sage: t4[1][P('y')] x2 sage: t4[1][P('w')] x3 sage: t4[1][P('z')] (x2*b + x3*b)/x4
The one-element poset:
sage: P = Poset({8: []}) sage: t = P.birational_free_labelling() sage: t8 = P.birational_toggle(8, t); t8 (Fraction Field of Multivariate Polynomial Ring in a, x1, b over Rational Field, {...}, a, b) sage: t8[1][8] a*b/x1
-
birational_toggles
(vs, labelling)¶ Return the result of applying a sequence of birational toggles (specified by
vs
) to the-labelling
labelling
of the posetself
.See the documentation of
birational_free_labelling()
for a definition of birational toggles and-labellings and for an explanation of how
-labellings are to be encoded to be understood by Sage. This implementation allows
to be a semifield, not just a field. The birational
-toggle is only a rational map, so an exception (most likely,
ZeroDivisionError
) will be thrown if the denominator is zero.INPUT:
vs
– an iterable comprising elements ofself
(which must haveself
as parent ifself
is afacade=False
poset)labelling
– a-labelling of
self
in the sense as defined in the documentation ofbirational_free_labelling()
OUTPUT:
The
-labelling
of
self
, whereis
labelling
andis
vs
(written as list).EXAMPLES:
sage: P = Posets.SymmetricGroupBruhatOrderPoset(3) sage: sorted(list(P)) ['123', '132', '213', '231', '312', '321'] sage: TT = TropicalSemiring(ZZ) sage: t = (TT, {'123': TT(4), '132': TT(2), '213': TT(3), '231': TT(1), '321': TT(1), '312': TT(2)}, TT(7), TT(1)) sage: tA = P.birational_toggles(['123', '231', '312'], t); tA (Tropical semiring over Integer Ring, {...}, 7, 1) sage: sorted(tA[1].items()) [('123', 6), ('132', 2), ('213', 3), ('231', 2), ('312', 1), ('321', 1)] sage: tAB = P.birational_toggles(['132', '213', '321'], tA); tAB (Tropical semiring over Integer Ring, {...}, 7, 1) sage: sorted(tAB[1].items()) [('123', 6), ('132', 6), ('213', 5), ('231', 2), ('312', 1), ('321', 1)] sage: P = Poset({1: [2, 3], 2: [4], 3: [4]}) sage: Qx = PolynomialRing(QQ, 'x').fraction_field() sage: x = Qx.gen() sage: t = (Qx, {1: 1, 2: x, 3: (x+1)/x, 4: x^2}, 1, 1) sage: t1 = P.birational_toggles((i for i in range(1, 5)), t); t1 (Fraction Field of Univariate Polynomial Ring in x over Rational Field, {...}, 1, 1) sage: sorted(t1[1].items()) [(1, (x^2 + x)/(x^2 + x + 1)), (2, (x^3 + x^2)/(x^2 + x + 1)), (3, x^4/(x^2 + x + 1)), (4, 1)] sage: t2 = P.birational_toggles(reversed(range(1, 5)), t) sage: sorted(t2[1].items()) [(1, 1/x^2), (2, (x^2 + x + 1)/x^4), (3, (x^2 + x + 1)/(x^3 + x^2)), (4, (x^2 + x + 1)/x^3)]
Facade set to
False
works:sage: P = Poset({'x': ['y', 'w'], 'y': ['z'], 'w': ['z']}, facade=False) sage: lex = ['x', 'y', 'w', 'z'] sage: t = P.birational_free_labelling(linear_extension=lex) sage: sorted(P.birational_toggles([P('x'), P('y')], t)[1].items()) [(x, a*x2*x3/(x1*x2 + x1*x3)), (y, a*x3*x4/(x1*x2 + x1*x3)), (w, x3), (z, x4)]
-
directed_subsets
(direction)¶ 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:
direction
– ‘up’ or ‘down’
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')) [[]]
-
is_lattice
()¶ 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
-
is_poset_isomorphism
(f, codomain)¶ Return whether
is an isomorphism of posets from
self
tocodomain
.INPUT:
f
– a function fromself
tocodomain
codomain
– a poset
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
andB
are not facade posets,f
is responsible for the conversions between integers and subsets to elements ofD
andB
and back.
-
is_poset_morphism
(f, codomain)¶ Return whether
is a morphism of posets from
self
tocodomain
, that isfor all
and
in
self
.INPUT:
f
– a function fromself
tocodomain
codomain
– a poset
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
andB
are not facade posets,f
is responsible for the conversions between integers and subsets to elements ofD
andB
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
-
is_selfdual
()¶ 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
-
order_filter_generators
(filter)¶ Generators for an order filter
INPUT:
filter
– an order filter ofself
, as a list (or iterable)
EXAMPLES:
sage: P = Poset((Subsets([1,2,3]), attrcall("issubset"))) sage: I = P.order_filter([Set([1,2]), Set([2,3]), Set([1])]); I [{2, 3}, {1}, {1, 2}, {1, 3}, {1, 2, 3}] sage: P.order_filter_generators(I) {{2, 3}, {1}}
See also
-
order_ideal_complement_generators
(antichain, direction='up')¶ 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 antichainis 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:
antichain
– an antichain ofself
, as a list (or iterable), or, more generally, generators of an order ideal (resp. order filter)direction
– ‘up’ or ‘down’ (default: ‘up’)
OUTPUT:
- the generating antichain of the complement order filter
(resp. order ideal) of the order ideal (resp. order filter)
generated by the antichain
antichain
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: P.order_ideal_complement_generators([1]) {2} sage: P.order_ideal_complement_generators([3]) set() sage: P.order_ideal_complement_generators([1,2]) {3} sage: P.order_ideal_complement_generators([1,2,3]) set() sage: P.order_ideal_complement_generators([1], direction="down") {2} sage: P.order_ideal_complement_generators([3], direction="down") {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
-
order_ideal_generators
(ideal, direction='down')¶ Return the antichain of (minimal) generators of the order ideal (resp. order filter)
ideal
.INPUT:
ideal
– an order ideal(resp. order filter) of
self
, as a list (or iterable); this should be an order ideal ifdirection
is set to'down'
, and an order filter ifdirection
is set to'up'
.direction
–'up'
or'down'
(default:'down'
).
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 [{}, {3}, {2}, {2, 3}, {1}, {1, 2}]
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 [{2, 3}, {1}, {1, 2}, {1, 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
.
-
order_ideals_lattice
(as_ideals=True, facade=False)¶ 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 toFalse
, one can make this method apply this bijection before returning the lattice.INPUT:
as_ideals
– Boolean, ifTrue
(default) returns a poset on the set of order ideals, otherwise on the set of antichains
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, 2, 3}, {0, 1}, {0, 1, 2}, {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.
-
panyushev_complement
(antichain, direction='up')¶ 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 antichainis 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:
antichain
– an antichain ofself
, as a list (or iterable), or, more generally, generators of an order ideal (resp. order filter)direction
– ‘up’ or ‘down’ (default: ‘up’)
OUTPUT:
- the generating antichain of the complement order filter
(resp. order ideal) of the order ideal (resp. order filter)
generated by the antichain
antichain
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: P.order_ideal_complement_generators([1]) {2} sage: P.order_ideal_complement_generators([3]) set() sage: P.order_ideal_complement_generators([1,2]) {3} sage: P.order_ideal_complement_generators([1,2,3]) set() sage: P.order_ideal_complement_generators([1], direction="down") {2} sage: P.order_ideal_complement_generators([3], direction="down") {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
-
panyushev_orbit_iter
(antichain, element_constructor=<type 'set'>, stop=True, check=True)¶ Iterate over the Panyushev orbit of an antichain
antichain
ofself
.The Panyushev orbit of an antichain is its orbit under Panyushev complementation (see
panyushev_complement()
).INPUT:
antichain
– an antichain ofself
, given as an iterable.element_constructor
(defaults toset
) – a type constructor (set
,tuple
,list
,frozenset
,iter
, etc.) which is to be applied to the antichains before they are yielded.stop
– a Boolean (default:True
) determining whether the iterator should stop once it completes its cycle (this happens when it is set toTrue
) or go on forever (this happens when it is set toFalse
).check
– a Boolean (default:True
) determining whetherantichain
should be checked for being an antichain.
OUTPUT:
- an iterator over the orbit of the antichain
antichain
under Panyushev complementation. This iteratorhas the property that
I[0] == antichain
and eachsatisfies
self.order_ideal_complement_generators(I[i]) == I[i+1]
, whereI[i+1]
has to be understood asI[0]
if it is undefined. The entriesI[i]
are sets by default, but depending on the optional keyword variableelement_constructors
they can also be tuples, lists etc.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: list(P.panyushev_orbit_iter(set([1, 2]))) [{1, 2}, {3}, set()] sage: list(P.panyushev_orbit_iter([1, 2])) [{1, 2}, {3}, set()] sage: list(P.panyushev_orbit_iter([2, 1])) [{1, 2}, {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: next(Piter) {2} sage: next(Piter) {3} sage: next(Piter) {2} sage: next(Piter) {3}
-
panyushev_orbits
(element_constructor=<type 'set'>)¶ Return the Panyushev orbits of antichains in
self
.The Panyushev orbit of an antichain is its orbit under Panyushev complementation (see
panyushev_complement()
).INPUT:
element_constructor
(defaults toset
) – a type constructor (set
,tuple
,list
,frozenset
,iter
, etc.) which is to be applied to the antichains before they are returned.
OUTPUT:
- the partition of the set of all antichains of
self
into orbits under Panyushev complementation. This is returned as a list of listsL
such that for eachL
andi
, cyclically:self.order_ideal_complement_generators(L[i]) == L[i+1]
. The entriesL[i]
are sets by default, but depending on the optional keyword variableelement_constructors
they can also be tuples, lists etc.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: P.panyushev_orbits() [[{2}, {1}], [set(), {1, 2}, {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()]]
-
rowmotion
(order_ideal)¶ The image of the order ideal
order_ideal
under rowmotion inself
.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:
order_ideal
– an order ideal ofself
, as a set
OUTPUT:
- the image of
order_ideal
under rowmotion, as a set again
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 {}
-
rowmotion_orbit_iter
(oideal, element_constructor=<type 'set'>, stop=True, check=True)¶ Iterate over the rowmotion orbit of an order ideal
oideal
ofself
.The rowmotion orbit of an order ideal is its orbit under rowmotion (see
rowmotion()
).INPUT:
oideal
– an order ideal ofself
, given as an iterable.element_constructor
(defaults toset
) – a type constructor (set
,tuple
,list
,frozenset
,iter
, etc.) which is to be applied to the order ideals before they are yielded.stop
– a Boolean (default:True
) determining whether the iterator should stop once it completes its cycle (this happens when it is set toTrue
) or go on forever (this happens when it is set toFalse
).check
– a Boolean (default:True
) determining whetheroideal
should be checked for being an order ideal.
OUTPUT:
- an iterator over the orbit of the order ideal
oideal
under rowmotion. This iteratorhas the property that
I[0] == oideal
and that everysatisfies
self.rowmotion(I[i]) == I[i+1]
, whereI[i+1]
has to be understood asI[0]
if it is undefined. The entriesI[i]
are sets by default, but depending on the optional keyword variableelement_constructors
they can also be tuples, lists etc.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: list(P.rowmotion_orbit_iter(set([1, 2]))) [{1, 2}, {1, 2, 3}, set()] sage: list(P.rowmotion_orbit_iter([1, 2])) [{1, 2}, {1, 2, 3}, set()] sage: list(P.rowmotion_orbit_iter([2, 1])) [{1, 2}, {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: next(Piter) {1, 2, 3} sage: next(Piter) {1, 2, 3, 4} sage: next(Piter) set() sage: next(Piter) {1} sage: next(Piter) {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]]
-
rowmotion_orbits
(element_constructor=<type 'set'>)¶ Return the rowmotion orbits of order ideals in
self
.The rowmotion orbit of an order ideal is its orbit under rowmotion (see
rowmotion()
).INPUT:
element_constructor
(defaults toset
) – a type constructor (set
,tuple
,list
,frozenset
,iter
, etc.) which is to be applied to the antichains before they are returned.
OUTPUT:
- the partition of the set of all order ideals of
self
into orbits under rowmotion. This is returned as a list of listsL
such that for eachL
andi
, cyclically:self.rowmotion(L[i]) == L[i+1]
. The entriesL[i]
are sets by default, but depending on the optional keyword variableelement_constructors
they can also be tuples, lists etc.
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)) [[()]]
-
toggling_orbit_iter
(vs, oideal, element_constructor=<type 'set'>, stop=True, check=True)¶ Iterate over the orbit of an order ideal
oideal
ofself
under the operation of toggling the verticesvs[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
andmeans toggling at
) rather than
.
INPUT:
vs
: a list (or other iterable) of elements ofself
(but since the output depends on the order, sets should not be used asvs
).oideal
– an order ideal ofself
, given as an iterable.element_constructor
(defaults toset
) – a type constructor (set
,tuple
,list
,frozenset
,iter
, etc.) which is to be applied to the order ideals before they are yielded.stop
– a Boolean (default:True
) determining whether the iterator should stop once it completes its cycle (this happens when it is set toTrue
) or go on forever (this happens when it is set toFalse
).check
– a Boolean (default:True
) determining whetheroideal
should be checked for being an order ideal.
OUTPUT:
- an iterator over the orbit of the order ideal
oideal
under toggling the vertices in the listvs
in this order. This iteratorhas the property that
I[0] == oideal
and that everysatisfies
self.order_ideal_toggles(I[i], vs) == I[i+1]
, whereI[i+1]
has to be understood asI[0]
if it is undefined. The entriesI[i]
are sets by default, but depending on the optional keyword variableelement_constructors
they can also be tuples, lists etc.
EXAMPLES:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: list(P.toggling_orbit_iter([1, 3, 1], set([1, 2]))) [{1, 2}] sage: list(P.toggling_orbit_iter([1, 2, 3], set([1, 2]))) [{1, 2}, set(), {1, 2, 3}] sage: list(P.toggling_orbit_iter([3, 2, 1], set([1, 2]))) [{1, 2}, {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: next(Piter) {1, 2, 3} sage: next(Piter) {1} sage: next(Piter) set() sage: next(Piter) {1, 2, 3} sage: next(Piter) {1}
-
toggling_orbits
(vs, element_constructor=<type 'set'>)¶ Return the orbits of order ideals in
self
under the operation of toggling the verticesvs[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:
vs
: a list (or other iterable) of elements ofself
(but since the output depends on the order, sets should not be used asvs
).
OUTPUT:
- a partition of the order ideals of
self
, as a list of setsL
such that for eachL
andi
, cyclically:self.order_ideal_toggles(L[i], vs) == L[i+1]
.
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]
-
-
class