Cartesian products of Posets

AUTHORS:

  • Daniel Krenn (2015)

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

Bases: sage.sets.cartesian_product.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 – 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 ≤. 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

See also

CartesianProduct

class Element

Bases: sage.sets.cartesian_product.CartesianProduct.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