Posets¶

class sage.categories.posets.Posets(s=None)¶

Bases: sage.categories.category.Category

The category of posets i.e. sets with a partial order structure.

EXAMPLES:

sage: Posets()
Category of posets
sage: Posets().super_categories()
[Category of sets]
sage: P = Posets().example(); P
An example of a poset: sets ordered by inclusion

The partial order is implemented by the mandatory method le():

sage: x = P(Set([1,3])); y = P(Set([1,2,3]))
sage: x, y
({1, 3}, {1, 2, 3})
sage: P.le(x, y)
True
sage: P.le(x, x)
True
sage: P.le(y, x)
False

The other comparison methods are called lt(), ge(), gt(), following Python’s naming convention in operator. Default implementations are provided:

sage: P.lt(x, x)
False
sage: P.ge(y, x)
True

Unless the poset is a facade (see Sets.Facade), one can compare directly its elements using the usual Python operators:

sage: D = Poset((divisors(30), attrcall("divides")), facade = False)
sage: D(3) <= D(6)
True
sage: D(3) <= D(3)
True
sage: D(3) <= D(5)
False
sage: D(3) < D(3)
False
sage: D(10) >= D(5)
True

At this point, this has to be implemented by hand. Once trac ticket #10130 will be resolved, this will be automatically provided by this category:

sage: x < y      # todo: not implemented
True
sage: x < x      # todo: not implemented
False
sage: x <= x     # todo: not implemented
True
sage: y >= x     # todo: not implemented
True

class ElementMethods¶: Bases: object

Finite¶: alias of sage.categories.finite_posets.FinitePosets

class ParentMethods¶

Bases: object

CartesianProduct¶: alias of sage.combinat.posets.cartesian_product.CartesianProductPoset

directed_subset(elements, direction)¶

Return the order filter or the order ideal generated by a list of elements.

If direction is ‘up’, the order filter (upper set) is being returned.

If direction is ‘down’, the order ideal (lower set) is being returned.

INPUT:

elements – a list of elements.
direction – ‘up’ or ‘down’.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.directed_subset([3, 8], 'up')
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sage: B.directed_subset([7, 10], 'down')
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

ge(x, y)¶

Return whether \(x \ge y\) in the poset self.

INPUT:

x, y – elements of self.

This default implementation delegates the work to le().

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.ge( 6, 3 )
True
sage: D.ge( 3, 3 )
True
sage: D.ge( 3, 5 )
False

gt(x, y)¶

Return whether \(x > y\) in the poset self.

INPUT:

x, y – elements of self.

This default implementation delegates the work to lt().

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.gt( 3, 6 )
False
sage: D.gt( 3, 3 )
False
sage: D.gt( 3, 5 )
False

is_antichain_of_poset(o)¶

Return whether an iterable o is an antichain of self.

INPUT:

o – an iterable (e. g., list, set, or tuple) containing some elements of self

OUTPUT:

True if the subset of self consisting of the entries of o is an antichain of self, and False otherwise.

EXAMPLES:

sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_antichain_of_poset([1, 3])
False
sage: P.is_antichain_of_poset([3, 1])
False
sage: P.is_antichain_of_poset([1, 1, 3])
False
sage: P.is_antichain_of_poset([])
True
sage: P.is_antichain_of_poset([1])
True
sage: P.is_antichain_of_poset([1, 1])
True
sage: P.is_antichain_of_poset([3, 4])
True
sage: P.is_antichain_of_poset([3, 4, 12])
False
sage: P.is_antichain_of_poset([6, 4])
True
sage: P.is_antichain_of_poset(i for i in divisors(12) if (2 < i and i < 6))
True
sage: P.is_antichain_of_poset(i for i in divisors(12) if (2 <= i and i < 6))
False

sage: Q = Poset({2: [3, 1], 3: [4], 1: [4]})
sage: Q.is_antichain_of_poset((1, 2))
False
sage: Q.is_antichain_of_poset((2, 4))
False
sage: Q.is_antichain_of_poset((4, 2))
False
sage: Q.is_antichain_of_poset((2, 2))
True
sage: Q.is_antichain_of_poset((3, 4))
False
sage: Q.is_antichain_of_poset((3, 1))
True
sage: Q.is_antichain_of_poset((1, ))
True
sage: Q.is_antichain_of_poset(())
True

An infinite poset:

sage: from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
sage: R = FiniteSetsOrderedByInclusion()
sage: R.is_antichain_of_poset([R(set([3, 1, 2])), R(set([1, 4])), R(set([4, 5]))])
True
sage: R.is_antichain_of_poset([R(set([3, 1, 2, 4])), R(set([1, 4])), R(set([4, 5]))])
False

is_chain_of_poset(o, ordered=False)¶

Return whether an iterable o is a chain of self, including a check for o being ordered from smallest to largest element if the keyword ordered is set to True.

INPUT:

o – an iterable (e. g., list, set, or tuple) containing some elements of self
ordered – a Boolean (default: False) which decides whether the notion of a chain includes being ordered

OUTPUT:

If ordered is set to False, the truth value of the following assertion is returned: The subset of self formed by the elements of o is a chain in self.

If ordered is set to True, the truth value of the following assertion is returned: Every element of the list o is (strictly!) smaller than its successor in self. (This makes no sense if ordered is a set.)

EXAMPLES:

sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_chain_of_poset([1, 3])
True
sage: P.is_chain_of_poset([3, 1])
True
sage: P.is_chain_of_poset([1, 3], ordered=True)
True
sage: P.is_chain_of_poset([3, 1], ordered=True)
False
sage: P.is_chain_of_poset([])
True
sage: P.is_chain_of_poset([], ordered=True)
True
sage: P.is_chain_of_poset((2, 12, 6))
True
sage: P.is_chain_of_poset((2, 6, 12), ordered=True)
True
sage: P.is_chain_of_poset((2, 12, 6), ordered=True)
False
sage: P.is_chain_of_poset((2, 12, 6, 3))
False
sage: P.is_chain_of_poset((2, 3))
False

sage: Q = Poset({2: [3, 1], 3: [4], 1: [4]})
sage: Q.is_chain_of_poset([1, 2], ordered=True)
False
sage: Q.is_chain_of_poset([1, 2])
True
sage: Q.is_chain_of_poset([2, 1], ordered=True)
True
sage: Q.is_chain_of_poset([2, 1, 1], ordered=True)
False
sage: Q.is_chain_of_poset([3])
True
sage: Q.is_chain_of_poset([4, 2, 3])
True
sage: Q.is_chain_of_poset([4, 2, 3], ordered=True)
False
sage: Q.is_chain_of_poset([2, 3, 4], ordered=True)
True

Examples with infinite posets:

sage: from sage.categories.examples.posets import FiniteSetsOrderedByInclusion
sage: R = FiniteSetsOrderedByInclusion()
sage: R.is_chain_of_poset([R(set([3, 1, 2])), R(set([1, 4])), R(set([4, 5]))])
False
sage: R.is_chain_of_poset([R(set([3, 1, 2])), R(set([1, 2])), R(set([1]))], ordered=True)
False
sage: R.is_chain_of_poset([R(set([3, 1, 2])), R(set([1, 2])), R(set([1]))])
True

sage: from sage.categories.examples.posets import PositiveIntegersOrderedByDivisibilityFacade
sage: T = PositiveIntegersOrderedByDivisibilityFacade()
sage: T.is_chain_of_poset((T(3), T(4), T(7)))
False
sage: T.is_chain_of_poset((T(3), T(6), T(3)))
True
sage: T.is_chain_of_poset((T(3), T(6), T(3)), ordered=True)
False
sage: T.is_chain_of_poset((T(3), T(3), T(6)))
True
sage: T.is_chain_of_poset((T(3), T(3), T(6)), ordered=True)
False
sage: T.is_chain_of_poset((T(3), T(6)), ordered=True)
True
sage: T.is_chain_of_poset((), ordered=True)
True
sage: T.is_chain_of_poset((T(3),), ordered=True)
True
sage: T.is_chain_of_poset((T(q) for q in divisors(27)))
True
sage: T.is_chain_of_poset((T(q) for q in divisors(18)))
False

is_order_filter(o)¶

Return whether o is an order filter of self, assuming self has no infinite ascending path.

INPUT:

o – a list (or set, or tuple) containing some elements of self

EXAMPLES:

sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_order_filter([4, 12])
True
sage: P.is_order_filter([])
True
sage: P.is_order_filter({3, 4, 12})
False
sage: P.is_order_filter({3, 6, 12})
True

is_order_ideal(o)¶

Return whether o is an order ideal of self, assuming self has no infinite descending path.

INPUT:

o – a list (or set, or tuple) containing some elements of self

EXAMPLES:

sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_order_ideal([1, 3])
True
sage: P.is_order_ideal([])
True
sage: P.is_order_ideal({1, 3})
True
sage: P.is_order_ideal([1, 3, 4])
False

le(x, y)¶

Return whether \(x \le y\) in the poset self.

INPUT:

x, y – elements of self.

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.le( 3, 6 )
True
sage: D.le( 3, 3 )
True
sage: D.le( 3, 5 )
False

lower_covers(x)¶

Return the lower covers of \(x\), that is, the elements \(y\) such that \(y<x\) and there exists no \(z\) such that \(y<z<x\).

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.lower_covers(15)
[3, 5]

lt(x, y)¶

Return whether \(x < y\) in the poset self.

INPUT:

x, y – elements of self.

This default implementation delegates the work to le().

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.lt( 3, 6 )
True
sage: D.lt( 3, 3 )
False
sage: D.lt( 3, 5 )
False

order_filter(elements)¶

Return the order filter generated by a list of elements.

A subset \(I\) of a poset is said to be an order filter if, for any \(x\) in \(I\) and \(y\) such that \(y \ge x\), then \(y\) is in \(I\).

This is also called the upper set generated by these elements.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.order_filter([3,8])
[3, 7, 8, 9, 10, 11, 12, 13, 14, 15]

order_ideal(elements)¶

Return the order ideal in self generated by the elements of an iterable elements.

A subset \(I\) of a poset is said to be an order ideal if, for any \(x\) in \(I\) and \(y\) such that \(y \le x\), then \(y\) is in \(I\).

This is also called the lower set generated by these elements.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.order_ideal([7,10])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

order_ideal_toggle(I, v)¶

Return the result of toggling the element v in the order ideal I.

If \(v\) is an element of a poset \(P\), then toggling the element \(v\) is an automorphism of the set \(J(P)\) of all order ideals of \(P\). It is defined as follows: If \(I\) is an order ideal of \(P\), then the image of \(I\) under toggling the element \(v\) is

the set \(I \cup \{ v \}\), if \(v \not\in I\) but every element of \(P\) smaller than \(v\) is in \(I\);
the set \(I \setminus \{ v \}\), if \(v \in I\) but no element of \(P\) greater than \(v\) is in \(I\);
\(I\) otherwise.

This image always is an order ideal of \(P\).

EXAMPLES:

sage: P = Poset({1: [2,3], 2: [4], 3: []})
sage: I = Set({1, 2})
sage: I in P.order_ideals_lattice()
True
sage: P.order_ideal_toggle(I, 1)
{1, 2}
sage: P.order_ideal_toggle(I, 2)
{1}
sage: P.order_ideal_toggle(I, 3)
{1, 2, 3}
sage: P.order_ideal_toggle(I, 4)
{1, 2, 4}
sage: P4 = Posets(4)
sage: all(all(all(P.order_ideal_toggle(P.order_ideal_toggle(I, i), i) == I
....:               for i in range(4))
....:          for I in P.order_ideals_lattice(facade=True))
....:     for P in P4)
True

order_ideal_toggles(I, vs)¶

Return the result of toggling the elements of the list (or iterable) vs (one by one, from left to right) in the order ideal I.

See order_ideal_toggle() for a definition of toggling.

EXAMPLES:

sage: P = Poset({1: [2,3], 2: [4], 3: []})
sage: I = Set({1, 2})
sage: P.order_ideal_toggles(I, [1,2,3,4])
{1, 3}
sage: P.order_ideal_toggles(I, (1,2,3,4))
{1, 3}

principal_lower_set(x)¶

Return the order ideal generated by an element x.

This is also called the lower set generated by this element.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]

principal_order_filter(x)¶

Return the order filter generated by an element x.

This is also called the upper set generated by this element.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]

principal_order_ideal(x)¶

Return the order ideal generated by an element x.

This is also called the lower set generated by this element.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_ideal(6)
[0, 2, 4, 6]

principal_upper_set(x)¶

Return the order filter generated by an element x.

This is also called the upper set generated by this element.

EXAMPLES:

sage: B = posets.BooleanLattice(4)
sage: B.principal_order_filter(2)
[2, 3, 6, 7, 10, 11, 14, 15]

upper_covers(x)¶

Return the upper covers of \(x\), that is, the elements \(y\) such that \(x<y\) and there exists no \(z\) such that \(x<z<y\).

EXAMPLES:

sage: D = Poset((divisors(30), attrcall("divides")))
sage: D.upper_covers(3)
[6, 15]

example(choice=None)¶

Return examples of objects of Posets(), as per Category.example().

EXAMPLES:

sage: Posets().example()
An example of a poset: sets ordered by inclusion

sage: Posets().example("facade")
An example of a facade poset: the positive integers ordered by divisibility

super_categories()¶

Return a list of the (immediate) super categories of self, as per Category.super_categories().

EXAMPLES:

sage: Posets().super_categories()
[Category of sets]

Posets¶

Previous topic

Next topic

This Page