Cartesian products of Posets

AUTHORS:

  • Daniel Krenn (2015)

class sage.combinat.posets.cartesian_product.CartesianProductPoset(sets, category, order=None, **kwargs)[source]

Bases: CartesianProduct

A class implementing Cartesian products of posets (and elements thereof). Compared to CartesianProduct you are able to specify an order for comparison of the elements.

INPUT:

  • sets – tuple of parents

  • category – a subcategory of Sets().CartesianProducts() & Posets()

  • order – string or function specifying an order less or equal; it can be one of the following:

    • 'native' – elements are ordered by their native ordering, i.e., the order the wrapped elements (tuples) provide

    • 'lex' – elements are ordered lexicographically

    • 'product' – an element is less or equal to another element, if less or equal is true for all its components (Cartesian projections)

    • a function which performs the comparison \(\leq\); it takes two input arguments and outputs a boolean

Other keyword arguments (kwargs) are passed to the constructor of CartesianProduct.

EXAMPLES:

sage: P = Poset((srange(3), lambda left, right: left <= right))
sage: Cl = cartesian_product((P, P), order='lex')
sage: Cl((1, 1)) <= Cl((2, 0))
True
sage: Cp = cartesian_product((P, P), order='product')
sage: Cp((1, 1)) <= Cp((2, 0))
False
sage: def le_sum(left, right):
....:     return (sum(left) < sum(right) or
....:             sum(left) == sum(right) and left[0] <= right[0])
sage: Cs = cartesian_product((P, P), order=le_sum)
sage: Cs((1, 1)) <= Cs((2, 0))
True

>>> from sage.all import *
>>> P = Poset((srange(Integer(3)), lambda left, right: left <= right))
>>> Cl = cartesian_product((P, P), order='lex')
>>> Cl((Integer(1), Integer(1))) <= Cl((Integer(2), Integer(0)))
True
>>> Cp = cartesian_product((P, P), order='product')
>>> Cp((Integer(1), Integer(1))) <= Cp((Integer(2), Integer(0)))
False
>>> def le_sum(left, right):
...     return (sum(left) < sum(right) or
...             sum(left) == sum(right) and left[Integer(0)] <= right[Integer(0)])
>>> Cs = cartesian_product((P, P), order=le_sum)
>>> Cs((Integer(1), Integer(1))) <= Cs((Integer(2), Integer(0)))
True

See also

CartesianProduct

class Element[source]

Bases: Element

le(left, right)[source]

Test whether left is less than or equal to right.

INPUT:

  • left – an element

  • right – an element

OUTPUT: boolean

Note

This method uses the order defined on creation of this Cartesian product. See CartesianProductPoset.

EXAMPLES:

sage: P = posets.ChainPoset(10)
sage: def le_sum(left, right):
....:     return (sum(left) < sum(right) or
....:             sum(left) == sum(right) and left[0] <= right[0])
sage: C = cartesian_product((P, P), order=le_sum)
sage: C.le(C((1, 6)), C((6, 1)))
True
sage: C.le(C((6, 1)), C((1, 6)))
False
sage: C.le(C((1, 6)), C((6, 6)))
True
sage: C.le(C((6, 6)), C((1, 6)))
False

>>> from sage.all import *
>>> P = posets.ChainPoset(Integer(10))
>>> def le_sum(left, right):
...     return (sum(left) < sum(right) or
...             sum(left) == sum(right) and left[Integer(0)] <= right[Integer(0)])
>>> C = cartesian_product((P, P), order=le_sum)
>>> C.le(C((Integer(1), Integer(6))), C((Integer(6), Integer(1))))
True
>>> C.le(C((Integer(6), Integer(1))), C((Integer(1), Integer(6))))
False
>>> C.le(C((Integer(1), Integer(6))), C((Integer(6), Integer(6))))
True
>>> C.le(C((Integer(6), Integer(6))), C((Integer(1), Integer(6))))
False
le_lex(left, right)[source]

Test whether left is lexicographically smaller or equal to right.

INPUT:

  • left – an element

  • right – an element

OUTPUT: boolean

EXAMPLES:

sage: P = Poset((srange(2), lambda left, right: left <= right))
sage: Q = cartesian_product((P, P), order='lex')
sage: T = [Q((0, 0)), Q((1, 1)), Q((0, 1)), Q((1, 0))]
sage: for a in T:
....:     for b in T:
....:         assert Q.le(a, b) == (a <= b)
....:         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = True
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True

>>> from sage.all import *
>>> P = Poset((srange(Integer(2)), lambda left, right: left <= right))
>>> Q = cartesian_product((P, P), order='lex')
>>> T = [Q((Integer(0), Integer(0))), Q((Integer(1), Integer(1))), Q((Integer(0), Integer(1))), Q((Integer(1), Integer(0)))]
>>> for a in T:
...     for b in T:
...         assert Q.le(a, b) == (a <= b)
...         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = True
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True
le_native(left, right)[source]

Test whether left is smaller or equal to right in the order provided by the elements themselves.

INPUT:

  • left – an element

  • right – an element

OUTPUT: boolean

EXAMPLES:

sage: P = Poset((srange(2), lambda left, right: left <= right))
sage: Q = cartesian_product((P, P), order='native')
sage: T = [Q((0, 0)), Q((1, 1)), Q((0, 1)), Q((1, 0))]
sage: for a in T:
....:     for b in T:
....:         assert Q.le(a, b) == (a <= b)
....:         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = True
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True

>>> from sage.all import *
>>> P = Poset((srange(Integer(2)), lambda left, right: left <= right))
>>> Q = cartesian_product((P, P), order='native')
>>> T = [Q((Integer(0), Integer(0))), Q((Integer(1), Integer(1))), Q((Integer(0), Integer(1))), Q((Integer(1), Integer(0)))]
>>> for a in T:
...     for b in T:
...         assert Q.le(a, b) == (a <= b)
...         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = True
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True
le_product(left, right)[source]

Test whether left is component-wise smaller or equal to right.

INPUT:

  • left – an element

  • right – an element

OUTPUT: boolean

The comparison is True if the result of the comparison in each component is True.

EXAMPLES:

sage: P = Poset((srange(2), lambda left, right: left <= right))
sage: Q = cartesian_product((P, P), order='product')
sage: T = [Q((0, 0)), Q((1, 1)), Q((0, 1)), Q((1, 0))]
sage: for a in T:
....:     for b in T:
....:         assert Q.le(a, b) == (a <= b)
....:         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = False
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True

>>> from sage.all import *
>>> P = Poset((srange(Integer(2)), lambda left, right: left <= right))
>>> Q = cartesian_product((P, P), order='product')
>>> T = [Q((Integer(0), Integer(0))), Q((Integer(1), Integer(1))), Q((Integer(0), Integer(1))), Q((Integer(1), Integer(0)))]
>>> for a in T:
...     for b in T:
...         assert Q.le(a, b) == (a <= b)
...         print('%s <= %s = %s' % (a, b, a <= b))
(0, 0) <= (0, 0) = True
(0, 0) <= (1, 1) = True
(0, 0) <= (0, 1) = True
(0, 0) <= (1, 0) = True
(1, 1) <= (0, 0) = False
(1, 1) <= (1, 1) = True
(1, 1) <= (0, 1) = False
(1, 1) <= (1, 0) = False
(0, 1) <= (0, 0) = False
(0, 1) <= (1, 1) = True
(0, 1) <= (0, 1) = True
(0, 1) <= (1, 0) = False
(1, 0) <= (0, 0) = False
(1, 0) <= (1, 1) = True
(1, 0) <= (0, 1) = False
(1, 0) <= (1, 0) = True