# Cartesian products of Posets¶

AUTHORS:

• Daniel Krenn (2015)
class sage.combinat.posets.cartesian_product.CartesianProductPoset(sets, category, order=None, **kwargs)

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 – a tuple of parents.
• category – a subcategory of Sets().CartesianProducts() & Posets().
• order – a 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

class Element
le(left, right)

Test whether left is less than or equal to right.

INPUT:

• left – an element.
• right – an element.

OUTPUT:

A 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

le_lex(left, right)

Test whether left is lexicographically smaller or equal to right.

INPUT:

• left – an element.
• right – an element.

OUTPUT:

A 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

le_native(left, right)

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:

A 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

le_product(left, right)

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

INPUT:

• left – an element.
• right – an element.

OUTPUT:

A 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