Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- r""" Finite posets
This module implements finite partially ordered sets. It defines:
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:class:`FinitePoset` | A class for finite posets :class:`FinitePosets_n` | A class for finite posets up to isomorphism (i.e. unlabeled posets) :meth:`Poset` | Construct a finite poset from various forms of input data. :meth:`is_poset` | Return ``True`` if a directed graph is acyclic and transitively reduced.
List of Poset methods ---------------------
**Comparing, intervals and relations**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.is_less_than` | Return ``True`` if `x` is strictly less than `y` in the poset. :meth:`~FinitePoset.is_greater_than` | Return ``True`` if `x` is strictly greater than `y` in the poset. :meth:`~FinitePoset.is_lequal` | Return ``True`` if `x` is less than or equal to `y` in the poset. :meth:`~FinitePoset.is_gequal` | Return ``True`` if `x` is greater than or equal to `y` in the poset. :meth:`~FinitePoset.compare_elements` | Compare two element of the poset. :meth:`~FinitePoset.closed_interval` | Return the list of elements in a closed interval of the poset. :meth:`~FinitePoset.open_interval` | Return the list of elements in an open interval of the poset. :meth:`~FinitePoset.relations` | Return the list of relations in the poset. :meth:`~FinitePoset.relations_iterator` | Return an iterator over relations in the poset. :meth:`~FinitePoset.order_filter` | Return the upper set generated by elements. :meth:`~FinitePoset.order_ideal` | Return the lower set generated by elements.
**Covering**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.covers` | Return ``True`` if ``y`` covers ``x``. :meth:`~FinitePoset.lower_covers` | Return elements covered by given element. :meth:`~FinitePoset.upper_covers` | Return elements covering given element. :meth:`~FinitePoset.cover_relations` | Return the list of cover relations. :meth:`~FinitePoset.lower_covers_iterator` | Return an iterator over elements covered by given element. :meth:`~FinitePoset.upper_covers_iterator` | Return an iterator over elements covering given element. :meth:`~FinitePoset.cover_relations_iterator` | Return an iterator over cover relations of the poset.
**Properties of the poset**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.cardinality` | Return the number of elements in the poset. :meth:`~FinitePoset.height` | Return the number of elements in a longest chain of the poset. :meth:`~FinitePoset.width` | Return the number of elements in a longest antichain of the poset. :meth:`~FinitePoset.relations_number` | Return the number of relations in the poset. :meth:`~FinitePoset.dimension` | Return the dimension of the poset. :meth:`~FinitePoset.jump_number` | Return the jump number of the poset. :meth:`~FinitePoset.has_bottom` | Return ``True`` if the poset has a unique minimal element. :meth:`~FinitePoset.has_top` | Return ``True`` if the poset has a unique maximal element. :meth:`~FinitePoset.is_bounded` | Return ``True`` if the poset has both unique minimal and unique maximal element. :meth:`~FinitePoset.is_chain` | Return ``True`` if the poset is totally ordered. :meth:`~FinitePoset.is_connected` | Return ``True`` if the poset is connected. :meth:`~FinitePoset.is_graded` | Return ``True`` if all maximal chains of the poset has same length. :meth:`~FinitePoset.is_ranked` | Return ``True`` if the poset has a rank function. :meth:`~FinitePoset.is_rank_symmetric` | Return ``True`` if the poset is rank symmetric. :meth:`~FinitePoset.is_series_parallel` | Return ``True`` if the poset can be built by ordinal sums and disjoint unions. :meth:`~FinitePoset.is_greedy` | Return ``True`` if all greedy linear extensions have equal number of jumps. :meth:`~FinitePoset.is_eulerian` | Return ``True`` if the poset is Eulerian. :meth:`~FinitePoset.is_incomparable_chain_free` | Return ``True`` if the poset is (m+n)-free. :meth:`~FinitePoset.is_slender` | Return ``True`` if the poset is slender. :meth:`~FinitePoset.is_join_semilattice` | Return ``True`` is the poset has a join operation. :meth:`~FinitePoset.is_meet_semilattice` | Return ``True`` if the poset has a meet operation.
**Minimal and maximal elements**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.bottom` | Return the bottom element of the poset, if it exists. :meth:`~FinitePoset.top` | Return the top element of the poset, if it exists. :meth:`~FinitePoset.maximal_elements` | Return the list of the maximal elements of the poset. :meth:`~FinitePoset.minimal_elements` | Return the list of the minimal elements of the poset.
**New posets from old ones**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.disjoint_union` | Return the disjoint union of the poset with other poset. :meth:`~FinitePoset.ordinal_sum` | Return the ordinal sum of the poset with other poset. :meth:`~FinitePoset.product` | Return the Cartesian product of the poset with other poset. :meth:`~FinitePoset.ordinal_product` | Return the ordinal product of the poset with other poset. :meth:`~FinitePoset.star_product` | Return the star product of the poset with other poset. :meth:`~FinitePoset.with_bounds` | Return the poset with bottom and top element adjoined. :meth:`~FinitePoset.without_bounds` | Return the poset with bottom and top element removed. :meth:`~FinitePoset.dual` | Return the dual of the poset. :meth:`~FinitePoset.completion_by_cuts` | Return the Dedekind-MacNeille completion of the poset. :meth:`~FinitePoset.intervals_poset` | Return the poset of intervals of the poset. :meth:`~FinitePoset.connected_components` | Return the connected components of the poset as subposets. :meth:`~FinitePoset.ordinal_summands` | Return the ordinal summands of the poset. :meth:`~FinitePoset.subposet` | Return the subposet containing elements with partial order induced by this poset. :meth:`~FinitePoset.random_subposet` | Return a random subposet that contains each element with given probability. :meth:`~FinitePoset.relabel` | Return a copy of this poset with its elements relabelled. :meth:`~FinitePoset.canonical_label` | Return copy of the poset canonically (re)labelled to integers.
**Chains & antichains**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.is_chain_of_poset` | Return ``True`` if elements in the given list are comparable. :meth:`~FinitePoset.is_antichain_of_poset` | Return ``True`` if elements in the given list are incomparable. :meth:`~FinitePoset.chains` | Return the chains of the poset. :meth:`~FinitePoset.antichains` | Return the antichains of the poset. :meth:`~FinitePoset.maximal_chains` | Return the maximal chains of the poset. :meth:`~FinitePoset.maximal_antichains` | Return the maximal antichains of the poset. :meth:`~FinitePoset.antichains_iterator` | Return an iterator over the antichains of the poset.
**Drawing**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.show` | Display the Hasse diagram of the poset. :meth:`~FinitePoset.plot` | Return a Graphic object corresponding the Hasse diagram of the poset. :meth:`~FinitePoset.graphviz_string` | Return a representation in the DOT language, ready to render in graphviz.
**Comparing posets**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.is_isomorphic` | Return ``True`` if both posets are isomorphic. :meth:`~FinitePoset.is_induced_subposet` | Return ``True`` if given poset is an induced subposet of this poset.
**Polynomials**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.chain_polynomial` | Return the chain polynomial of the poset. :meth:`~FinitePoset.characteristic_polynomial` | Return the characteristic polynomial of the poset. :meth:`~FinitePoset.f_polynomial` | Return the f-polynomial of the poset. :meth:`~FinitePoset.flag_f_polynomial` | Return the flag f-polynomial of the poset. :meth:`~FinitePoset.h_polynomial` | Return the h-polynomial of the poset. :meth:`~FinitePoset.flag_h_polynomial` | Return the flag h-polynomial of the poset. :meth:`~FinitePoset.order_polynomial` | Return the order polynomial of the poset. :meth:`~FinitePoset.zeta_polynomial` | Return the zeta polynomial of the poset. :meth:`~FinitePoset.kazhdan_lusztig_polynomial` | Return the Kazhdan-Lusztig polynomial of the poset. :meth:`~FinitePoset.coxeter_polynomial` | Return the characteristic polynomial of the Coxeter transformation. :meth:`~FinitePoset.degree_polynomial` | Return the generating polynomial of degrees of vertices in the Hasse diagram.
**Polytopes**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.chain_polytope` | Return the chain polytope of the poset. :meth:`~FinitePoset.order_polytope` | Return the order polytope of the poset.
**Graphs**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.hasse_diagram` | Return the Hasse diagram of the poset as a directed graph. :meth:`~FinitePoset.cover_relations_graph` | Return the (undirected) graph of cover relations. :meth:`~FinitePoset.comparability_graph` | Return the comparability graph of the poset. :meth:`~FinitePoset.incomparability_graph` | Return the incomparability graph of the poset. :meth:`~FinitePoset.frank_network` | Return Frank's network of the poset. :meth:`~FinitePoset.linear_extensions_graph` | Return the linear extensions graph of the poset.
**Linear extensions**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.is_linear_extension` | Return ``True`` if the given list is a linear extension of the poset. :meth:`~FinitePoset.linear_extension` | Return a linear extension of the poset. :meth:`~FinitePoset.linear_extensions` | Return the enumerated set of all the linear extensions of the poset. :meth:`~FinitePoset.promotion` | Return the (extended) promotion on the linear extension of the poset. :meth:`~FinitePoset.evacuation` | Return evacuation on the linear extension associated to the poset.
**Miscellanous**
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~FinitePoset.sorted` | Return given list sorted by the poset. :meth:`~FinitePoset.isomorphic_subposets` | Return all subposets isomorphic to another poset. :meth:`~FinitePoset.isomorphic_subposets_iterator` | Return an iterator over the subposets isomorphic to another poset. :meth:`~FinitePoset.has_isomorphic_subposet` | Return ``True`` if the poset contains a subposet isomorphic to another poset. :meth:`~FinitePoset.moebius_function` | Return the value of Möbius function of given elements in the poset. :meth:`~FinitePoset.moebius_function_matrix` | Return a matrix whose ``(i,j)`` entry is the value of the Möbius function evaluated at ``self.linear_extension()[i]`` and ``self.linear_extension()[j]``. :meth:`~FinitePoset.coxeter_transformation` | Return the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules. :meth:`~FinitePoset.list` | List the elements of the poset. :meth:`~FinitePoset.cuts` | Return the cuts of the given poset. :meth:`~FinitePoset.dilworth_decomposition` | Return a partition of the points into the minimal number of chains. :meth:`~FinitePoset.greene_shape` | Computes the Greene-Kleitman partition aka Greene shape of the poset ``self``. :meth:`~FinitePoset.incidence_algebra` | Return the incidence algebra of ``self``. :meth:`~FinitePoset.is_EL_labelling` | Return whether ``f`` is an EL labelling of the poset. :meth:`~FinitePoset.isomorphic_subposets_iterator` | Return an iterator over the subposets isomorphic to another poset. :meth:`~FinitePoset.isomorphic_subposets` | Return all subposets isomorphic to another poset. :meth:`~FinitePoset.lequal_matrix` | Computes the matrix whose ``(i,j)`` entry is 1 if ``self.linear_extension()[i] < self.linear_extension()[j]`` and 0 otherwise. :meth:`~FinitePoset.level_sets` | Return a list l such that l[i+1] is the set of minimal elements of the poset obtained by removing the elements in l[0], l[1], ..., l[i]. :meth:`~FinitePoset.order_complex` | Return the order complex associated to this poset. :meth:`~FinitePoset.p_partition_enumerator` | Return a `P`-partition enumerator of the poset. :meth:`~FinitePoset.random_order_ideal` | Return a random order ideal of ``self`` with uniform probability. :meth:`~FinitePoset.rank` | Return the rank of an element, or the rank of the poset. :meth:`~FinitePoset.rank_function` | Return a rank function of the poset, if it exists. :meth:`~FinitePoset.unwrap` | Unwraps an element of this poset. :meth:`~FinitePoset.with_linear_extension` | Return a copy of ``self`` with a different default linear extension.
Classes and functions --------------------- """
#***************************************************************************** # Copyright (C) 2008 Peter Jipsen <jipsen@chapman.edu> # Copyright (C) 2008 Franco Saliola <saliola@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** # python3 from __future__ import division, print_function, absolute_import
from six.moves import range from six import iteritems
import copy from sage.misc.cachefunc import cached_method from sage.misc.lazy_attribute import lazy_attribute from sage.misc.misc_c import prod from sage.functions.other import floor from sage.categories.category import Category from sage.categories.sets_cat import Sets from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets from sage.categories.posets import Posets from sage.categories.finite_posets import FinitePosets from sage.structure.unique_representation import UniqueRepresentation from sage.structure.parent import Parent from sage.rings.integer import Integer from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ from sage.rings.polynomial.polynomial_ring import polygen from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.graphs.digraph import DiGraph from sage.graphs.digraph_generators import digraphs from sage.combinat.posets.hasse_diagram import HasseDiagram from sage.combinat.posets.elements import PosetElement from sage.combinat.combinatorial_map import combinatorial_map from sage.misc.superseded import deprecated_function_alias
def Poset(data=None, element_labels=None, cover_relations=False, linear_extension=False, category=None, facade=None, key=None): r""" Construct a finite poset from various forms of input data.
INPUT:
- ``data`` -- different input are accepted by this constructor:
1. A two-element list or tuple ``(E, R)``, where ``E`` is a collection of elements of the poset and ``R`` is a collection of relations ``x <= y``, each represented as a two-element list/tuple/iterable such as ``[x, y]``. The poset is then the transitive closure of the provided relations. If ``cover_relations=True``, then ``R`` is assumed to contain exactly the cover relations of the poset. If ``E`` is empty, then ``E`` is taken to be the set of elements appearing in the relations ``R``.
2. A two-element list or tuple ``(E, f)``, where ``E`` is the set of elements of the poset and ``f`` is a function such that, for any pair ``x, y`` of elements of ``E``, ``f(x, y)`` returns whether ``x <= y``. If ``cover_relations=True``, then ``f(x, y)`` should instead return whether ``x`` is covered by ``y``.
3. A dictionary, list or tuple of upper covers: ``data[x]`` is a list of the elements that cover the element `x` in the poset.
.. WARNING::
If data is a list or tuple of length `2`, then it is handled by the above case..
4. An acyclic, loop-free and multi-edge free ``DiGraph``. If ``cover_relations`` is ``True``, then the edges of the digraph are assumed to correspond to the cover relations of the poset. Otherwise, the cover relations are computed.
5. A previously constructed poset (the poset itself is returned).
- ``element_labels`` -- (default: ``None``); an optional list or dictionary of objects that label the poset elements.
- ``cover_relations`` -- a boolean (default: ``False``); whether the data can be assumed to describe a directed acyclic graph whose arrows are cover relations; otherwise, the cover relations are first computed.
- ``linear_extension`` -- a boolean (default: ``False``); whether to use the provided list of elements as default linear extension for the poset; otherwise a linear extension is computed. If the data is given as the pair ``(E, f)``, then ``E`` is taken to be the linear extension.
- ``facade`` -- a boolean or ``None`` (default); whether the :meth:`Poset`'s elements should be wrapped to make them aware of the Poset they belong to.
* If ``facade = True``, the :meth:`Poset`'s elements are exactly those given as input.
* If ``facade = False``, the :meth:`Poset`'s elements will become :class:`~sage.combinat.posets.posets.PosetElement` objects.
* If ``facade = None`` (default) the expected behaviour is the behaviour of ``facade = True``, unless the opposite can be deduced from the context (i.e. for instance if a :meth:`Poset` is built from another :meth:`Poset`, itself built with ``facade = False``)
OUTPUT:
``FinitePoset`` -- an instance of the :class:`FinitePoset` class.
If ``category`` is specified, then the poset is created in this category instead of :class:`FinitePosets`.
.. SEEALSO::
:class:`Posets`, :class:`~sage.categories.posets.Posets`, :class:`FinitePosets`
EXAMPLES:
1. Elements and cover relations::
sage: elms = [1,2,3,4,5,6,7] sage: rels = [[1,2],[3,4],[4,5],[2,5]] sage: Poset((elms, rels), cover_relations = True, facade = False) Finite poset containing 7 elements
Elements and non-cover relations::
sage: elms = [1,2,3,4] sage: rels = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] sage: P = Poset( [elms,rels] ,cover_relations=False); P Finite poset containing 4 elements sage: P.cover_relations() [[1, 2], [2, 3], [3, 4]]
2. Elements and function: the standard permutations of [1, 2, 3, 4] with the Bruhat order::
sage: elms = Permutations(4) sage: fcn = lambda p,q : p.bruhat_lequal(q) sage: Poset((elms, fcn)) Finite poset containing 24 elements
With a function that identifies the cover relations: the set partitions of `\{1, 2, 3\}` ordered by refinement::
sage: elms = SetPartitions(3) sage: def fcn(A, B): ....: if len(A) != len(B)+1: ....: return False ....: for a in A: ....: if not any(set(a).issubset(b) for b in B): ....: return False ....: return True sage: Poset((elms, fcn), cover_relations=True) Finite poset containing 5 elements
3. A dictionary of upper covers::
sage: Poset({'a':['b','c'], 'b':['d'], 'c':['d'], 'd':[]}) Finite poset containing 4 elements
A list of upper covers::
sage: Poset([[1,2],[4],[3],[4],[]]) Finite poset containing 5 elements
A list of upper covers and a dictionary of labels::
sage: elm_labs = {0:"a",1:"b",2:"c",3:"d",4:"e"} sage: P = Poset([[1,2],[4],[3],[4],[]], elm_labs, facade = False) sage: P.list() [a, b, c, d, e]
.. WARNING::
The special case where the argument data is a list or tuple of length 2 is handled by the above cases. So you cannot use this method to input a 2-element poset.
4. An acyclic DiGraph.
::
sage: dag = DiGraph({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}) sage: Poset(dag) Finite poset containing 6 elements
Any directed acyclic graph without loops or multiple edges, as long as ``cover_relations=False``::
sage: dig = DiGraph({0:[2,3], 1:[3,4,5], 2:[5], 3:[5], 4:[5]}) sage: dig.allows_multiple_edges() False sage: dig.allows_loops() False sage: dig.transitive_reduction() == dig False sage: Poset(dig, cover_relations=False) Finite poset containing 6 elements sage: Poset(dig, cover_relations=True) Traceback (most recent call last): ... ValueError: Hasse diagram is not transitively reduced
.. rubric:: Default Linear extension
Every poset `P` obtained with ``Poset`` comes equipped with a default linear extension, which is also used for enumerating its elements. By default, this linear extension is computed, and has no particular significance::
sage: P = Poset((divisors(12), attrcall("divides"))) sage: P.list() [1, 2, 4, 3, 6, 12] sage: P.linear_extension() [1, 2, 4, 3, 6, 12]
You may enforce a specific linear extension using the ``linear_extension`` option::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: P.linear_extension() [1, 2, 3, 4, 6, 12]
Depending on popular request, ``Poset`` might eventually get modified to always use the provided list of elements as default linear extension, when it is one.
.. SEEALSO:: :meth:`FinitePoset.linear_extensions`
.. rubric:: Facade posets
When ``facade = False``, the elements of a poset are wrapped so as to make them aware that they belong to that poset::
sage: P = Poset(DiGraph({'d':['c','b'],'c':['a'],'b':['a']}), facade = False) sage: d,c,b,a = list(P) sage: a.parent() is P True
This allows for comparing elements according to `P`::
sage: c < a True
However, this may have surprising effects::
sage: my_elements = ['a','b','c','d'] sage: any(x in my_elements for x in P) False
and can be annoying when one wants to manipulate the elements of the poset::
sage: a + b Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for +: 'Finite poset containing 4 elements' and 'Finite poset containing 4 elements' sage: a.element + b.element 'ab'
By default, facade posets are constructed instead::
sage: P = Poset(DiGraph({'d':['c','b'],'c':['a'],'b':['a']}))
In this example, the elements of the poset remain plain strings::
sage: d,c,b,a = list(P) sage: type(a) <... 'str'>
Of course, those strings are not aware of `P`. So to compare two such strings, one needs to query `P`::
sage: a < b True sage: P.lt(a,b) False
which models the usual mathematical notation `a <_P b`.
Most operations seem to still work, but at this point there is no guarantee whatsoever::
sage: P.list() ['d', 'c', 'b', 'a'] sage: P.principal_order_ideal('a') ['d', 'c', 'b', 'a'] sage: P.principal_order_ideal('b') ['d', 'b'] sage: P.principal_order_ideal('d') ['d'] sage: TestSuite(P).run()
.. WARNING::
:class:`DiGraph` is used to construct the poset, and the vertices of a :class:`DiGraph` are converted to plain Python :class:`int`'s if they are :class:`Integer`'s::
sage: G = DiGraph({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}) sage: type(G.vertices()[0]) <... 'int'>
This is worked around by systematically converting back the vertices of a poset to :class:`Integer`'s if they are :class:`int`'s::
sage: P = Poset((divisors(15), attrcall("divides")), facade = False) sage: type(P.an_element().element) <... 'sage.rings.integer.Integer'>
sage: P = Poset((divisors(15), attrcall("divides")), facade=True) sage: type(P.an_element()) <... 'sage.rings.integer.Integer'>
This may be abusive::
sage: P = Poset((range(5), operator.le), facade = True) sage: P.an_element().parent() Integer Ring
.. rubric:: Unique representation
As most parents, :class:`Poset` have unique representation (see :class:`UniqueRepresentation`). Namely if two posets are created from two equal data, then they are not only equal but actually identical::
sage: data1 = [[1,2],[3],[3]] sage: data2 = [[1,2],[3],[3]] sage: P1 = Poset(data1) sage: P2 = Poset(data2) sage: P1 == P2 True sage: P1 is P2 True
In situations where this behaviour is not desired, one can use the ``key`` option::
sage: P1 = Poset(data1, key = "foo") sage: P2 = Poset(data2, key = "bar") sage: P1 is P2 False sage: P1 == P2 False
``key`` can be any hashable value and is passed down to :class:`UniqueRepresentation`. It is otherwise ignored by the poset constructor.
TESTS::
sage: P = Poset([[1,2],[3],[3]]) sage: type(hash(P)) <... 'int'>
Bad input::
sage: Poset([1,2,3], lambda x,y : x<y) Traceback (most recent call last): ... TypeError: element_labels should be a dict or a list if different from None. (Did you intend data to be equal to a pair ?)
Another kind of bad input, digraphs with oriented cycles::
sage: Poset(DiGraph([[1,2],[2,3],[3,4],[4,1]])) Traceback (most recent call last): ... ValueError: The graph is not directed acyclic """ # Avoiding some errors from the user when data should be a pair not isinstance(element_labels, dict) and not isinstance(element_labels, list)): "different from None. (Did you intend data to be "+ "equal to a pair ?)")
#Convert data to a DiGraph P = P.relabel(element_labels) else: if element_labels is None: return FinitePoset(data, elements=data._elements, category=category, facade=facade) else: return FinitePoset(data, elements=element_labels, category=category, facade=facade) else: # type 1 # check that relations are relations except ValueError: raise TypeError("not a list of relations") # type 3, list/tuple of upper covers format="dict_of_lists") else: raise ValueError("not valid poset data")
# DEBUG: At this point D should be a DiGraph.
# Determine cover relations, if necessary.
# Check that the digraph does not contain loops, multiple edges # and is transitively reduced. raise ValueError("Hasse diagram contains loops") raise ValueError("Hasse diagram contains multiple edges")
elements = element_labels # Compute a linear extension of the poset (a topological sort). except Exception: raise ValueError("Hasse diagram contains cycles") else:
class FinitePoset(UniqueRepresentation, Parent): r""" A (finite) `n`-element poset constructed from a directed acyclic graph.
INPUT:
- ``hasse_diagram`` -- an instance of :class:`~sage.combinat.posets.posets.FinitePoset`, or a :class:`DiGraph` that is transitively-reduced, acyclic, loop-free, and multiedge-free.
- ``elements`` -- an optional list of elements, with ``element[i]`` corresponding to vertex ``i``. If ``elements`` is ``None``, then it is set to be the vertex set of the digraph. Note that if this option is set, then ``elements`` is considered as a specified linear extension of the poset and the `linear_extension` attribute is set.
- ``category`` -- :class:`FinitePosets`, or a subcategory thereof.
- ``facade`` -- a boolean or ``None`` (default); whether the :class:`~sage.combinat.posets.posets.FinitePoset`'s elements should be wrapped to make them aware of the Poset they belong to.
* If ``facade = True``, the :class:`~sage.combinat.posets.posets.FinitePoset`'s elements are exactly those given as input.
* If ``facade = False``, the :class:`~sage.combinat.posets.posets.FinitePoset`'s elements will become :class:`~sage.combinat.posets.posets.PosetElement` objects.
* If ``facade = None`` (default) the expected behaviour is the behaviour of ``facade = True``, unless the opposite can be deduced from the context (i.e. for instance if a :class:`~sage.combinat.posets.posets.FinitePoset` is built from another :class:`~sage.combinat.posets.posets.FinitePoset`, itself built with ``facade = False``)
- ``key`` -- any hashable value (default: ``None``).
EXAMPLES::
sage: uc = [[2,3], [], [1], [1], [1], [3,4]] sage: from sage.combinat.posets.posets import FinitePoset sage: P = FinitePoset(DiGraph(dict([[i,uc[i]] for i in range(len(uc))])), facade=False); P Finite poset containing 6 elements sage: P.cover_relations() [[5, 4], [5, 3], [4, 1], [0, 2], [0, 3], [2, 1], [3, 1]] sage: TestSuite(P).run() sage: P.category() Category of finite enumerated posets sage: P.__class__ <class 'sage.combinat.posets.posets.FinitePoset_with_category'>
sage: Q = sage.combinat.posets.posets.FinitePoset(P, facade = False); Q Finite poset containing 6 elements
sage: Q is P True
We keep the same underlying Hasse diagram, but change the elements::
sage: Q = sage.combinat.posets.posets.FinitePoset(P, elements=[1,2,3,4,5,6], facade=False); Q Finite poset containing 6 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 5], [2, 6], [3, 4], [3, 5], [4, 6], [5, 6]]
We test the facade argument::
sage: P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=False) sage: P.category() Category of finite enumerated posets sage: parent(P[0]) is P True
sage: Q = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=True) sage: Q.category() Category of facade finite enumerated posets sage: parent(Q[0]) is str True sage: TestSuite(Q).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented
Changing a non facade poset to a facade poset::
sage: PQ = Poset(P, facade=True) sage: PQ.category() Category of facade finite enumerated posets sage: parent(PQ[0]) is str True sage: PQ is Q True
Changing a facade poset to a non facade poset::
sage: QP = Poset(Q, facade = False) sage: QP.category() Category of finite enumerated posets sage: parent(QP[0]) is QP True
.. NOTE::
A class that inherits from this class needs to define ``Element``. This is the class of the elements that the inheriting class contains. For example, for this class, ``FinitePoset``, ``Element`` is ``PosetElement``. It can also define ``_dual_class`` which is the class of dual posets of this class. E.g. ``FiniteMeetSemilattice._dual_class`` is ``FiniteJoinSemilattice``.
TESTS:
Equality is derived from :class:`UniqueRepresentation`. We check that this gives consistent results::
sage: P = Poset([[1,2],[3],[3]]) sage: P == P True sage: Q = Poset([[1,2],[],[1]]) sage: Q == P False sage: p1, p2 = Posets(2).list() sage: p2 == p1, p1 != p2 (False, True) sage: [[p1.__eq__(p2) for p1 in Posets(2)] for p2 in Posets(2)] [[True, False], [False, True]] sage: [[p2.__eq__(p1) for p1 in Posets(2)] for p2 in Posets(2)] [[True, False], [False, True]] sage: [[p2 == p1 for p1 in Posets(3)] for p2 in Posets(3)] [[True, False, False, False, False], [False, True, False, False, False], [False, False, True, False, False], [False, False, False, True, False], [False, False, False, False, True]]
sage: [[p1.__ne__(p2) for p1 in Posets(2)] for p2 in Posets(2)] [[False, True], [True, False]] sage: P = Poset([[1,2,4],[3],[3]]) sage: Q = Poset([[1,2],[],[1],[4]]) sage: P != Q True sage: P != P False sage: Q != Q False sage: [[p1.__ne__(p2) for p1 in Posets(2)] for p2 in Posets(2)] [[False, True], [True, False]]
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: Q = Poset(P) sage: Q == P False sage: Q = Poset(P, linear_extension=True) sage: Q == P True """
# The parsing of the construction data (like a list of cover relations) # into a :class:`DiGraph` is done in :func:`Poset`. @staticmethod def __classcall__(cls, hasse_diagram, elements=None, category=None, facade=None, key=None): """ Normalizes the arguments passed to the constructor.
INPUT:
- ``hasse_diagram`` -- a :class:`DiGraph` or a :class:`FinitePoset` that is labeled by the elements of the poset - ``elements`` -- (default: ``None``) the default linear extension or ``None`` if no such default linear extension is wanted - ``category`` -- (optional) a subcategory of :class:`FinitePosets` - ``facade`` -- (optional) boolean if this is a facade parent or not - ``key`` -- (optional) a key value
TESTS::
sage: P = sage.combinat.posets.posets.FinitePoset(DiGraph()) sage: type(P) <class 'sage.combinat.posets.posets.FinitePoset_with_category'> sage: TestSuite(P).run()
See also the extensive tests in the class documentation.
We check that :trac:`17059` is fixed::
sage: p = Poset() sage: p is Poset(p, category=p.category()) True """ else: else: # Standardize the category by letting the Facade axiom be carried # by the facade variable elements=elements, category=category, facade=facade, key=key)
def __init__(self, hasse_diagram, elements, category, facade, key): """ EXAMPLES::
sage: P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade = False) sage: type(P) <class 'sage.combinat.posets.posets.FinitePoset_with_category'>
The internal data structure currently consists of:
- the Hasse diagram of the poset, represented by a DiGraph with vertices labelled 0,...,n-1 according to a linear extension of the poset (that is if `i \mapsto j` is an edge then `i<j`), together with some extra methods (see :class:`sage.combinat.posets.hasse_diagram.HasseDiagram`)::
sage: P._hasse_diagram Hasse diagram of a poset containing 4 elements sage: P._hasse_diagram.cover_relations() [(0, 1), (1, 2), (2, 3)]
- a tuple of the original elements, not wrapped as elements of ``self`` (but see also ``P._list``)::
sage: P._elements ('a', 'b', 'c', 'd')
``P._elements[i]`` gives the element of ``P`` corresponding to the vertex ``i``
- a dictionary mapping back elements to vertices::
sage: P._element_to_vertex_dict {'a': 0, 'b': 1, 'c': 2, 'd': 3}
- and a boolean stating whether the poset is a facade poset::
sage: P._is_facade False
This internal data structure is subject to change at any point. Do not break encapsulation!
TESTS::
sage: TestSuite(P).run()
See also the extensive tests in the class documentation. """ # Compute a linear extension of the poset (a topological sort). except Exception: raise ValueError("Hasse diagram contains cycles") else: # Work around the fact that, currently, when a DiGraph is # created with Integer's as vertices, those vertices are # converted to plain int's. This is a bit abusive. # Relabel using the linear_extension. # So range(len(D)) becomes a linear extension of the poset. for i in range(len(self._elements)) )
@lazy_attribute def _list(self): """ The list of the elements of ``self``, each wrapped to have ``self`` as parent
EXAMPLES::
sage: P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade = False) sage: L = P._list; L (a, b, c, d) sage: type(L[0]) <class 'sage.combinat.posets.posets.FinitePoset_with_category.element_class'> sage: L[0].parent() is P True
Constructing them once for all makes future conversions between the vertex id and the element faster. This also ensures unique representation of the elements of this poset, which could be used to later speed up certain operations (equality test, ...) """ else: for vertex in range(len(self._elements)))
# This defines the type (class) of elements of poset. Element = PosetElement
def _element_to_vertex(self, element): """ Given an element of the poset (wrapped or not), returns the corresponding vertex of the Hasse diagram.
EXAMPLES::
sage: P = Poset((divisors(15), attrcall("divides"))) sage: list(P) [1, 3, 5, 15] sage: x = P(5) sage: P._element_to_vertex(x) 2
The same with a non-wrapped element of `P`::
sage: P._element_to_vertex(5) 2
TESTS::
sage: P = Poset((divisors(15), attrcall("divides")), facade = False)
Testing for wrapped elements::
sage: all(P._vertex_to_element(P._element_to_vertex(x)) is x for x in P) True
Testing for non-wrapped elements::
sage: all(P._vertex_to_element(P._element_to_vertex(x)) is P(x) for x in divisors(15)) True
Testing for non-wrapped elements for a facade poset::
sage: P = Poset((divisors(15), attrcall("divides")), facade = True) sage: all(P._vertex_to_element(P._element_to_vertex(x)) is x for x in P) True """ else:
def _vertex_to_element(self, vertex): """ Return the element of ``self`` corresponding to the vertex ``vertex`` of the Hasse diagram.
It is wrapped if ``self`` is not a facade poset.
EXAMPLES::
sage: P = Poset((divisors(15), attrcall("divides")), facade = False) sage: x = P._vertex_to_element(2) sage: x 5 sage: x.parent() is P True
sage: P = Poset((divisors(15), attrcall("divides")), facade = True) sage: x = P._vertex_to_element(2) sage: x 5 sage: x.parent() is ZZ True """
def unwrap(self, element): """ Return the element ``element`` of the poset ``self`` in unwrapped form.
INPUT:
- ``element`` -- an element of ``self``
EXAMPLES::
sage: P = Poset((divisors(15), attrcall("divides")), facade = False) sage: x = P.an_element(); x 1 sage: x.parent() Finite poset containing 4 elements sage: P.unwrap(x) 1 sage: P.unwrap(x).parent() Integer Ring
For a non facade poset, this is equivalent to using the ``.element`` attribute::
sage: P.unwrap(x) is x.element True
For a facade poset, this does nothing::
sage: P = Poset((divisors(15), attrcall("divides")), facade=True) sage: x = P.an_element() sage: P.unwrap(x) is x True
This method is useful in code where we don't know if ``P`` is a facade poset or not. """ else:
def __contains__(self, x): r""" Returns True if x is an element of the poset.
TESTS::
sage: from sage.combinat.posets.posets import FinitePoset sage: P5 = FinitePoset(DiGraph({(5,):[(4,1),(3,2)], \ (4,1):[(3,1,1),(2,2,1)], \ (3,2):[(3,1,1),(2,2,1)], \ (3,1,1):[(2,1,1,1)], \ (2,2,1):[(2,1,1,1)], \ (2,1,1,1):[(1,1,1,1,1)], \ (1,1,1,1,1):[]})) sage: x = P5.list()[3] sage: x in P5 True
For the sake of speed, an element with the right class and parent is assumed to be in this parent. This can possibly be counterfeited by feeding garbage to the constructor::
sage: x = P5.element_class(P5, "a", 5) sage: x in P5 True """
is_parent_of = __contains__
def _element_constructor_(self, element): """ Constructs an element of ``self``
EXAMPLES::
sage: from sage.combinat.posets.posets import FinitePoset sage: P = FinitePoset(DiGraph({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}), facade = False) sage: P(5) 5 sage: Q = FinitePoset(DiGraph({5:[2,3], 1:[3,4], 2:[0], 3:[0], 4:[0]}), facade = False) sage: Q(5) 5
Accessing the ``i``-th element of ``self`` as ``P[i]``::
sage: P = FinitePoset(DiGraph({'a':['b','c'], 'b':['d'], 'c':['d'], 'd':[]}), facade = False) sage: P('a') == P[0] True sage: P('d') == P[-1] True
TESTS::
sage: P = Poset(DiGraph({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}), facade = False) sage: all(P(x) is x for x in P) True sage: P = Poset((divisors(15), attrcall("divides")), facade = True) sage: all(P(x) is x for x in P) True """ % type(element))
def __call__(self, element): """ Creates elements of this poset
This overrides the generic call method for all parents :meth:`Parent.__call__`, as a work around to allow for facade posets over plain Python objects (e.g. Python's int's). Indeed, the default __call__ method expects the result of :meth:`_element_constructor_` to be a Sage element (see :meth:`sage.structure.coerce_maps.DefaultConvertMap_unique._call_`)::
sage: P = Poset(DiGraph({'d':['c','b'],'c':['a'],'b':['a']}), ....: facade = True) sage: P('a') # indirect doctest 'a' sage: TestSuite(P).run() sage: P = Poset(((False, True), operator.eq), facade = True) sage: P(True) 1 """
def hasse_diagram(self): r""" Return the Hasse diagram of the poset as a Sage :class:`DiGraph`.
The Hasse diagram is a directed graph where vertices are the elements of the poset and there is an edge from `u` to `v` whenever `v` covers `u` in the poset.
If ``dot2tex`` is installed, then this sets the Hasse diagram's latex options to use the ``dot2tex`` formatting.
EXAMPLES::
sage: P = posets.DivisorLattice(12) sage: H = P.hasse_diagram(); H Digraph on 6 vertices sage: P.cover_relations() [[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]] sage: H.edges(labels=False) [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]
TESTS::
sage: Poset().hasse_diagram() Digraph on 0 vertices
sage: P = Poset((divisors(15), attrcall("divides")), facade=True) sage: H = P.hasse_diagram() sage: H.vertices() [1, 3, 5, 15] sage: H.edges() [(1, 3, None), (1, 5, None), (3, 15, None), (5, 15, None)] sage: H.set_latex_options(format="dot2tex") sage: view(H) # optional - dot2tex, not tested (opens external window) """ G.set_latex_options(format='dot2tex', prog='dot', rankdir='up',)
def _latex_(self): r""" Return a latex method for the poset.
EXAMPLES::
sage: P = Poset(([1,2], [[1,2]]), cover_relations = True) sage: print(P._latex_()) #optional - dot2tex graphviz \begin{tikzpicture}[>=latex,line join=bevel,] %% \node (node_1) at (6.0...bp,57.0...bp) [draw,draw=none] {$2$}; \node (node_0) at (6.0...bp,7.0...bp) [draw,draw=none] {$1$}; \draw [black,->] (node_0) ..controls (...bp,...bp) and (...bp,...bp) .. (node_1); % \end{tikzpicture} """ return self.hasse_diagram()._latex_()
def _repr_(self): r""" Returns a string representation of the poset.
TESTS::
sage: partitions_of_five = {(5,):[(4,1),(3,2)], \ (4,1):[(3,1,1),(2,2,1)], \ (3,2):[(3,1,1),(2,2,1)], \ (3,1,1):[(2,1,1,1)], \ (2,2,1):[(2,1,1,1)], \ (2,1,1,1):[(1,1,1,1,1)], \ (1,1,1,1,1):[]} sage: P5 = Poset(partitions_of_five) sage: P5._repr_() 'Finite poset containing 7 elements' """
def _rich_repr_(self, display_manager, **kwds): """ Rich Output Magic Method
See :mod:`sage.repl.rich_output` for details.
EXAMPLES::
sage: from sage.repl.rich_output import get_display_manager sage: dm = get_display_manager() sage: Poset()._rich_repr_(dm, edge_labels=True) OutputPlainText container
The ``supplemental_plot`` preference lets us control whether this object is shown as text or picture+text::
sage: dm.preferences.supplemental_plot 'never' sage: del dm.preferences.supplemental_plot sage: posets.ChainPoset(20) Finite lattice containing 20 elements (use the .plot() method to plot) sage: dm.preferences.supplemental_plot = 'never' """ # Under certain circumstances we display the plot as graphics plot_kwds = dict(kwds) plot_kwds.setdefault('title', repr(self)) output = self.plot(**plot_kwds)._rich_repr_(display_manager) if output is not None: return output # create text for non-graphical output else: # latex() produces huge tikz environment, override return tp.OutputLatex(r'\text{{{0}}}'.format(text))
def __iter__(self): """ Iterates through the elements of a linear extension of the poset.
EXAMPLES::
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] }) sage: sorted(D.__iter__()) [0, 1, 2, 3, 4] """
def sorted(self, l, allow_incomparable=True, remove_duplicates=False): """ Return the list `l` sorted by the poset.
INPUT:
- ``l`` -- a list of elements of the poset - ``allow_incomparable`` -- a Boolean. If ``True`` (the default), return incomparable elements in some order; if ``False``, raise an error if ``l`` is not a chain of the poset. - ``remove_duplicates`` - a Boolean. If ``True``, remove duplicates from the output list.
EXAMPLES::
sage: P = posets.DivisorLattice(36) sage: P.sorted([1, 4, 1, 6, 2, 12]) # Random order for 4 and 6 [1, 1, 2, 4, 6, 12] sage: P.sorted([1, 4, 1, 6, 2, 12], remove_duplicates=True) [1, 2, 4, 6, 12] sage: P.sorted([1, 4, 1, 6, 2, 12], allow_incomparable=False) Traceback (most recent call last): ... ValueError: the list contains incomparable elements
sage: P = Poset({7:[1, 5], 1:[2, 6], 5:[3], 6:[3, 4]}) sage: P.sorted([4, 1, 4, 5, 7]) # Random order for 1 and 5 [7, 1, 5, 4, 4] sage: P.sorted([1, 4, 4, 7], remove_duplicates=True) [7, 1, 4] sage: P.sorted([4, 1, 4, 5, 7], allow_incomparable=False) Traceback (most recent call last): ... ValueError: the list contains incomparable elements
TESTS::
sage: P = posets.PentagonPoset() sage: P.sorted([], allow_incomparable=True, remove_duplicates=True) [] sage: P.sorted([], allow_incomparable=False, remove_duplicates=True) [] sage: P.sorted([], allow_incomparable=True, remove_duplicates=False) [] sage: P.sorted([], allow_incomparable=False, remove_duplicates=False) [] """
else:
def linear_extension(self, linear_extension=None, check=True): """ Return a linear extension of this poset.
A linear extension of a finite poset `P` of size `n` is a total ordering `\pi := \pi_0 \pi_1 \ldots \pi_{n-1}` of its elements such that `i<j` whenever `\pi_i < \pi_j` in the poset `P`.
INPUT:
- ``linear_extension`` -- (default: ``None``) a list of the elements of ``self`` - ``check`` -- a boolean (default: True); whether to check that ``linear_extension`` is indeed a linear extension of ``self``.
EXAMPLES::
sage: P = Poset((divisors(15), attrcall("divides")), facade=True)
Without optional argument, the default linear extension of the poset is returned, as a plain list::
sage: P.linear_extension() [1, 3, 5, 15]
Otherwise, a full-featured linear extension is constructed as an element of ``P.linear_extensions()``::
sage: l = P.linear_extension([1,5,3,15]); l [1, 5, 3, 15] sage: type(l) <class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category.element_class'> sage: l.parent() The set of all linear extensions of Finite poset containing 4 elements
By default, the linear extension is checked for correctness::
sage: l = P.linear_extension([1,3,15,5]) Traceback (most recent call last): ... ValueError: [1, 3, 15, 5] is not a linear extension of Finite poset containing 4 elements
This can be disabled (at your own risks!) with::
sage: P.linear_extension([1,3,15,5], check=False) [1, 3, 15, 5]
.. SEEALSO:: :meth:`is_linear_extension`, :meth:`linear_extensions`
.. TODO::
- Is it acceptable to have those two features for a single method?
- In particular, we miss a short idiom to get the default linear extension """
@cached_method def linear_extensions(self, facade=False): """ Returns the enumerated set of all the linear extensions of this poset
INPUT:
- ``facade`` -- a boolean (default: ``False``); whether to return the linear extensions as plain lists
.. warning::
The ``facade`` option is not yet fully functional::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: L = P.linear_extensions(facade=True); L The set of all linear extensions of Finite poset containing 6 elements with distinguished linear extension sage: L([1, 2, 3, 4, 6, 12]) Traceback (most recent call last): ... TypeError: Cannot convert list to sage.structure.element.Element
EXAMPLES::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: L = P.linear_extensions(); L The set of all linear extensions of Finite poset containing 6 elements with distinguished linear extension sage: l = L.an_element(); l [1, 2, 3, 4, 6, 12] sage: L.cardinality() 5 sage: L.list() [[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 4, 12], [1, 2, 4, 3, 6, 12], [1, 3, 2, 4, 6, 12], [1, 3, 2, 6, 4, 12]]
Each element is aware that it is a linear extension of `P`::
sage: type(l.parent()) <class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category'>
With ``facade=True``, the elements of ``L`` are plain lists instead::
sage: L = P.linear_extensions(facade=True) sage: l = L.an_element() sage: type(l) <... 'list'>
.. WARNING::
In Sage <= 4.8, this function used to return a plain list of lists. To recover the previous functionality, please use::
sage: L = list(P.linear_extensions(facade=True)); L [[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 4, 12], [1, 2, 4, 3, 6, 12], [1, 3, 2, 4, 6, 12], [1, 3, 2, 6, 4, 12]] sage: type(L[0]) <... 'list'>
.. SEEALSO:: :meth:`linear_extension`, :meth:`is_linear_extension`
TESTS::
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] }) sage: list(D.linear_extensions()) [[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3]]
"""
def is_linear_extension(self, l): """ Returns whether ``l`` is a linear extension of ``self``
INPUT:
- ``l`` -- a list (or iterable) containing all of the elements of ``self`` exactly once
EXAMPLES::
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: P.is_linear_extension([1, 2, 4, 3, 6, 12]) True sage: P.is_linear_extension([1, 2, 4, 6, 3, 12]) False
sage: [p for p in Permutations(list(P)) if P.is_linear_extension(p)] [[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 4, 12], [1, 2, 4, 3, 6, 12], [1, 3, 2, 4, 6, 12], [1, 3, 2, 6, 4, 12]] sage: list(P.linear_extensions()) [[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 4, 12], [1, 2, 4, 3, 6, 12], [1, 3, 2, 4, 6, 12], [1, 3, 2, 6, 4, 12]]
.. NOTE::
This is used and systematically tested in :class:`~sage.combinat.posets.linear_extensions.LinearExtensionsOfPosets`
.. SEEALSO:: :meth:`linear_extension`, :meth:`linear_extensions`
TESTS:
Check that :trac:`15313` is fixed::
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True) sage: P.is_linear_extension([1,2,4,3,6,12,1337]) False sage: P.is_linear_extension([1,2,4,3,6,666,12,1337]) False sage: P = Poset(DiGraph(5)) sage: P.is_linear_extension(['David', 'McNeil', 'La', 'Lamentable', 'Aventure', 'de', 'Simon', 'Wiesenthal']) False """ all(x in index for x in self) and all(index[i] < index[j] for (i,j) in self.cover_relations()))
def list(self): """ List the elements of the poset. This just returns the result of :meth:`linear_extension`.
EXAMPLES::
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] }, facade = False) sage: D.list() [0, 1, 2, 3, 4] sage: type(D.list()[0]) <class 'sage.combinat.posets.posets.FinitePoset_with_category.element_class'> """
def plot(self, label_elements=True, element_labels=None, layout='acyclic', cover_labels=None, **kwds): r""" Return a Graphic object for the Hasse diagram of the poset.
If the poset is ranked, the plot uses the rank function for the heights of the elements.
INPUT:
- Options to change element look:
* ``element_colors`` - a dictionary where keys are colors and values are lists of elements * ``element_color`` - a color for elements not set in ``element_colors`` * ``element_shape`` - the shape of elements, like ``'s'`` for square; see https://matplotlib.org/api/markers_api.html for the list * ``element_size`` (default: 200) - the size of elements * ``label_elements`` (default: ``True``) - whether to display element labels * ``element_labels`` (default: ``None``) - a dictionary where keys are elements and values are labels to show
- Options to change cover relation look:
* ``cover_colors`` - a dictionary where keys are colors and values are lists of cover relations given as pairs of elements * ``cover_color`` - a color for elements not set in ``cover_colors`` * ``cover_style`` - style for cover relations: ``'solid'``, ``'dashed'``, ``'dotted'`` or ``'dashdot'`` * ``cover_labels`` - a dictionary, list or function representing labels of the covers of the poset. When set to ``None`` (default) no label is displayed on the edges of the Hasse Diagram. * ``cover_labels_background`` - a background color for cover relations. The default is "white". To achieve a transparent background use "transparent".
- Options to change overall look:
* ``figsize`` (default: 8) - size of the whole plot * ``title`` - a title for the plot * ``fontsize`` - fontsize for the title * ``border`` (default: ``False``) - whether to draw a border over the plot
.. NOTE::
All options of :meth:`GenericGraph.plot <sage.graphs.generic_graph.GenericGraph.plot>` are also available through this function.
EXAMPLES:
This function can be used without any parameters::
sage: D12 = posets.DivisorLattice(12) sage: D12.plot() Graphics object consisting of 14 graphics primitives
Just the abstract form of the poset; examples of relabeling::
sage: D12.plot(label_elements=False) Graphics object consisting of 8 graphics primitives sage: d = {1: 0, 2: 'a', 3: 'b', 4: 'c', 6: 'd', 12: 1} sage: D12.plot(element_labels=d) Graphics object consisting of 14 graphics primitives sage: d = {i:str(factor(i)) for i in D12} sage: D12.plot(element_labels=d) Graphics object consisting of 14 graphics primitives
Some settings for coverings::
sage: d = {(a, b): b/a for a, b in D12.cover_relations()} sage: D12.plot(cover_labels=d, cover_color='gray', cover_style='dotted') Graphics object consisting of 21 graphics primitives
To emphasize some elements and show some options::
sage: L = LatticePoset({0: [1, 2, 3, 4], 1: [12], 2: [6, 7], ....: 3: [5, 9], 4: [5, 6, 10, 11], 5: [13], ....: 6: [12], 7: [12, 8, 9], 8: [13], 9: [13], ....: 10: [12], 11: [12], 12: [13]}) sage: F = L.frattini_sublattice() sage: F_internal = [c for c in F.cover_relations() if c in L.cover_relations()] sage: L.plot(figsize=12, border=True, element_shape='s', ....: element_size=400, element_color='white', ....: element_colors={'blue': F, 'green': L.double_irreducibles()}, ....: cover_color='lightgray', cover_colors={'black': F_internal}, ....: title='The Frattini\nsublattice in blue', fontsize=10) Graphics object consisting of 39 graphics primitives
TESTS:
We check that ``label_elements`` and ``element_labels`` are honored::
sage: def get_plot_labels(P): return sorted(t.string for t in P if isinstance(t, sage.plot.text.Text)) sage: P1 = Poset({ 0:[1,2], 1:[3], 2:[3,4] }) sage: P2 = Poset({ 0:[1,2], 1:[3], 2:[3,4] }, facade=True) sage: get_plot_labels(P1.plot(label_elements=False)) [] sage: get_plot_labels(P1.plot(label_elements=True)) [u'0', u'1', u'2', u'3', u'4'] sage: element_labels = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'} sage: get_plot_labels(P1.plot(element_labels=element_labels)) [u'a', u'b', u'c', u'd', u'e'] sage: get_plot_labels(P2.plot(element_labels=element_labels)) [u'a', u'b', u'c', u'd', u'e']
The following checks that :trac:`18936` has been fixed and labels still work::
sage: P = Poset({0: [1,2], 1:[3]}) sage: heights = {1 : [0], 2 : [1], 3 : [2,3]} sage: P.plot(heights=heights) Graphics object consisting of 8 graphics primitives sage: elem_labels = {0 : 'a', 1 : 'b', 2 : 'c', 3 : 'd'} sage: P.plot(element_labels=elem_labels, heights=heights) Graphics object consisting of 8 graphics primitives
Plot of the empty poset::
sage: P = Poset({}) sage: P.plot() Graphics object consisting of 0 graphics primitives """
'element_colors': 'vertex_colors', 'element_size': 'vertex_size', 'element_shape': 'vertex_shape', 'cover_color': 'edge_color', 'cover_labels_background': 'edge_labels_background', 'cover_colors': 'edge_colors', 'cover_style': 'edge_style', 'border': 'graph_border', }
# if relabeling is needed for (element, label) in element_labels.items())
cover_labels[(v, w)]) else: for (v, w, l) in cover_labels: graph.set_edge_label(self(v), self(w), l) else:
edge_labels=cover_labels, layout=layout, heights=heights, **kwds)
def show(self, label_elements=True, element_labels=None, cover_labels=None, **kwds): """ Displays the Hasse diagram of the poset.
INPUT:
- ``label_elements`` (default: ``True``) - whether to display element labels
- ``element_labels`` (default: ``None``) - a dictionary of element labels
- ``cover_labels`` - a dictionary, list or function representing labels of the covers of ``self``. When set to ``None`` (default) no label is displayed on the edges of the Hasse Diagram.
.. NOTE::
This method also accepts:
- All options of :meth:`GenericGraph.plot <sage.graphs.generic_graph.GenericGraph.plot>`
- All options of :meth:`Graphics.show <sage.plot.graphics.Graphics.show>`
EXAMPLES::
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] }) sage: D.plot(label_elements=False) Graphics object consisting of 6 graphics primitives sage: D.show() sage: elm_labs = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'} sage: D.show(element_labels=elm_labs)
One more example with cover labels::
sage: P = posets.PentagonPoset() sage: P.show(cover_labels=lambda a, b: a - b)
""" # We split the arguments into those meant for plot() and those meant for show() # # The plot_kwds dictionary only contains the options that graphplot # understands. These options are removed from kwds at the same time.
element_labels=element_labels, cover_labels=cover_labels, **plot_kwds).show(**kwds)
def level_sets(self): """ Return elements grouped by maximal number of cover relations from a minimal element.
This returns a list of lists ``l`` such that ``l[i]`` is the set of minimal elements of the poset obtained by removing the elements in ``l[0], l[1], ..., l[i-1]``. (In particular, ``l[0]`` is the set of minimal elements of ``self``.)
Every level is an antichain of the poset.
EXAMPLES::
sage: P = Poset({0:[1,2],1:[3],2:[3],3:[]}) sage: P.level_sets() [[0], [1, 2], [3]]
sage: Q = Poset({0:[1,2], 1:[3], 2:[4], 3:[4]}) sage: Q.level_sets() [[0], [1, 2], [3], [4]]
.. SEEALSO::
:meth:`dilworth_decomposition` to return elements grouped to chains. """ self._hasse_diagram.level_sets()]
def cover_relations(self): """ Return the list of pairs ``[x, y]`` of elements of the poset such that ``y`` covers ``x``.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.cover_relations() [[1, 2], [0, 2], [2, 3], [3, 4]] """
@combinatorial_map(name="cover_relations_graph") def cover_relations_graph(self): """ Return the (undirected) graph of cover relations.
EXAMPLES::
sage: P = Poset({0: [1, 2], 1: [3], 2: [3]}) sage: G = P.cover_relations_graph(); G Graph on 4 vertices sage: G.has_edge(3, 1), G.has_edge(3, 0) (True, False)
.. SEEALSO::
:meth:`hasse_diagram`
TESTS::
sage: Poset().cover_relations_graph() Graph on 0 vertices
Check that it is hashable and coincides with the Hasse diagram as a graph::
sage: P = Poset({0: [1, 2], 1: [3], 2: [3]}) sage: G = P.cover_relations_graph() sage: hash(G) == hash(G) True sage: G == Graph(P.hasse_diagram()) True """
def cover_relations_iterator(self): """ Return an iterator over the cover relations of the poset.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(P.cover_relations_iterator()) <... 'generator'> sage: [z for z in P.cover_relations_iterator()] [[1, 2], [0, 2], [2, 3], [3, 4]] """
def relations(self): r""" Return the list of all relations of the poset.
A relation is a pair of elements `x` and `y` such that `x \leq y` in the poset.
The number of relations is the dimension of the incidence algebra.
OUTPUT:
A list of pairs (each pair is a list), where the first element of the pair is less than or equal to the second element.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.relations() [[1, 1], [1, 2], [1, 3], [1, 4], [0, 0], [0, 2], [0, 3], [0, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]]
.. SEEALSO::
:meth:`relations_number`, :meth:`relations_iterator`
TESTS::
sage: P = Poset() # Test empty poset sage: P.relations() []
AUTHOR:
- Rob Beezer (2011-05-04) """
intervals = deprecated_function_alias(19360, relations)
def intervals_poset(self): """ Return the natural partial order on the set of intervals of the poset.
OUTPUT:
a finite poset
The poset of intervals of a poset `P` has the set of intervals `[x,y]` in `P` as elements, endowed with the order relation defined by `[x_1,y_1] \leq [x_2,y_2]` if and only if `x_1 \leq x_2` and `y_1 \leq y_2`.
This is also called `P` to the power *2*, meaning the poset of poset-morphisms from the 2-chain to `P`.
If `P` is a lattice, the result is also a lattice.
EXAMPLES::
sage: P = Poset({0:[1]}) sage: P.intervals_poset() Finite poset containing 3 elements
sage: P = posets.PentagonPoset() sage: P.intervals_poset() Finite lattice containing 13 elements
TESTS::
sage: P = Poset({}) sage: P.intervals_poset() Finite poset containing 0 elements
sage: P = Poset({0:[]}) sage: P.intervals_poset() Finite poset containing 1 elements
sage: P = Poset({0:[], 1:[]}) sage: P.intervals_poset().is_isomorphic(P) True """ FiniteLatticePoset) else:
if self.le(aa, b)])
def relations_iterator(self, strict=False): r""" Return an iterator for all the relations of the poset.
A relation is a pair of elements `x` and `y` such that `x \leq y` in the poset.
INPUT:
- ``strict`` -- a boolean (default ``False``) if ``True``, returns an iterator over relations `x < y`, excluding all relations `x \leq x`.
OUTPUT:
A generator that produces pairs (each pair is a list), where the first element of the pair is less than or equal to the second element.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: it = P.relations_iterator() sage: type(it) <... 'generator'> sage: next(it), next(it) ([1, 1], [1, 2])
sage: P = posets.PentagonPoset() sage: list(P.relations_iterator(strict=True)) [[0, 1], [0, 2], [0, 4], [0, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
.. SEEALSO::
:meth:`relations_number`, :meth:`relations`.
AUTHOR:
- Rob Beezer (2011-05-04) """ else:
intervals_iterator = deprecated_function_alias(19360, relations_iterator)
def relations_number(self): """ Return the number of relations in the poset.
A relation is a pair of elements `x` and `y` such that `x\leq y` in the poset.
Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.
EXAMPLES::
sage: P = posets.PentagonPoset() sage: P.relations_number() 13
sage: from sage.combinat.tamari_lattices import TamariLattice sage: TamariLattice(4).relations_number() 68
.. SEEALSO::
:meth:`relations_iterator`, :meth:`relations`
TESTS::
sage: Poset().relations_number() 0 """
# Maybe this should also be deprecated. intervals_number = relations_number
def is_incomparable_chain_free(self, m, n=None): r""" Return ``True`` if the poset is `(m+n)`-free, and ``False`` otherwise.
A poset is `(m+n)`-free if there is no incomparable chains of lengths `m` and `n`. Three cases have special name (see [EnumComb1]_, exercise 3.15):
- ''interval order'' is `(2+2)`-free - ''semiorder'' (or ''unit interval order'') is `(1+3)`-free and `(2+2)`-free - ''weak order'' is `(1+2)`-free.
INPUT:
- ``m``, ``n`` - positive integers
It is also possible to give a list of integer pairs as argument. See below for an example.
EXAMPLES::
sage: B3 = posets.BooleanLattice(3) sage: B3.is_incomparable_chain_free(1, 3) True sage: B3.is_incomparable_chain_free(2, 2) False
sage: IP6 = posets.IntegerPartitions(6) sage: IP6.is_incomparable_chain_free(1, 3) False sage: IP6.is_incomparable_chain_free(2, 2) True
A list of pairs as an argument::
sage: B3.is_incomparable_chain_free([[1, 3], [2, 2]]) False
We show how to get an incomparable chain pair::
sage: P = posets.PentagonPoset() sage: chains_1_2 = Poset({0:[], 1:[2]}) sage: incomps = P.isomorphic_subposets(chains_1_2)[0] sage: sorted(incomps.list()), incomps.cover_relations() ([1, 2, 3], [[2, 3]])
TESTS::
sage: Poset().is_incomparable_chain_free(1,1) # Test empty poset True
sage: [len([p for p in Posets(n) if p.is_incomparable_chain_free(((3, 1), (2, 2)))]) for n in range(6)] # long time [1, 1, 2, 5, 14, 42]
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: Q.is_incomparable_chain_free(2, 20/10) True sage: Q.is_incomparable_chain_free(2, pi) Traceback (most recent call last): ... TypeError: 2 and pi must be integers. sage: Q.is_incomparable_chain_free(2, -1) Traceback (most recent call last): ... ValueError: 2 and -1 must be positive integers. sage: P = Poset(((0, 1, 2, 3, 4), ((0, 1), (1, 2), (0, 3), (4, 2)))) sage: P.is_incomparable_chain_free((3, 1)) Traceback (most recent call last): ... TypeError: (3, 1) is not a tuple of tuples. sage: P.is_incomparable_chain_free([3, 1], [2, 2]) Traceback (most recent call last): ... TypeError: [3, 1] and [2, 2] must be integers. sage: P.is_incomparable_chain_free([[3, 1], [2, 2]]) True sage: P.is_incomparable_chain_free(([3, 1], [2, 2])) True sage: P.is_incomparable_chain_free([3, 1], 2) Traceback (most recent call last): ... TypeError: [3, 1] and 2 must be integers. sage: P.is_incomparable_chain_free(([3, 1], [2, 2, 2])) Traceback (most recent call last): ... ValueError: '([3, 1], [2, 2, 2])' is not a tuple of length-2 tuples.
AUTHOR:
- Eric Rowland (2013-05-28) """ else:
def is_lequal(self, x, y): """ Return ``True`` if `x` is less than or equal to `y` in the poset, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.is_lequal(2, 4) True sage: P.is_lequal(2, 2) True sage: P.is_lequal(0, 1) False sage: P.is_lequal(3, 2) False
.. SEEALSO:: :meth:`is_less_than`, :meth:`is_gequal`. """
le = is_lequal
def is_less_than(self, x, y): """ Return ``True`` if `x` is less than but not equal to `y` in the poset, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.is_less_than(1, 3) True sage: P.is_less_than(0, 1) False sage: P.is_less_than(2, 2) False
For non-facade posets also ``<`` works::
sage: P = Poset({3: [1, 2]}, facade=False) sage: P(1) < P(2) False
.. SEEALSO:: :meth:`is_lequal`, :meth:`is_greater_than`. """
lt = is_less_than
def is_gequal(self, x, y): """ Return ``True`` if `x` is greater than or equal to `y` in the poset, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.is_gequal(3, 1) True sage: P.is_gequal(2, 2) True sage: P.is_gequal(0, 1) False
.. SEEALSO:: :meth:`is_greater_than`, :meth:`is_lequal`. """
ge = is_gequal
def is_greater_than(self, x, y): """ Return ``True`` if `x` is greater than but not equal to `y` in the poset, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.is_greater_than(3, 1) True sage: P.is_greater_than(1, 2) False sage: P.is_greater_than(3, 3) False sage: P.is_greater_than(0, 1) False
For non-facade posets also ``>`` works::
sage: P = Poset({3: [1, 2]}, facade=False) sage: P(2) > P(3) True
.. SEEALSO:: :meth:`is_gequal`, :meth:`is_less_than`. """
gt = is_greater_than
def compare_elements(self, x, y): r""" Compare `x` and `y` in the poset.
- If `x < y`, return ``-1``. - If `x = y`, return ``0``. - If `x > y`, return ``1``. - If `x` and `y` are not comparable, return ``None``.
EXAMPLES::
sage: P = Poset([[1, 2], [4], [3], [4], []]) sage: P.compare_elements(0, 0) 0 sage: P.compare_elements(0, 4) -1 sage: P.compare_elements(4, 0) 1 sage: P.compare_elements(1, 2) is None True """ else:
def minimal_elements(self): """ Return the list of the minimal elements of the poset.
EXAMPLES::
sage: P = Poset({0:[3],1:[3],2:[3],3:[4],4:[]}) sage: P(0) in P.minimal_elements() True sage: P(1) in P.minimal_elements() True sage: P(2) in P.minimal_elements() True
.. SEEALSO:: :meth:`maximal_elements`. """
def maximal_elements(self): """ Return the list of the maximal elements of the poset.
EXAMPLES::
sage: P = Poset({0:[3],1:[3],2:[3],3:[4],4:[]}) sage: P.maximal_elements() [4]
.. SEEALSO:: :meth:`minimal_elements`. """
def bottom(self): """ Return the unique minimal element of the poset, if it exists.
EXAMPLES::
sage: P = Poset({0:[3],1:[3],2:[3],3:[4],4:[]}) sage: P.bottom() is None True sage: Q = Poset({0:[1],1:[]}) sage: Q.bottom() 0
.. SEEALSO:: :meth:`has_bottom`, :meth:`top` """ else:
def has_bottom(self): """ Return ``True`` if the poset has a unique minimal element, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[3], 1:[3], 2:[3], 3:[4], 4:[]}) sage: P.has_bottom() False sage: Q = Poset({0:[1], 1:[]}) sage: Q.has_bottom() True
.. SEEALSO::
- Dual Property: :meth:`has_top` - Stronger properties: :meth:`is_bounded` - Other: :meth:`bottom`
TESTS::
sage: Poset().has_top() # Test empty poset False """
def top(self): """ Return the unique maximal element of the poset, if it exists.
EXAMPLES::
sage: P = Poset({0:[3],1:[3],2:[3],3:[4,5],4:[],5:[]}) sage: P.top() is None True sage: Q = Poset({0:[1],1:[]}) sage: Q.top() 1
.. SEEALSO:: :meth:`has_top`, :meth:`bottom`
TESTS::
sage: R = Poset([[0],[]]) sage: R.list() [0] sage: R.top() #Trac #10776 0 """ else:
def has_top(self): """ Return ``True`` if the poset has a unique maximal element, and ``False`` otherwise.
EXAMPLES::
sage: P = Poset({0:[3], 1:[3], 2:[3], 3:[4, 5], 4:[], 5:[]}) sage: P.has_top() False sage: Q = Poset({0:[3], 1:[3], 2:[3], 3:[4], 4:[]}) sage: Q.has_top() True
.. SEEALSO::
- Dual Property: :meth:`has_bottom` - Stronger properties: :meth:`is_bounded` - Other: :meth:`top`
TESTS::
sage: Poset().has_top() # Test empty poset False """
def height(self, certificate=False): """ Return the height (number of elements in a longest chain) of the poset.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return ``(h, c)``, where ``h`` is the height and ``c`` is a chain of maximum cardinality. If ``certificate=False`` return only the height.
EXAMPLES::
sage: P = Poset({0: [1], 2: [3, 4], 4: [5, 6]}) sage: P.height() 3 sage: posets.PentagonPoset().height(certificate=True) (4, [0, 2, 3, 4])
TESTS::
sage: Poset().height() 0 """
return (0, [])
def has_isomorphic_subposet(self, other): """ Return ``True`` if the poset contains a subposet isomorphic to ``other``.
By subposet we mean that there exist a set ``X`` of elements such that ``self.subposet(X)`` is isomorphic to ``other``.
INPUT:
- ``other`` -- a finite poset
EXAMPLES::
sage: D = Poset({1:[2,3], 2:[4], 3:[4]}) sage: T = Poset({1:[2,3], 2:[4,5], 3:[6,7]}) sage: N5 = posets.PentagonPoset()
sage: N5.has_isomorphic_subposet(T) False sage: N5.has_isomorphic_subposet(D) True
sage: len([P for P in Posets(5) if P.has_isomorphic_subposet(D)]) 11
""" raise TypeError("'other' is not a finite poset")
def is_bounded(self): """ Return ``True`` if the poset is bounded, and ``False`` otherwise.
A poset is bounded if it contains both a unique maximal element and a unique minimal element.
EXAMPLES::
sage: P = Poset({0:[3], 1:[3], 2:[3], 3:[4, 5], 4:[], 5:[]}) sage: P.is_bounded() False sage: Q = posets.DiamondPoset(5) sage: Q.is_bounded() True
.. SEEALSO::
- Weaker properties: :meth:`has_bottom`, :meth:`has_top` - Other: :meth:`with_bounds`, :meth:`without_bounds`
TESTS::
sage: Poset().is_bounded() # Test empty poset False sage: Poset({1:[]}).is_bounded() # Here top == bottom True sage: ( len([P for P in Posets(5) if P.is_bounded()]) == ....: Posets(3).cardinality() ) True """
def is_chain(self): """ Return ``True`` if the poset is totally ordered ("chain"), and ``False`` otherwise.
EXAMPLES::
sage: I = Poset({0:[1], 1:[2], 2:[3], 3:[4]}) sage: I.is_chain() True
sage: II = Poset({0:[1], 2:[3]}) sage: II.is_chain() False
sage: V = Poset({0:[1, 2]}) sage: V.is_chain() False
TESTS::
sage: [len([P for P in Posets(n) if P.is_chain()]) for n in range(5)] [1, 1, 1, 1, 1] """
def is_chain_of_poset(self, elms, ordered=False): """ Return ``True`` if ``elms`` is a chain of the poset, and ``False`` otherwise.
Set of elements are a *chain* of a poset if they are comparable to each other.
INPUT:
- ``elms`` -- a list or other iterable containing some elements of the poset
- ``ordered`` -- a Boolean. If ``True``, then return ``True`` only if elements in `elms` are strictly increasing in the poset; this makes no sense if `elms` is a set. If ``False`` (the default), then elements can be repeated and be in any order.
EXAMPLES::
sage: P = Poset((divisors(12), attrcall("divides"))) sage: sorted(P.list()) [1, 2, 3, 4, 6, 12] sage: P.is_chain_of_poset([12, 3]) True sage: P.is_chain_of_poset({3, 4, 12}) False sage: P.is_chain_of_poset([12, 3], ordered=True) False sage: P.is_chain_of_poset((1, 1, 3)) True sage: P.is_chain_of_poset((1, 1, 3), ordered=True) False sage: P.is_chain_of_poset((1, 3), ordered=True) True
TESTS::
sage: P = posets.BooleanLattice(4) sage: P.is_chain_of_poset([]) True sage: P.is_chain_of_poset((1,3,7,15,14)) False sage: P.is_chain_of_poset({10}) True sage: P.is_chain_of_poset([32]) Traceback (most recent call last): ... ValueError: element (=32) not in poset """ else: # _element_to_vertex can be assumed to be a linear extension # of the poset according to the documentation of class # HasseDiagram.
def is_antichain_of_poset(self, elms): """ Return ``True`` if ``elms`` is an antichain of the poset and ``False`` otherwise.
Set of elements are an *antichain* of a poset if they are pairwise incomparable.
EXAMPLES::
sage: P = posets.BooleanLattice(5) sage: P.is_antichain_of_poset([3, 5, 7]) False sage: P.is_antichain_of_poset([3, 5, 14]) True
TESTS::
sage: P = posets.PentagonPoset() sage: P.is_antichain_of_poset([]) True sage: P.is_antichain_of_poset([0]) True sage: P.is_antichain_of_poset([1, 2, 1]) True
Check :trac:`19078`::
sage: P.is_antichain_of_poset([0, 1, 'junk']) Traceback (most recent call last): ... ValueError: element (=junk) not in poset """
def is_connected(self): """ Return ``True`` if the poset is connected, and ``False`` otherwise.
A poset is connected if it's Hasse diagram is connected.
If a poset is not connected, then it can be divided to parts `S_1` and `S_2` so that every element of `S_1` is incomparable to every element of `S_2`.
EXAMPLES::
sage: P = Poset({1:[2, 3], 3:[4, 5]}) sage: P.is_connected() True
sage: P = Poset({1:[2, 3], 3:[4, 5], 6:[7, 8]}) sage: P.is_connected() False
.. SEEALSO:: :meth:`connected_components`
TESTS::
sage: Poset().is_connected() # Test empty poset True """
def is_series_parallel(self): """ Return ``True`` if the poset is series-parallel, and ``False`` otherwise.
A poset is *series-parallel* if it can be built up from one-element posets using the operations of disjoint union and ordinal sum. This is also called *N-free* property: every poset that is not series-parallel contains a subposet isomorphic to the 4-element N-shaped poset where `a > c, d` and `b > d`.
.. NOTE::
Some papers use the term N-free for posets having no N-shaped poset as a *cover-preserving subposet*. This definition is not used here.
See :wikipedia:`Series-parallel partial order`.
EXAMPLES::
sage: VA = Poset({1: [2, 3], 4: [5], 6: [5]}) sage: VA.is_series_parallel() True sage: big_N = Poset({1: [2, 4], 2: [3], 4:[7], 5:[6], 6:[7]}) sage: big_N.is_series_parallel() False
TESTS::
sage: Poset().is_series_parallel() True """ # TODO: Add series-parallel decomposition later.
def is_EL_labelling(self, f, return_raising_chains=False): r""" Return ``True`` if ``f`` is an EL labelling of ``self``.
A labelling `f` of the edges of the Hasse diagram of a poset is called an EL labelling (edge lexicographic labelling) if for any two elements `u` and `v` with `u \leq v`,
- there is a unique `f`-raising chain from `u` to `v` in the Hasse diagram, and this chain is lexicographically first among all chains from `u` to `v`.
For more details, see [Bj1980]_.
INPUT:
- ``f`` -- a function taking two elements ``a`` and ``b`` in ``self`` such that ``b`` covers ``a`` and returning elements in a totally ordered set.
- ``return_raising_chains`` (optional; default:``False``) if ``True``, returns the set of all raising chains in ``self``, if possible.
EXAMPLES:
Let us consider a Boolean poset::
sage: P = Poset([[(0,0),(0,1),(1,0),(1,1)],[[(0,0),(0,1)],[(0,0),(1,0)],[(0,1),(1,1)],[(1,0),(1,1)]]],facade=True) sage: label = lambda a,b: min( i for i in [0,1] if a[i] != b[i] ) sage: P.is_EL_labelling(label) True sage: P.is_EL_labelling(label,return_raising_chains=True) {((0, 0), (0, 1)): [1], ((0, 0), (1, 0)): [0], ((0, 0), (1, 1)): [0, 1], ((0, 1), (1, 1)): [0], ((1, 0), (1, 1)): [1]} """ return False else:
def dimension(self, certificate=False): r""" Return the dimension of the Poset.
The (Dushnik-Miller) dimension of a poset is the minimal number of total orders so that the poset can be defined as "intersection" of all of them. Mathematically said, dimension of a poset defined on a set `X` of points is the smallest integer `n` such that there exists `P_1,...,P_n` linear extensions of `P` satisfying the following property:
.. MATH::
u\leq_P v\ \text{if and only if }\ \forall i, u\leq_{P_i} v
For more information, see the :wikipedia:`Order_dimension`.
INPUT:
- ``certificate`` (boolean; default:``False``) -- whether to return an integer (the dimension) or a certificate, i.e. a smallest set of linear extensions.
.. NOTE::
The speed of this function greatly improves when more efficient MILP solvers (e.g. Gurobi, CPLEX) are installed. See :class:`MixedIntegerLinearProgram` for more information.
ALGORITHM:
As explained [FT00]_, the dimension of a poset is equal to the (weak) chromatic number of a hypergraph. More precisely:
Let `inc(P)` be the set of (ordered) pairs of incomparable elements of `P`, i.e. all `uv` and `vu` such that `u\not \leq_P v` and `v\not \leq_P u`. Any linear extension of `P` is a total order on `X` that can be seen as the union of relations from `P` along with some relations from `inc(P)`. Thus, the dimension of `P` is the smallest number of linear extensions of `P` which *cover* all points of `inc(P)`.
Consequently, `dim(P)` is equal to the chromatic number of the hypergraph `\mathcal H_{inc}`, where `\mathcal H_{inc}` is the hypergraph defined on `inc(P)` whose sets are all `S\subseteq inc(P)` such that `P\cup S` is not acyclic.
We solve this problem through a :mod:`Mixed Integer Linear Program <sage.numerical.mip>`.
EXAMPLES:
We create a poset, compute a set of linear extensions and check that we get back the poset from them::
sage: P = Poset([[1,4], [3], [4,5,3], [6], [], [6], []]) sage: P.dimension() 3 sage: L = P.dimension(certificate=True) sage: L # random -- architecture-dependent [[0, 2, 4, 5, 1, 3, 6], [2, 5, 0, 1, 3, 4, 6], [0, 1, 2, 3, 5, 6, 4]] sage: Poset( (L[0], lambda x, y: all(l.index(x) < l.index(y) for l in L)) ) == P True
According to Schnyder's theorem, the poset (of height 2) of a graph has dimension `\leq 3` if and only if the graph is planar::
sage: G = graphs.CompleteGraph(4) sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()})) sage: P.dimension() 3
sage: G = graphs.CompleteBipartiteGraph(3,3) sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()})) sage: P.dimension() # not tested - around 4s with CPLEX 4
TESTS:
Empty Poset::
sage: Poset().dimension() 0 sage: Poset().dimension(certificate=True) [] """
# Current bound on the chromatic number of the hypergraph
# cycles is the list of all cycles found during the execution of the # algorithm
r""" Initializes a LP object with k colors and the constraints from 'cycles'
sage: init_LP(1,2,3) # not tested """
# Compute a coloring of the hypergraph. If there is a problem, # increase the number of colors and start again.
# We create the digraphs of all color classes
# We check that all color classes induce an acyclic graph, and add a # constraint otherwise.
# Check that the linear extensions do generate the poset (just to be # sure)
# The only 2-cycles are the incomparable pair raise RuntimeError("Something went wrong. Please report this " "bug to sage-devel@googlegroups.com")
for l in linear_extensions]
def jump_number(self, certificate=False): """ Return the jump number of the poset.
A *jump* in a linear extension `[e_1, \ldots, e_n]` of a poset `P` is a pair `(e_i, e_{i+1})` so that `e_{i+1}` does not cover `e_i` in `P`. The jump number of a poset is the minimal number of jumps in linear extensions of a poset.
INPUT:
- ``certificate`` -- (default: ``False``) Whether to return a certificate
OUTPUT:
- If ``certificate=True`` return a pair `(n, l)` where `n` is the jump number and `l` is a linear extension with `n` jumps. If ``certificate=False`` return only the jump number.
EXAMPLES::
sage: B3 = posets.BooleanLattice(3) sage: B3.jump_number() 3
sage: N = Poset({1: [3, 4], 2: [3]}) sage: N.jump_number(certificate=True) (1, [1, 4, 2, 3])
ALGORITHM:
It is known that every poset has a greedy linear extension -- an extension `[e_1, e_2, \ldots, e_n]` where every `e_{i+1}` is an upper cover of `e_i` if that is possible -- with the smallest possible number of jumps; see [Mac1987]_.
Hence it suffices to test only those. We do that by backtracking.
The problem is proven to be NP-complete.
TESTS::
sage: E = Poset() sage: E.jump_number(certificate=True) (0, [])
sage: C4 = posets.ChainPoset(4) sage: A4 = posets.AntichainPoset(4) sage: C4.jump_number() 0 sage: A4.jump_number() 3 """ # No 'nonlocal' in Python 2. Workaround: # nonlocals[0] is the best jump number found so far, # nonlocals[1] is the linear extension giving it.
""" Recursively extend beginning of a linear extension by one element, unless we see that an extension with smaller jump number already has been found. """
# S is elements where we can grow the chain without a jump. all(low in linext for low in self.lower_covers(x))] # S is minimal elements of the poset without elements in linext not any(low in S_ for low in self.lower_covers(x))]
def rank_function(self): r""" Return the (normalized) rank function of the poset, if it exists.
A *rank function* of a poset `P` is a function `r` that maps elements of `P` to integers and satisfies: `r(x) = r(y) + 1` if `x` covers `y`. The function `r` is normalized such that its minimum value on every connected component of the Hasse diagram of `P` is `0`. This determines the function `r` uniquely (when it exists).
OUTPUT:
- a lambda function, if the poset admits a rank function - ``None``, if the poset does not admit a rank function
EXAMPLES::
sage: P = Poset(([1,2,3,4],[[1,4],[2,3],[3,4]]), facade=True) sage: P.rank_function() is not None True sage: P = Poset(([1,2,3,4,5],[[1,2],[2,3],[3,4],[1,5],[5,4]]), facade=True) sage: P.rank_function() is not None False sage: P = Poset(([1,2,3,4,5,6,7,8],[[1,4],[2,3],[3,4],[5,7],[6,7]]), facade=True) sage: f = P.rank_function(); f is not None True sage: f(5) 0 sage: f(2) 0
TESTS::
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]) sage: r = P.rank_function() sage: for u,v in P.cover_relations_iterator(): ....: if r(v) != r(u) + 1: ....: print("Bug in rank_function!")
::
sage: Q = Poset([[1,2],[4],[3],[4],[]]) sage: Q.rank_function() is None True """ else:
def rank(self, element=None): r""" Return the rank of an element ``element`` in the poset ``self``, or the rank of the poset if ``element`` is ``None``.
(The rank of a poset is the length of the longest chain of elements of the poset.)
EXAMPLES::
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False) sage: P.rank(5) 2 sage: P.rank() 3 sage: Q = Poset([[1,2],[3],[],[]])
sage: P = posets.SymmetricGroupBruhatOrderPoset(4) sage: [(v,P.rank(v)) for v in P] [('1234', 0), ('1243', 1), ... ('4312', 5), ('4321', 6)] """ else: raise ValueError("the poset is not ranked")
def is_ranked(self): r""" Return ``True`` if the poset is ranked, and ``False`` otherwise.
A poset is ranked if there is a function `r` from poset elements to integers so that `r(x)=r(y)+1` when `x` covers `y`.
Informally said a ranked poset can be "levelized": every element is on a "level", and every cover relation goes only one level up.
EXAMPLES::
sage: P = Poset( ([1, 2, 3, 4], [[1, 2], [2, 4], [3, 4]] )) sage: P.is_ranked() True
sage: P = Poset([[1, 5], [2, 6], [3], [4],[], [6, 3], [4]]) sage: P.is_ranked() False
.. SEEALSO:: :meth:`rank_function`, :meth:`rank`, :meth:`is_graded`
TESTS::
sage: Poset().is_ranked() # Test empty poset True """
def is_graded(self): r""" Return ``True`` if the poset is graded, and ``False`` otherwise.
A poset is graded if all its maximal chains have the same length.
There are various competing definitions for graded posets (see :wikipedia:`Graded_poset`). This definition is from section 3.1 of Richard Stanley's *Enumerative Combinatorics, Vol. 1* [EnumComb1]_.
Every graded poset is ranked. The converse is true for bounded posets, including lattices.
EXAMPLES::
sage: P = posets.PentagonPoset() # Not even ranked sage: P.is_graded() False
sage: P = Poset({1:[2, 3], 3:[4]}) # Ranked, but not graded sage: P.is_graded() False
sage: P = Poset({1:[3, 4], 2:[3, 4], 5:[6]}) sage: P.is_graded() True
sage: P = Poset([[1], [2], [], [4], []]) sage: P.is_graded() False
.. SEEALSO:: :meth:`is_ranked`, :meth:`level_sets`
TESTS::
sage: Poset().is_graded() # Test empty poset True """ # Let's work with the Hasse diagram in order to avoid some # indirection (the output doesn't depend on the vertex labels). return False
def covers(self, x, y): """ Return ``True`` if ``y`` covers ``x`` and ``False`` otherwise.
Element `y` covers `x` if `x < y` and there is no `z` such that `x < z < y`.
EXAMPLES::
sage: P = Poset([[1,5], [2,6], [3], [4], [], [6,3], [4]]) sage: P.covers(1, 6) True sage: P.covers(1, 4) False sage: P.covers(1, 5) False """
def upper_covers_iterator(self, x): """ Return an iterator over the upper covers of the element ``x``.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[]}) sage: type(P.upper_covers_iterator(0)) <... 'generator'> """
def upper_covers(self, x): """ Return the list of upper covers of the element ``x``.
An upper cover of `x` is an element `y` such that `x < y` and there is no element `z` so that `x < z < y`.
EXAMPLES::
sage: P = Poset([[1,5], [2,6], [3], [4], [], [6,3], [4]]) sage: P.upper_covers(1) [2, 6]
.. SEEALSO:: :meth:`lower_covers` """
def lower_covers_iterator(self, x): """ Return an iterator over the lower covers of the element ``x``.
EXAMPLES::
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[]}) sage: l0 = P.lower_covers_iterator(3) sage: type(l0) <... 'generator'> sage: next(l0) 2 """
def lower_covers(self, x): """ Return the list of lower covers of the element ``x``.
A lower cover of `x` is an element `y` such that `y < x` and there is no element `z` so that `y < z < x`.
EXAMPLES::
sage: P = Poset([[1,5], [2,6], [3], [4], [], [6,3], [4]]) sage: P.lower_covers(3) [2, 5] sage: P.lower_covers(0) []
.. SEEALSO:: :meth:`upper_covers` """
def cardinality(self): """ Return the number of elements in the poset.
EXAMPLES::
sage: Poset([[1,2,3],[4],[4],[4],[]]).cardinality() 5
.. SEEALSO::
:meth:`degree_polynomial` for a more refined invariant """
def moebius_function(self,x,y): r""" Returns the value of the Möbius function of the poset on the elements x and y.
EXAMPLES::
sage: P = Poset([[1,2,3],[4],[4],[4],[]]) sage: P.moebius_function(P(0),P(4)) 2 sage: sum([P.moebius_function(P(0),v) for v in P]) 0 sage: sum([abs(P.moebius_function(P(0),v)) \ ....: for v in P]) 6 sage: for u,v in P.cover_relations_iterator(): ....: if P.moebius_function(u,v) != -1: ....: print("Bug in moebius_function!")
::
sage: Q = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]) sage: Q.moebius_function(Q(0),Q(7)) 0 sage: Q.moebius_function(Q(0),Q(5)) 0 sage: Q.moebius_function(Q(2),Q(7)) 2 sage: Q.moebius_function(Q(3),Q(3)) 1 sage: sum([Q.moebius_function(Q(0),v) for v in Q]) 0 """ mobius_function = deprecated_function_alias(19855, moebius_function)
def moebius_function_matrix(self, ring = ZZ, sparse = False): r""" Returns a matrix whose ``(i,j)`` entry is the value of the Möbius function evaluated at ``self.linear_extension()[i]`` and ``self.linear_extension()[j]``.
INPUT:
- ``ring`` -- the ring of coefficients (default: ``ZZ``) - ``sparse`` -- whether the returned matrix is sparse or not (default: ``True``)
EXAMPLES::
sage: P = Poset([[4,2,3],[],[1],[1],[1]]) sage: x,y = (P.linear_extension()[0],P.linear_extension()[1]) sage: P.moebius_function(x,y) -1 sage: M = P.moebius_function_matrix(); M [ 1 -1 -1 -1 2] [ 0 1 0 0 -1] [ 0 0 1 0 -1] [ 0 0 0 1 -1] [ 0 0 0 0 1] sage: M[0,4] 2 sage: M[0,1] -1
We now demonstrate the usage of the optional parameters::
sage: P.moebius_function_matrix(ring=QQ, sparse=False).parent() Full MatrixSpace of 5 by 5 dense matrices over Rational Field """ mobius_function_matrix = deprecated_function_alias(19855, moebius_function_matrix)
def lequal_matrix(self, ring = ZZ, sparse = False): """ Computes the matrix whose ``(i,j)`` entry is 1 if ``self.linear_extension()[i] < self.linear_extension()[j]`` and 0 otherwise.
INPUT:
- ``ring`` -- the ring of coefficients (default: ``ZZ``) - ``sparse`` -- whether the returned matrix is sparse or not (default: ``True``)
EXAMPLES::
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False) sage: LEQM = P.lequal_matrix(); LEQM [1 1 1 1 1 1 1 1] [0 1 0 1 0 0 0 1] [0 0 1 1 1 0 1 1] [0 0 0 1 0 0 0 1] [0 0 0 0 1 0 0 1] [0 0 0 0 0 1 1 1] [0 0 0 0 0 0 1 1] [0 0 0 0 0 0 0 1] sage: LEQM[1,3] 1 sage: P.linear_extension()[1] < P.linear_extension()[3] True sage: LEQM[2,5] 0 sage: P.linear_extension()[2] < P.linear_extension()[5] False
We now demonstrate the usage of the optional parameters::
sage: P.lequal_matrix(ring=QQ, sparse=False).parent() Full MatrixSpace of 8 by 8 dense matrices over Rational Field """
def coxeter_transformation(self): r""" Return the Coxeter transformation of the poset.
OUTPUT:
a square matrix with integer coefficients
The output is the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules on the poset, in the basis of simple modules. This matrix is usually called the Coxeter transformation.
EXAMPLES::
sage: posets.PentagonPoset().coxeter_transformation() [ 0 0 0 0 -1] [ 0 0 0 1 -1] [ 0 1 0 0 -1] [-1 1 1 0 -1] [-1 1 0 1 -1]
.. SEEALSO::
:meth:`coxeter_polynomial`
TESTS::
sage: M = posets.PentagonPoset().coxeter_transformation() sage: M ** 8 == 1 True """
def coxeter_polynomial(self): """ Return the Coxeter polynomial of the poset.
OUTPUT:
a polynomial in one variable
The output is the characteristic polynomial of the Coxeter transformation. This polynomial only depends on the derived category of modules on the poset.
EXAMPLES::
sage: P = posets.PentagonPoset() sage: P.coxeter_polynomial() x^5 + x^4 + x + 1
sage: p = posets.SymmetricGroupWeakOrderPoset(3) sage: p.coxeter_polynomial() x^6 + x^5 - x^3 + x + 1
.. SEEALSO::
:meth:`coxeter_transformation` """
def is_meet_semilattice(self, certificate=False): r""" Return ``True`` if the poset has a meet operation, and ``False`` otherwise.
A meet is the greatest lower bound for given elements, if it exists.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return either ``(True, None)`` or ``(False, (a, b))`` where elements `a` and `b` have no greatest lower bound. If ``certificate=False`` return ``True`` or ``False``.
EXAMPLES::
sage: P = Poset({1:[2, 3, 4], 2:[5, 6], 3:[6], 4:[6, 7]}) sage: P.is_meet_semilattice() True
sage: Q = P.dual() sage: Q.is_meet_semilattice() False
sage: V = posets.IntegerPartitions(5) sage: V.is_meet_semilattice(certificate=True) (False, ((2, 2, 1), (3, 1, 1)))
.. SEEALSO::
- Dual property: :meth:`is_join_semilattice` - Stronger properties: :meth:`~sage.categories.finite_posets.FinitePosets.ParentMethods.is_lattice`
TESTS::
sage: Poset().is_meet_semilattice() # Test empty lattice True sage: len([P for P in Posets(4) if P.is_meet_semilattice()]) 5
sage: P = Poset({1: [2], 3: []}) sage: P.is_meet_semilattice(certificate=True) (False, (3, 1)) """ return False raise i += 1 return (True, None)
def is_join_semilattice(self, certificate=False): """ Return ``True`` if the poset has a join operation, and ``False`` otherwise.
A join is the least upper bound for given elements, if it exists.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return either ``(True, None)`` or ``(False, (a, b))`` where elements `a` and `b` have no least upper bound. If ``certificate=False`` return ``True`` or ``False``.
EXAMPLES::
sage: P = Poset([[1,3,2], [4], [4,5,6], [6], [7], [7], [7], []]) sage: P.is_join_semilattice() True
sage: P = Poset({1:[3, 4], 2:[3, 4], 3:[5], 4:[5]}) sage: P.is_join_semilattice() False sage: P.is_join_semilattice(certificate=True) (False, (2, 1))
.. SEEALSO::
- Dual property: :meth:`is_meet_semilattice` - Stronger properties: :meth:`~sage.categories.finite_posets.FinitePosets.ParentMethods.is_lattice`
TESTS::
sage: Poset().is_join_semilattice() # Test empty lattice True sage: len([P for P in Posets(4) if P.is_join_semilattice()]) 5
sage: X = Poset({1: [3], 2: [3], 3: [4, 5]}) sage: X.is_join_semilattice(certificate=True) (False, (5, 4)) """ raise i -= 1 return (True, None)
def is_isomorphic(self, other): """ Returns True if both posets are isomorphic.
EXAMPLES::
sage: P = Poset(([1,2,3],[[1,3],[2,3]])) sage: Q = Poset(([4,5,6],[[4,6],[5,6]])) sage: P.is_isomorphic( Q ) True """ else: raise TypeError("'other' is not a finite poset")
def isomorphic_subposets_iterator(self, other): """ Return an iterator over the subposets of `self` isomorphic to `other`.
By subposet we mean ``self.subposet(X)`` which is isomorphic to ``other`` and where ``X`` is a subset of elements of ``self``.
INPUT:
- ``other`` -- a finite poset
EXAMPLES::
sage: D = Poset({1:[2,3], 2:[4], 3:[4]}) sage: N5 = posets.PentagonPoset() sage: for P in N5.isomorphic_subposets_iterator(D): ....: print(P.cover_relations()) [[0, 1], [0, 2], [1, 4], [2, 4]] [[0, 1], [0, 3], [1, 4], [3, 4]] [[0, 1], [0, 2], [1, 4], [2, 4]] [[0, 1], [0, 3], [1, 4], [3, 4]]
.. WARNING::
This function will return same subposet as many times as there are automorphism on it. This is due to :meth:`~sage.graphs.generic_graph.GenericGraph.subgraph_search_iterator` returning labelled subgraphs. On the other hand, this function does not eat memory like :meth:`isomorphic_subposets` does.
.. SEEALSO::
:meth:`sage.combinat.posets.lattices.FiniteLatticePoset.isomorphic_sublattices_iterator`. """ raise TypeError("'other' is not a finite poset")
def isomorphic_subposets(self, other): """ Return a list of subposets of `self` isomorphic to `other`.
By subposet we mean ``self.subposet(X)`` which is isomorphic to ``other`` and where ``X`` is a subset of elements of ``self``.
INPUT:
- ``other`` -- a finite poset
EXAMPLES::
sage: C2=Poset({0:[1]}) sage: C3=Poset({'a':['b'], 'b':['c']}) sage: for x in C3.isomorphic_subposets(C2): ....: print(x.cover_relations()) [['b', 'c']] [['a', 'c']] [['a', 'b']] sage: D = Poset({1:[2,3], 2:[4], 3:[4]}) sage: N5 = posets.PentagonPoset() sage: len(N5.isomorphic_subposets(D)) 2
.. NOTE::
If this function takes too much time, try using :meth:`isomorphic_subposets_iterator`. """
raise TypeError("'other' is not a finite poset") # Since subgraph_search_iterator returns labelled copies, we # remove duplicates.
from six.moves import builtins # Caveat: list is overridden by the method list above!!!
def antichains(self, element_constructor = builtins.list): """ Return the antichains of the poset.
An *antichain* of a poset is a set of elements of the poset that are pairwise incomparable.
INPUT:
- ``element_constructor`` -- a function taking an iterable as argument (default: ``list``)
OUTPUT:
The enumerated set (of type :class:`~sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets`) of all antichains of the poset, each of which is given as an ``element_constructor.``
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]] sage: A.cardinality() 8 sage: A[3] [1, 2]
To get the antichains as, say, sets, one may use the ``element_constructor`` option::
sage: list(posets.ChainPoset(3).antichains(element_constructor=set)) [set(), {0}, {1}, {2}]
To get the antichains of a given size one can currently use::
sage: list(A.elements_of_depth_iterator(2)) [[1, 2], [1, 3]]
Eventually the following syntax will be accepted::
sage: A.subset(size = 2) # todo: not implemented
.. NOTE::
Internally, this uses :class:`sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets` and :class:`SearchForest`. At this point, iterating through this set is about twice slower than using :meth:`antichains_iterator` (tested on ``posets.AntichainPoset(15)``). The algorithm is the same (depth first search through the tree), but :meth:`antichains_iterator` manually inlines things which apparently avoids some infrastructure overhead.
On the other hand, this returns a full featured enumerated set, with containment testing, etc.
.. SEEALSO:: :meth:`maximal_antichains`, :meth:`chains` """
def antichains_iterator(self): """ Return an iterator over the antichains of the poset.
EXAMPLES::
sage: it = posets.PentagonPoset().antichains_iterator(); it <generator object antichains_iterator at ...> sage: next(it), next(it) ([], [4])
.. SEEALSO:: :meth:`antichains` """
def width(self, certificate=False): r""" Return the width of the poset (the size of its longest antichain).
It is computed through a matching in a bipartite graph; see :wikipedia:`Dilworth's_theorem` for more information. The width is also called Dilworth number.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return ``(w, a)``, where `w` is the width of a poset and `a` is an antichain of maximum cardinality. If ``certificate=False`` return only width of the poset.
EXAMPLES::
sage: P = posets.BooleanLattice(4) sage: P.width() 6
sage: w, max_achain = P.width(certificate=True) sage: sorted(max_achain) [3, 5, 6, 9, 10, 12]
TESTS::
sage: Poset().width() 0 sage: Poset().width(certificate=True) (0, []) """
# See the doc of dilworth_decomposition for an explanation of what is # going on.
def dilworth_decomposition(self): r""" Return a partition of the points into the minimal number of chains.
According to Dilworth's theorem, the points of a poset can be partitioned into `\alpha` chains, where `\alpha` is the cardinality of its largest antichain. This method returns such a partition.
See :wikipedia:`Dilworth's_theorem`.
ALGORITHM:
We build a bipartite graph in which a vertex `v` of the poset is represented by two vertices `v^-,v^+`. For any two `u,v` such that `u<v` in the poset we add an edge `v^+u^-`.
A matching in this graph is equivalent to a partition of the poset into chains: indeed, a chain `v_1...v_k` gives rise to the matching `v_1^+v_2^-,v_2^+v_3^-,...`, and from a matching one can build the union of chains.
According to Dilworth's theorem, the number of chains is equal to `\alpha` (the posets' width).
EXAMPLES::
sage: p = posets.BooleanLattice(4) sage: p.width() 6 sage: p.dilworth_decomposition() # random [[7, 6, 4], [11, 3], [12, 8, 0], [13, 9, 1], [14, 10, 2], [15, 5]]
.. SEEALSO::
:meth:`level_sets` to return elements grouped to antichains.
TESTS::
sage: p = posets.IntegerCompositions(5) sage: d = p.dilworth_decomposition() sage: for chain in d: ....: for i in range(len(chain)-1): ....: assert p.is_greater_than(chain[i],chain[i+1]) sage: set(p) == set().union(*d) True """ # v is the top element of its chain
def chains(self, element_constructor=builtins.list, exclude=None): """ Return the chains of the poset.
A *chain* of a poset is a set of elements of the poset that are pairwise comparable.
INPUT:
- ``element_constructor`` -- a function taking an iterable as argument (default: ``list``)
- ``exclude`` -- elements of the poset to be excluded (default: ``None``)
OUTPUT:
The enumerated set (of type :class:`~sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets`) of all chains of the poset, each of which is given as an ``element_constructor``.
EXAMPLES::
sage: C = posets.PentagonPoset().chains(); C Set of chains of Finite lattice containing 5 elements sage: list(C) [[], [0], [0, 1], [0, 1, 4], [0, 2], [0, 2, 3], [0, 2, 3, 4], [0, 2, 4], [0, 3], [0, 3, 4], [0, 4], [1], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
Exclusion of elements, tuple (instead of list) as constructor::
sage: P = Poset({1: [2, 3], 2: [4], 3: [4, 5]}) sage: list(P.chains(element_constructor=tuple, exclude=[3])) [(), (1,), (1, 2), (1, 2, 4), (1, 4), (1, 5), (2,), (2, 4), (4,), (5,)]
To get the chains of a given size one can currently use::
sage: list(C.elements_of_depth_iterator(2)) [[0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 4]]
Eventually the following syntax will be accepted::
sage: C.subset(size = 2) # todo: not implemented
.. SEEALSO:: :meth:`maximal_chains`, :meth:`antichains` """
exclude=exclude)
def connected_components(self): """ Return the connected components of the poset as subposets.
EXAMPLES::
sage: P = Poset({1: [2, 3], 3: [4, 5], 6: [7, 8]}) sage: parts = sorted(P.connected_components(), key=len); parts [Finite poset containing 3 elements, Finite poset containing 5 elements] sage: parts[0].cover_relations() [[6, 7], [6, 8]]
.. SEEALSO:: :meth:`disjoint_union`, :meth:`is_connected`
TESTS::
sage: Poset().connected_components() # Test empty poset []
sage: P = Poset({1: [2, 3], 3: [4, 5]}) sage: CC = P.connected_components() sage: CC[0] is P True
sage: P = Poset({1: [2, 3], 3: [4, 5], 6: [7, 8]}, facade=False) sage: V = sorted(P.connected_components(), key=len)[0] sage: V(7) < V(8) # Facade argument should be inherited False """ for cc in comps]
def ordinal_summands(self): r""" Return the ordinal summands of the poset as subposets.
The ordinal summands of a poset `P` is the longest list of non-empty subposets `P_1, \ldots, P_n` whose ordinal sum is `P`. This decomposition is unique.
EXAMPLES::
sage: P = Poset({'a': ['c', 'd'], 'b': ['d'], 'c': ['x', 'y'], ....: 'd': ['x', 'y']}) sage: parts = P.ordinal_summands(); parts [Finite poset containing 4 elements, Finite poset containing 2 elements] sage: sorted(parts[0]) ['a', 'b', 'c', 'd'] sage: Q = parts[0].ordinal_sum(parts[1]) sage: Q.is_isomorphic(P) True
.. SEEALSO::
:meth:`ordinal_sum`
ALGORITHM:
Suppose that a poset `P` is the ordinal sum of posets `L` and `U`. Then `P` contains maximal antichains `l` and `u` such that every element of `u` covers every element of `l`; they correspond to maximal elements of `L` and minimal elements of `U`.
We consider a linear extension `x_1,\ldots,x_n` of the poset's elements.
We keep track of the maximal elements of subposet induced by elements `0,\ldots,x_i` and minimal elements of subposet induced by elements `x_{i+1},\ldots,x_n`, incrementing `i` one by one. We then check if `l` and `u` fit the previous description.
TESTS::
sage: Poset().ordinal_summands() [Finite poset containing 0 elements] sage: Poset({1: []}).ordinal_summands() [Finite poset containing 1 elements] """
# update 'lower' by adding 'e' to it
# update 'upper' too
else: break else:
for e in range(i+1,j+1)]))
def product(self, other): """ Return the Cartesian product of the poset with ``other``.
The Cartesian (or 'direct') product of `P` and `Q` is defined by `(p, q) \le (p', q')` iff `p \le p'` in `P` and `q \le q'` in `Q`.
Product of (semi)lattices are returned as a (semi)lattice.
EXAMPLES::
sage: P = posets.ChainPoset(3) sage: Q = posets.ChainPoset(4) sage: PQ = P.product(Q) ; PQ Finite lattice containing 12 elements sage: len(PQ.cover_relations()) 17 sage: Q.product(P).is_isomorphic(PQ) True
sage: P = posets.BooleanLattice(2) sage: Q = P.product(P) sage: Q.is_isomorphic(posets.BooleanLattice(4)) True
One can also simply use `*`::
sage: P = posets.ChainPoset(2) sage: Q = posets.ChainPoset(3) sage: P*Q Finite lattice containing 6 elements
.. SEEALSO::
:class:`~sage.combinat.posets.cartesian_product.CartesianProductPoset`
TESTS::
sage: Poset({0: [1]}).product(Poset()) # Product with empty poset Finite poset containing 0 elements sage: Poset().product(Poset()) # Product of two empty poset Finite poset containing 0 elements
We check that :trac:`19113` is fixed::
sage: L = LatticePoset({1: []}) sage: type(L) == type(L.product(L)) True """ JoinSemilattice, MeetSemilattice, FiniteLatticePoset, \ FiniteMeetSemilattice, FiniteJoinSemilattice isinstance(other, FiniteLatticePoset) ): isinstance(other, FiniteMeetSemilattice) ): constructor = MeetSemilattice isinstance(other, FiniteJoinSemilattice) ): constructor = JoinSemilattice else:
_mul_ = product
def disjoint_union(self, other, labels='pairs'): """ Return a poset isomorphic to disjoint union (also called direct sum) of the poset with ``other``.
The disjoint union of `P` and `Q` is a poset that contains every element and relation from both `P` and `Q`, and where every element of `P` is incomparable to every element of `Q`.
Mathematically, it is only defined when `P` and `Q` have no common element; here we force that by giving them different names in the resulting poset.
INPUT:
- ``other``, a poset.
- ``labels`` - (defaults to 'pairs') If set to 'pairs', each element ``v`` in this poset will be named ``(0,v)`` and each element ``u`` in ``other`` will be named ``(1,u)`` in the result. If set to 'integers', the elements of the result will be relabeled with consecutive integers.
EXAMPLES::
sage: P1 = Poset({'a': 'b'}) sage: P2 = Poset({'c': 'd'}) sage: P = P1.disjoint_union(P2); P Finite poset containing 4 elements sage: sorted(P.cover_relations()) [[(0, 'a'), (0, 'b')], [(1, 'c'), (1, 'd')]] sage: P = P1.disjoint_union(P2, labels='integers'); sage: P.cover_relations() [[2, 3], [0, 1]]
sage: N5 = posets.PentagonPoset(); N5 Finite lattice containing 5 elements sage: N5.disjoint_union(N5) # Union of lattices is not a lattice Finite poset containing 10 elements
We show how to get literally direct sum with elements untouched::
sage: P = P1.disjoint_union(P2).relabel(lambda x: x[1]) sage: sorted(P.cover_relations()) [['a', 'b'], ['c', 'd']]
.. SEEALSO:: :meth:`connected_components`
TESTS::
sage: N5 = posets.PentagonPoset() sage: P0 = Poset() sage: N5.disjoint_union(P0).is_isomorphic(N5) True sage: P0.disjoint_union(P0) Finite poset containing 0 elements
sage: A3 = posets.AntichainPoset(3) sage: A4 = posets.AntichainPoset(4) sage: A7 = posets.AntichainPoset(7) sage: A3.disjoint_union(A4).is_isomorphic(A7) True """ raise TypeError("'other' is not a finite poset") labels=labels))
def ordinal_product(self, other, labels='pairs'): """ Return the ordinal product of ``self`` and ``other``.
The ordinal product of two posets `P` and `Q` is a partial order on the Cartesian product of the underlying sets of `P` and `Q`, defined as follows (see [EnumComb1]_, p. 284).
In the ordinal product, `(p,q) \leq (p',q')` if either `p \leq p'` or `p = p'` and `q \leq q'`.
This construction is not symmetric in `P` and `Q`. Informally said we put a copy of `Q` in place of every element of `P`.
INPUT:
- ``other`` -- a poset
- ``labels`` -- either ``'integers'`` or ``'pairs'`` (default); how the resulting poset will be labeled
EXAMPLES::
sage: P1 = Poset((['a', 'b'], [['a', 'b']])) sage: P2 = Poset((['c', 'd'], [['c', 'd']])) sage: P = P1.ordinal_product(P2); P Finite poset containing 4 elements sage: sorted(P.cover_relations()) [[('a', 'c'), ('a', 'd')], [('a', 'd'), ('b', 'c')], [('b', 'c'), ('b', 'd')]]
.. SEEALSO::
:meth:`product`, :meth:`ordinal_sum`
TESTS::
sage: P1.ordinal_product(24) Traceback (most recent call last): ... TypeError: 'other' is not a finite poset sage: P1.ordinal_product(P2, labels='camembert') Traceback (most recent call last): ... ValueError: labels must be either 'pairs' or 'integers'
sage: N5 = posets.PentagonPoset() sage: P0 = Poset() sage: N5.ordinal_product(P0) == P0 True sage: P0.ordinal_product(N5) == P0 True sage: P0.ordinal_product(P0) == P0 True
sage: A3 = posets.AntichainPoset(3) sage: A4 = posets.AntichainPoset(4) sage: A12 = posets.AntichainPoset(12) sage: A3.ordinal_product(A4).is_isomorphic(A12) True
sage: C3 = posets.ChainPoset(3) sage: C4 = posets.ChainPoset(4) sage: C12 = posets.ChainPoset(12) sage: C3.ordinal_product(C4).is_isomorphic(C12) True """ FiniteLatticePoset
for s, s2 in self.cover_relations_iterator() for t in othermax for t2 in othermin]) for s in self for t, t2 in other.cover_relations_iterator()]) dg.relabel()
isinstance(other, FiniteLatticePoset)):
def ordinal_sum(self, other, labels='pairs'): """ Return a poset or (semi)lattice isomorphic to ordinal sum of the poset with ``other``.
The ordinal sum of `P` and `Q` is a poset that contains every element and relation from both `P` and `Q`, and where every element of `P` is smaller than any element of `Q`.
Mathematically, it is only defined when `P` and `Q` have no common element; here we force that by giving them different names in the resulting poset.
The ordinal sum on lattices is a lattice; resp. for meet- and join-semilattices.
INPUT:
- ``other``, a poset.
- ``labels`` - (defaults to 'pairs') If set to 'pairs', each element ``v`` in this poset will be named ``(0,v)`` and each element ``u`` in ``other`` will be named ``(1,u)`` in the result. If set to 'integers', the elements of the result will be relabeled with consecutive integers.
EXAMPLES::
sage: P1 = Poset( ([1, 2, 3, 4], [[1, 2], [1, 3], [1, 4]]) ) sage: P2 = Poset( ([1, 2, 3,], [[2,1], [3,1]]) ) sage: P3 = P1.ordinal_sum(P2); P3 Finite poset containing 7 elements sage: len(P1.maximal_elements())*len(P2.minimal_elements()) 6 sage: len(P1.cover_relations()+P2.cover_relations()) 5 sage: len(P3.cover_relations()) # Every element of P2 is greater than elements of P1. 11 sage: P3.list() # random [(0, 1), (0, 2), (0, 4), (0, 3), (1, 2), (1, 3), (1, 1)] sage: P4 = P1.ordinal_sum(P2, labels='integers') sage: P4.list() # random [0, 1, 2, 3, 5, 6, 4]
Return type depends on input types::
sage: P = Poset({1:[2]}); P Finite poset containing 2 elements sage: JL = JoinSemilattice({1:[2]}); JL Finite join-semilattice containing 2 elements sage: L = LatticePoset({1:[2]}); L Finite lattice containing 2 elements sage: P.ordinal_sum(L) Finite poset containing 4 elements sage: L.ordinal_sum(JL) Finite join-semilattice containing 4 elements sage: L.ordinal_sum(L) Finite lattice containing 4 elements
.. SEEALSO::
:meth:`ordinal_summands`, :meth:`disjoint_union`, :meth:`sage.combinat.posets.lattices.FiniteLatticePoset.vertical_composition`
TESTS::
sage: N5 = posets.PentagonPoset() sage: P0 = LatticePoset({}) sage: N5.ordinal_sum(P0).is_isomorphic(N5) True sage: P0.ordinal_sum(P0) Finite lattice containing 0 elements """ JoinSemilattice, MeetSemilattice, FiniteLatticePoset, \ FiniteMeetSemilattice, FiniteJoinSemilattice
raise TypeError("'other' is not a finite poset") raise ValueError("labels must be either 'pairs' or 'integers'")
isinstance(other, FiniteLatticePoset)): isinstance(other, FiniteMeetSemilattice)): return MeetSemilattice(G) isinstance(other, FiniteJoinSemilattice)):
def star_product(self, other, labels='pairs'): """ Return a poset isomorphic to the star product of the poset with ``other``.
Both this poset and ``other`` are expected to be bounded and have at least two elements.
Let `P` be a poset with top element `\\top_P` and `Q` be a poset with bottom element `\\bot_Q`. The star product of `P` and `Q` is the ordinal sum of `P \setminus \\top_P` and `Q \setminus \\bot_Q`.
Mathematically, it is only defined when `P` and `Q` have no common elements; here we force that by giving them different names in the resulting poset.
INPUT:
- ``other`` -- a poset.
- ``labels`` -- (defaults to 'pairs') If set to 'pairs', each element ``v`` in this poset will be named ``(0, v)`` and each element ``u`` in ``other`` will be named ``(1, u)`` in the result. If set to 'integers', the elements of the result will be relabeled with consecutive integers.
EXAMPLES:
This is mostly used to combine two Eulerian posets to third one, and makes sense for graded posets only::
sage: B2 = posets.BooleanLattice(2) sage: B3 = posets.BooleanLattice(3) sage: P = B2.star_product(B3); P Finite poset containing 10 elements sage: P.is_eulerian() True
We can get elements as pairs or as integers::
sage: ABC = Poset({'a': ['b'], 'b': ['c']}) sage: XYZ = Poset({'x': ['y'], 'y': ['z']}) sage: ABC.star_product(XYZ).list() [(0, 'a'), (0, 'b'), (1, 'y'), (1, 'z')] sage: ABC.star_product(XYZ, labels='integers').list() [0, 1, 2, 3]
TESTS::
sage: C0 = Poset() sage: C1 = Poset({0: []}) sage: C2 = Poset({0: [1]}) sage: C2.star_product(42) Traceback (most recent call last): ... TypeError: 'other' is not a finite poset sage: C2.star_product(C0) Traceback (most recent call last): ... ValueError: 'other' is not bounded sage: C0.star_product(C2) Traceback (most recent call last): ... ValueError: the poset is not bounded sage: C2.star_product(C1) Traceback (most recent call last): ... ValueError: 'other' has less than two elements sage: C1.star_product(C2) Traceback (most recent call last): ... ValueError: the poset has less than two elements """ raise ValueError("labels must be either 'pairs' or 'integers'")
def dual(self): """ Return the dual poset of the given poset.
In the dual of a poset `P` we have `x \le y` iff `y \le x` in `P`.
EXAMPLES::
sage: P = Poset({1: [2, 3], 3: [4]}) sage: P.cover_relations() [[1, 2], [1, 3], [3, 4]] sage: Q = P.dual() sage: Q.cover_relations() [[4, 3], [3, 1], [2, 1]]
Dual of a lattice is a lattice; dual of a meet-semilattice is join-semilattice and vice versa. Also the dual of a (non-)facade poset is again (non-)facade::
sage: V = MeetSemilattice({1: [2, 3]}, facade=False) sage: A = V.dual(); A Finite join-semilattice containing 3 elements sage: A(2) < A(1) True
.. SEEALSO:: :meth:`~sage.categories.finite_posets.FinitePosets.ParentMethods.is_self_dual`
TESTS::
sage: Poset().dual() == Poset() # Test the empty poset True """ elements = reversed(self._elements) else: inplace=False) elements=elements, category=self.category(), facade=self._is_facade)
def with_bounds(self, labels=('bottom', 'top')): r""" Return the poset with bottom and top elements adjoined.
This functions always adds two new elements to the poset, i.e. it does not check if the poset already has a bottom or a top element.
For lattices and semilattices this function returns a lattice.
INPUT:
- ``labels`` -- A pair of elements to use as a bottom and top element of the poset. Default is strings ``'bottom'`` and ``'top'``. Either of them can be ``None``, and then a new bottom or top element will not be added.
EXAMPLES::
sage: V = Poset({0: [1, 2]}) sage: trafficsign = V.with_bounds(); trafficsign Finite poset containing 5 elements sage: trafficsign.list() ['bottom', 0, 1, 2, 'top'] sage: trafficsign = V.with_bounds(labels=(-1, -2)) sage: trafficsign.cover_relations() [[-1, 0], [0, 1], [0, 2], [1, -2], [2, -2]]
sage: Y = V.with_bounds(labels=(-1, None)) sage: Y.cover_relations() [[-1, 0], [0, 1], [0, 2]]
sage: P = posets.PentagonPoset() # A lattice sage: P.with_bounds() Finite lattice containing 7 elements
.. SEEALSO::
:meth:`without_bounds` for the reverse operation
TESTS::
sage: P = Poset().with_bounds() sage: P.cover_relations() [['bottom', 'top']]
sage: L = LatticePoset({}).with_bounds(); L Finite lattice containing 2 elements sage: L.meet_irreducibles() # Trac 21543 ['bottom']
sage: Poset().with_bounds((None, 1)) Finite poset containing 1 elements sage: LatticePoset().with_bounds((None, 1)) Finite lattice containing 1 elements sage: MeetSemilattice().with_bounds((None, 1)) Finite lattice containing 1 elements sage: JoinSemilattice().with_bounds((None, 1)) Finite join-semilattice containing 1 elements sage: Poset().with_bounds((1, None)) Finite poset containing 1 elements sage: LatticePoset().with_bounds((1, None)) Finite lattice containing 1 elements sage: MeetSemilattice().with_bounds((1, None)) Finite meet-semilattice containing 1 elements sage: JoinSemilattice().with_bounds((1, None)) Finite lattice containing 1 elements
sage: P = Poset({0: []}) sage: L = LatticePoset({0: []}) sage: ML = MeetSemilattice({0: []}) sage: JL = JoinSemilattice({0: []}) sage: P.with_bounds((None, None)) Finite poset containing 1 elements sage: L.with_bounds((None, None)) Finite lattice containing 1 elements sage: ML.with_bounds((None, None)) Finite meet-semilattice containing 1 elements sage: JL.with_bounds((None, None)) Finite join-semilattice containing 1 elements sage: P.with_bounds((1, None)) Finite poset containing 2 elements sage: L.with_bounds((1, None)) Finite lattice containing 2 elements sage: ML.with_bounds((1, None)) Finite meet-semilattice containing 2 elements sage: JL.with_bounds((1, None)) Finite lattice containing 2 elements sage: P.with_bounds((None, 1)) Finite poset containing 2 elements sage: L.with_bounds((None, 1)) Finite lattice containing 2 elements sage: ML.with_bounds((None, 1)) Finite lattice containing 2 elements sage: JL.with_bounds((None, 1)) Finite join-semilattice containing 2 elements
sage: posets.PentagonPoset().with_bounds(labels=(4, 5)) Traceback (most recent call last): ... ValueError: the poset already has element 4 """ # TODO: Fix this to work with non-facade posets also raise NotImplementedError("the function is not defined on non-facade posets")
raise TypeError("labels must be a pair") raise ValueError("the poset already has element %s" % new_max)
JoinSemilattice, MeetSemilattice, FiniteLatticePoset, \ FiniteMeetSemilattice, FiniteJoinSemilattice (isinstance(self, FiniteMeetSemilattice) and new_max is not None) or (isinstance(self, FiniteJoinSemilattice) and new_min is not None) ): else:
return constructor()
def without_bounds(self): """ Return the poset without its top and bottom elements.
This is useful as an input for the method :meth:`order_complex`.
If there is either no top or no bottom element, this raises a ``TypeError``.
EXAMPLES::
sage: P = posets.PentagonPoset() sage: Q = P.without_bounds(); Q Finite poset containing 3 elements sage: Q.cover_relations() [[2, 3]]
sage: P = posets.DiamondPoset(5) sage: Q = P.without_bounds(); Q Finite poset containing 3 elements sage: Q.cover_relations() []
.. SEEALSO::
:meth:`with_bounds` for the reverse operation
TESTS::
sage: P = Poset({1:[2],3:[2,4]}) sage: P.without_bounds() Traceback (most recent call last): ... TypeError: the poset is missing either top or bottom
sage: P = Poset({1:[]}) sage: P.without_bounds() Finite poset containing 0 elements
sage: P = Poset({}) sage: P.without_bounds() Traceback (most recent call last): ... TypeError: the poset is missing either top or bottom """
def relabel(self, relabeling=None): r""" Return a copy of this poset with its elements relabeled.
INPUT:
- ``relabeling`` -- a function, dictionary, list or tuple
The given function or dictionary must map each (non-wrapped) element of ``self`` to some distinct object. The given list or tuple must be made of distinct objects.
When the input is a list or a tuple, the relabeling uses the total ordering of the elements of the poset given by ``list(self)``.
If no relabeling is given, the poset is relabeled by integers from `0` to `n-1` according to one of its linear extensions. This means that `i<j` as integers whenever `i<j` in the relabeled poset.
EXAMPLES:
Relabeling using a function::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: P.cover_relations() [[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]] sage: Q = P.relabel(lambda x: x+1) sage: Q.list() [2, 3, 4, 5, 7, 13] sage: Q.cover_relations() [[2, 3], [2, 4], [3, 5], [3, 7], [4, 7], [5, 13], [7, 13]]
Relabeling using a dictionary::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True, facade=False) sage: relabeling = {c.element:i for (i,c) in enumerate(P)} sage: relabeling {1: 0, 2: 1, 3: 2, 4: 3, 6: 4, 12: 5} sage: Q = P.relabel(relabeling) sage: Q.list() [0, 1, 2, 3, 4, 5] sage: Q.cover_relations() [[0, 1], [0, 2], [1, 3], [1, 4], [2, 4], [3, 5], [4, 5]]
Mind the ``c.element``; this is because the relabeling is applied to the elements of the poset without the wrapping. Thanks to this convention, the same relabeling function can be used both for facade or non facade posets.
Relabeling using a list::
sage: P = posets.PentagonPoset() sage: list(P) [0, 1, 2, 3, 4] sage: P.cover_relations() [[0, 1], [0, 2], [1, 4], [2, 3], [3, 4]] sage: Q = P.relabel(list('abcde')) sage: Q.cover_relations() [['a', 'b'], ['a', 'c'], ['b', 'e'], ['c', 'd'], ['d', 'e']]
Default behaviour is increasing relabeling::
sage: a2 = posets.ChainPoset(2) sage: P = a2 * a2 sage: Q = P.relabel() sage: Q.cover_relations() [[0, 1], [0, 2], [1, 3], [2, 3]]
Relabeling a (semi)lattice gives a (semi)lattice::
sage: P = JoinSemilattice({0: [1]}) sage: P.relabel(lambda n: n+1) Finite join-semilattice containing 2 elements
.. NOTE::
As can be seen in the above examples, the default linear extension of ``Q`` is that of ``P`` after relabeling. In particular, ``P`` and ``Q`` share the same internal Hasse diagram.
TESTS:
Test non-facade poset::
sage: P = Poset({3: [2]}, facade=False) sage: Q = P.relabel(lambda x: chr(ord('a')+x)) sage: Q('c') < Q('d') False
The following checks that :trac:`14019` has been fixed::
sage: d = DiGraph({2:[1],3:[1]}) sage: p1 = Poset(d) sage: p2 = p1.relabel({1:1,2:3,3:2}) sage: p1.hasse_diagram() == p2.hasse_diagram() True sage: p1 == p2 True
sage: d = DiGraph({2:[1],3:[1]}) sage: p1 = Poset(d) sage: p2 = p1.relabel({1:2,2:3,3:1}) sage: p3 = p2.relabel({2:1,1:2,3:3}) sage: p1.hasse_diagram() == p3.hasse_diagram() True sage: p1 == p3 True """ JoinSemilattice, MeetSemilattice, FiniteLatticePoset, FiniteMeetSemilattice, FiniteJoinSemilattice)
else:
facade=self._is_facade)
for i in range(len(self._elements))} else: for i, x in enumerate(self._elements)}
else: for x in self._elements)
inplace=False), elements=elements, category=self.category(), facade=self._is_facade)
def canonical_label(self, algorithm=None): """ Return the unique poset on the labels `\{0, \ldots, n-1\}` (where `n` is the number of elements in the poset) that is isomorphic to this poset and invariant in the isomorphism class.
INPUT:
- ``algorithm`` -- string (optional); a parameter forwarded to underlying graph function to select the algorithm to use
EXAMPLES::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: Q = P.canonical_label() sage: sorted(Q.list()) [0, 1, 2, 3, 4, 5] sage: Q.is_isomorphic(P) True
Canonical labeling of (semi)lattice returns (semi)lattice::
sage: D = DiGraph({'a':['b','c']}) sage: P = Poset(D) sage: ML = MeetSemilattice(D) sage: P.canonical_label() Finite poset containing 3 elements sage: ML.canonical_label() Finite meet-semilattice containing 3 elements
.. SEEALSO::
- Canonical labeling of directed graphs: :meth:`~sage.graphs.generic_graph.GenericGraph.canonical_label()`
TESTS::
sage: P = Poset(digraphs.Path(10), linear_extension=True) sage: Q = P.canonical_label() sage: Q.linear_extension() # random [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: Q.cover_relations() # random [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9]] sage: P = Poset(digraphs.Path(10)) sage: Q = P.canonical_label() sage: Q.linear_extension() # random [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: Q.is_isomorphic(P) True
sage: Poset().canonical_label() # Test the empty poset Finite poset containing 0 elements
sage: D2 = posets.DiamondPoset(4).canonical_label(algorithm='bliss') # optional: bliss sage: B2 = posets.BooleanLattice(2).canonical_label(algorithm='bliss') # optional: bliss sage: D2 == B2 # optional: bliss True """ algorithm=algorithm)[1]
def with_linear_extension(self, linear_extension): """ Return a copy of ``self`` with a different default linear extension.
EXAMPLES::
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True) sage: P.cover_relations() [[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]] sage: list(P) [1, 2, 3, 4, 6, 12] sage: Q = P.with_linear_extension([1,3,2,6,4,12]) sage: list(Q) [1, 3, 2, 6, 4, 12] sage: Q.cover_relations() [[1, 3], [1, 2], [3, 6], [2, 6], [2, 4], [6, 12], [4, 12]]
TESTS:
We check that we can pass in a list of elements of ``P`` instead::
sage: Q = P.with_linear_extension([P(_) for _ in [1,3,2,6,4,12]]) sage: list(Q) [1, 3, 2, 6, 4, 12] sage: Q.cover_relations() [[1, 3], [1, 2], [3, 6], [2, 6], [2, 4], [6, 12], [4, 12]]
We check that this works for facade posets too::
sage: P = Poset((divisors(12), attrcall("divides")), facade=True) sage: Q = P.with_linear_extension([1,3,2,6,4,12]); Q Finite poset containing 6 elements with distinguished linear extension sage: list(Q) [1, 3, 2, 6, 4, 12] sage: Q.cover_relations() [[1, 3], [1, 2], [3, 6], [2, 6], [2, 4], [6, 12], [4, 12]] sage: sorted(Q.cover_relations()) == sorted(P.cover_relations()) True
(Semi)lattice remains (semi)lattice with new linear extension::
sage: L = LatticePoset(P) sage: Q = L.with_linear_extension([1,3,2,6,4,12]); Q Finite lattice containing 6 elements with distinguished linear extension
.. NOTE::
With the current implementation, this requires relabeling the internal :class:`DiGraph` which is `O(n+m)`, where `n` is the number of elements and `m` the number of cover relations. """ # Hack to get the actual class, not the categorified class elements=linear_extension, category=self.category(), facade=self._is_facade)
def graphviz_string(self,graph_string="graph",edge_string="--"): r""" Returns a representation in the DOT language, ready to render in graphviz.
See http://www.graphviz.org/doc/info/lang.html for more information about graphviz.
EXAMPLES::
sage: P = Poset({'a':['b'],'b':['d'],'c':['d'],'d':['f'],'e':['f'],'f':[]}) sage: print(P.graphviz_string()) graph { "f";"d";"b";"a";"c";"e"; "f"--"e";"d"--"c";"b"--"a";"d"--"b";"f"--"d"; } """
def subposet(self, elements): """ Return the poset containing given elements with partial order induced by this poset.
EXAMPLES::
sage: P = Poset({'a': ['c', 'd'], 'b': ['d','e'], 'c': ['f'], ....: 'd': ['f'], 'e': ['f']}) sage: Q = P.subposet(['a', 'b', 'f']); Q Finite poset containing 3 elements sage: Q.cover_relations() [['b', 'f'], ['a', 'f']]
A subposet of a non-facade poset is again a non-facade poset::
sage: P = posets.PentagonPoset(facade=False) sage: Q = P.subposet([0, 1, 2, 4]) sage: Q(1) < Q(2) False
TESTS::
sage: P = Poset({'a': ['b'], 'b': ['c']}) sage: P.subposet(('a', 'b', 'c')) Finite poset containing 3 elements sage: P.subposet([]) Finite poset containing 0 elements sage: P.subposet(["a","b","x"]) Traceback (most recent call last): ... ValueError: <... 'str'> is not an element of this poset sage: P.subposet(3) Traceback (most recent call last): ... TypeError: 'sage.rings.integer.Integer' object is not iterable """ # Type checking is performed by the following line:
def random_subposet(self, p): """ Return a random subposet that contains each element with probability ``p``.
EXAMPLES::
sage: P = posets.BooleanLattice(3) sage: set_random_seed(0) # Results are reproducible sage: Q = P.random_subposet(0.5) sage: Q.cover_relations() [[0, 2], [0, 5], [2, 3], [3, 7], [5, 7]]
TESTS::
sage: P = posets.IntegerPartitions(4) sage: P.random_subposet(1) == P True """ raise ValueError("probability p must be in [0..1]")
def random_order_ideal(self, direction='down'): """ Return a random order ideal with uniform probability.
INPUT:
- ``direction`` -- ``'up'``, ``'down'`` or ``'antichain'`` (default: ``'down'``)
OUTPUT:
A randomly selected order ideal (or order filter if ``direction='up'``, or antichain if ``direction='antichain'``) where all order ideals have equal probability of occurring.
ALGORITHM:
Uses the coupling from the past algorithm described in [Propp1997]_.
EXAMPLES::
sage: P = posets.BooleanLattice(3) sage: P.random_order_ideal() [0, 1, 2, 3, 4, 5, 6] sage: P.random_order_ideal(direction='up') [6, 7] sage: P.random_order_ideal(direction='antichain') [1, 2]
sage: P = posets.TamariLattice(5) sage: a = P.random_order_ideal('antichain') sage: P.is_antichain_of_poset(a) True sage: a = P.random_order_ideal('up') sage: P.is_order_filter(a) True sage: a = P.random_order_ideal('down') sage: P.is_order_ideal(a) True """ # states are 0 -- in order ideal # 1 -- not in order ideal 2 -- undecided else: if x == 0 and all(state[j] == 1 for j in hd.upper_covers_iterator(i))] raise ValueError("direction must be 'up', 'down' or 'antichain'")
def order_filter(self, elements): """ Return the order filter generated by the elements of an iterable ``elements``.
`I` is 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 upper set or upset.
EXAMPLES::
sage: P = Poset((divisors(1000), attrcall("divides"))) sage: P.order_filter([20, 25]) [20, 40, 25, 50, 100, 200, 125, 250, 500, 1000]
.. SEEALSO::
:meth:`order_ideal`, :meth:`~sage.categories.posets.Posets.ParentMethods.principal_order_filter`.
TESTS::
sage: P = Poset() # Test empty poset sage: P.order_filter([]) [] sage: C = posets.ChainPoset(5) sage: C.order_filter([]) [] """
def order_ideal(self, elements): """ Return the order ideal generated by the elements of an iterable ``elements``.
`I` is 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 lower set or downset.
EXAMPLES::
sage: P = Poset((divisors(1000), attrcall("divides"))) sage: P.order_ideal([20, 25]) [1, 2, 4, 5, 10, 20, 25]
.. SEEALSO::
:meth:`order_filter`, :meth:`~sage.categories.posets.Posets.ParentMethods.principal_order_ideal`.
TESTS::
sage: P = Poset() # Test empty poset sage: P.order_ideal([]) [] sage: C = posets.ChainPoset(5) sage: C.order_ideal([]) [] """
def interval(self, x, y): """ Return a list of the elements `z` such that `x \le z \le y`.
INPUT:
- ``x`` -- any element of the poset
- ``y`` -- any element of the poset
EXAMPLES::
sage: uc = [[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]] sage: dag = DiGraph(dict(zip(range(len(uc)),uc))) sage: P = Poset(dag) sage: I = set(map(P,[2,5,6,4,7])) sage: I == set(P.interval(2,7)) True
::
sage: dg = DiGraph({"a":["b","c"], "b":["d"], "c":["d"]}) sage: P = Poset(dg, facade = False) sage: P.interval("a","d") [a, b, c, d] """ self._element_to_vertex(x),self._element_to_vertex(y))]
def closed_interval(self, x, y): """ Return the list of elements `z` such that `x \le z \le y` in the poset.
EXAMPLES::
sage: P = Poset((divisors(1000), attrcall("divides"))) sage: P.closed_interval(2, 100) [2, 4, 10, 20, 50, 100]
.. SEEALSO::
:meth:`open_interval`
TESTS::
sage: C = posets.ChainPoset(10) sage: C.closed_interval(3, 3) [3] sage: C.closed_interval(8, 5) [] sage: A = posets.AntichainPoset(10) sage: A.closed_interval(3, 7) [] """ self._element_to_vertex(x),self._element_to_vertex(y))]
def open_interval(self, x, y): """ Return the list of elements `z` such that `x < z < y` in the poset.
EXAMPLES::
sage: P = Poset((divisors(1000), attrcall("divides"))) sage: P.open_interval(2, 100) [4, 10, 20, 50]
.. SEEALSO::
:meth:`closed_interval`
TESTS::
sage: C = posets.ChainPoset(10) sage: C.open_interval(3, 3) [] sage: C.open_interval(3, 4) [] sage: C.open_interval(7, 3) [] sage: A = posets.AntichainPoset(10) sage: A.open_interval(3, 7) [] """ self._element_to_vertex(x),self._element_to_vertex(y))]
def comparability_graph(self): r""" Return the comparability graph of the poset.
The comparability graph is an undirected graph where vertices are the elements of the poset and there is an edge between two vertices if they are comparable in the poset.
See :wikipedia:`Comparability_graph`
EXAMPLES::
sage: Y = Poset({1: [2], 2: [3, 4]}) sage: g = Y.comparability_graph(); g Comparability graph on 4 vertices sage: Y.compare_elements(1, 3) is not None True sage: g.has_edge(1, 3) True
.. SEEALSO:: :meth:`incomparability_graph`, :mod:`sage.graphs.comparability`
TESTS::
sage: Poset().comparability_graph() Comparability graph on 0 vertices
sage: C4 = posets.ChainPoset(4) sage: C4.comparability_graph().is_isomorphic(graphs.CompleteGraph(4)) True
sage: A4 = posets.AntichainPoset(4) sage: A4.comparability_graph().is_isomorphic(Graph(4)) True """
def incomparability_graph(self): r""" Return the incomparability graph of the poset.
This is the complement of the comparability graph, i.e. an undirected graph where vertices are the elements of the poset and there is an edge between vertices if they are not comparable in the poset.
EXAMPLES::
sage: Y = Poset({1: [2], 2: [3, 4]}) sage: g = Y.incomparability_graph(); g Incomparability graph on 4 vertices sage: Y.compare_elements(1, 3) is not None True sage: g.has_edge(1, 3) False
.. SEEALSO:: :meth:`comparability_graph`
TESTS::
sage: Poset().incomparability_graph() Incomparability graph on 0 vertices
sage: C4 = posets.ChainPoset(4) sage: C4.incomparability_graph().is_isomorphic(Graph(4)) True
sage: A4 = posets.AntichainPoset(4) sage: A4.incomparability_graph().is_isomorphic(graphs.CompleteGraph(4)) True """
def linear_extensions_graph(self): r""" Return the linear extensions graph of the poset.
Vertices of the graph are linear extensions of the poset. Two vertices are connected by an edge if the linear extensions differ by only one adjacent transposition.
EXAMPLES::
sage: N = Poset({1: [3, 4], 2: [4]}) sage: G = N.linear_extensions_graph(); G Graph on 5 vertices sage: G.neighbors(N.linear_extension([1,2,3,4])) [[2, 1, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4]]
sage: chevron = Poset({1: [2, 6], 2: [3], 4: [3, 5], 6: [5]}) sage: G = chevron.linear_extensions_graph(); G Graph on 22 vertices sage: G.size() 36
TESTS::
sage: Poset().linear_extensions_graph() Graph on 1 vertex
sage: A4 = posets.AntichainPoset(4) sage: G = A4.linear_extensions_graph() sage: G.is_regular() True """ # Direct implementation, no optimizations
def maximal_antichains(self): """ Return the maximal antichains of the poset.
An antichain `a` of poset `P` is *maximal* if there is no element `e \in P \setminus a` such that `a \cup \{e\}` is an antichain.
EXAMPLES::
sage: P=Poset({'a':['b', 'c'], 'b':['d','e']}) sage: P.maximal_antichains() [['a'], ['b', 'c'], ['c', 'd', 'e']]
sage: posets.PentagonPoset().maximal_antichains() [[0], [1, 2], [1, 3], [4]]
.. SEEALSO:: :meth:`antichains`, :meth:`maximal_chains` """ # Maximal antichains are maximum cliques on incomparability graph.
def maximal_chains(self, partial=None): """ Return all maximal chains of this poset.
Each chain is listed in increasing order.
INPUT:
- ``partial`` -- list (optional); if present, find all maximal chains starting with the elements in partial
Returns list of the maximal chains of this poset.
This is used in constructing the order complex for the poset.
EXAMPLES::
sage: P = posets.BooleanLattice(3) sage: P.maximal_chains() [[0, 1, 3, 7], [0, 1, 5, 7], [0, 2, 3, 7], [0, 2, 6, 7], [0, 4, 5, 7], [0, 4, 6, 7]] sage: P.maximal_chains(partial=[0,2]) [[0, 2, 3, 7], [0, 2, 6, 7]] sage: Q = posets.ChainPoset(6) sage: Q.maximal_chains() [[0, 1, 2, 3, 4, 5]]
.. SEEALSO:: :meth:`maximal_antichains`, :meth:`chains` """ else:
def order_complex(self, on_ints=False): """ Return the order complex associated to this poset.
The order complex is the simplicial complex with vertices equal to the elements of the poset, and faces given by the chains.
INPUT:
- ``on_ints`` -- a boolean (default: False)
OUTPUT:
an order complex of type :class:`SimplicialComplex`
EXAMPLES::
sage: P = posets.BooleanLattice(3) sage: S = P.order_complex(); S Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6, 7) and 6 facets sage: S.f_vector() [1, 8, 19, 18, 6] sage: S.homology() # S is contractible {0: 0, 1: 0, 2: 0, 3: 0} sage: Q = P.subposet([1,2,3,4,5,6]) sage: Q.order_complex().homology() # a circle {0: 0, 1: Z}
sage: P = Poset((divisors(15), attrcall("divides")), facade = True) sage: P.order_complex() Simplicial complex with vertex set (1, 3, 5, 15) and facets {(1, 3, 15), (1, 5, 15)}
If ``on_ints``, then the elements of the poset are labelled `0,1,\dots` in the chain complex::
sage: P.order_complex(on_ints=True) Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (0, 1, 3)} """
# TODO: factor out the logic for on_ints / facade / ... # We will want to do similar things elsewhere else: facets.append([a.element for a in f])
def order_polytope(self): r""" Return the order polytope of the poset ``self``.
The order polytope of a finite poset `P` is defined as the subset of `\RR^P` consisting of all maps `x : P \to \RR` satisfying
.. MATH::
0 \leq x(p) \leq 1 \mbox{ for all } p \in P,
and
.. MATH::
x(p) \leq x(q) \mbox{ for all } p, q \in P \mbox{ satisfying } p < q.
This polytope was defined and studied in [St1986]_.
EXAMPLES::
sage: P = posets.AntichainPoset(3) sage: Q = P.order_polytope();Q A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: P = posets.PentagonPoset() sage: Q = P.order_polytope();Q A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices
sage: P = Poset([[1,2,3],[[1,2],[1,3]]]) sage: Q = P.order_polytope() sage: Q.contains((1,0,0)) False sage: Q.contains((0,1,1)) True """ for u, v, w in self.hasse_diagram().edges()]
def chain_polytope(self): r""" Return the chain polytope of the poset ``self``.
The chain polytope of a finite poset `P` is defined as the subset of `\RR^P` consisting of all maps `x : P \to \RR` satisfying
.. MATH::
x(p) \geq 0 \mbox{ for all } p \in P,
and
.. MATH::
x(p_1) + x(p_2) + \ldots + x(p_k) \leq 1 \mbox{ for all chains } p_1 < p_2 < \ldots < p_k \mbox{ in } P.
This polytope was defined and studied in [St1986]_.
EXAMPLES::
sage: P = posets.AntichainPoset(3) sage: Q = P.chain_polytope();Q A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: P = posets.PentagonPoset() sage: Q = P.chain_polytope();Q A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices """ for chain in self.maximal_chains()]
def zeta_polynomial(self): r""" Return the zeta polynomial of the poset.
The zeta polynomial of a poset is the unique polynomial `Z(q)` such that for every integer `m > 1`, `Z(m)` is the number of weakly increasing sequences `x_1 \leq x_2 \leq \dots \leq x_{m-1}` of elements of the poset.
The polynomial `Z(q)` is integral-valued, but generally does not have integer coefficients. It can be computed as
.. MATH::
Z(q) = \sum_{k \geq 1} \dbinom{q-2}{k-1} c_k,
where `c_k` is the number of all chains of length `k` in the poset.
For more information, see section 3.12 of [EnumComb1]_.
In particular, `Z(2)` is the number of vertices and `Z(3)` is the number of intervals.
EXAMPLES::
sage: posets.ChainPoset(2).zeta_polynomial() q sage: posets.ChainPoset(3).zeta_polynomial() 1/2*q^2 + 1/2*q
sage: P = posets.PentagonPoset() sage: P.zeta_polynomial() 1/6*q^3 + q^2 - 1/6*q
sage: P = posets.DiamondPoset(5) sage: P.zeta_polynomial() 3/2*q^2 - 1/2*q
TESTS:
Checking the simplest cases::
sage: Poset({}).zeta_polynomial() 0 sage: Poset({1: []}).zeta_polynomial() 1 sage: Poset({1: [], 2: []}).zeta_polynomial() 2 sage: parent(_) Univariate Polynomial Ring in q over Rational Field """
def f_polynomial(self): r""" Return the `f`-polynomial of the poset.
The poset is expected to be bounded.
This is the `f`-polynomial of the order complex of the poset minus its bounds.
The coefficient of `q^i` is the number of chains of `i+1` elements containing both bounds of the poset.
.. note::
This is slightly different from the ``fPolynomial`` method in Macaulay2.
EXAMPLES::
sage: P = posets.DiamondPoset(5) sage: P.f_polynomial() 3*q^2 + q
sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [7], 6: [7]}) sage: P.f_polynomial() q^4 + 4*q^3 + 5*q^2 + q
.. SEEALSO::
:meth:`is_bounded`, :meth:`h_polynomial`, :meth:`order_complex`, :meth:`sage.homology.cell_complex.GenericCellComplex.f_vector`
TESTS::
sage: P = Poset({2: []}) sage: P.f_polynomial() 1 """ raise ValueError("the poset is not bounded")
def h_polynomial(self): r""" Return the `h`-polynomial of a bounded poset ``self``.
This is the `h`-polynomial of the order complex of the poset minus its bounds.
This is related to the `f`-polynomial by a simple change of variables:
.. MATH::
h(q) = (1-q)^{\deg f} f \left( \frac{q}{1-q} \right),
where `f` and `h` denote the `f`-polynomial and the `h`-polynomial, respectively.
See :wikipedia:`h-vector`.
.. WARNING::
This is slightly different from the ``hPolynomial`` method in Macaulay2.
EXAMPLES::
sage: P = posets.AntichainPoset(3).order_ideals_lattice() sage: P.h_polynomial() q^3 + 4*q^2 + q sage: P = posets.DiamondPoset(5) sage: P.h_polynomial() 2*q^2 + q sage: P = Poset({1: []}) sage: P.h_polynomial() 1
.. SEEALSO::
:meth:`is_bounded`, :meth:`f_polynomial`, :meth:`order_complex`, :meth:`sage.homology.simplicial_complex.SimplicialComplex.h_vector` """ raise ValueError("the poset is not bounded")
def flag_f_polynomial(self): r""" Return the flag `f`-polynomial of the poset.
The poset is expected to be bounded and ranked.
This is the sum, over all chains containing both bounds, of a monomial encoding the ranks of the elements of the chain.
More precisely, if `P` is a bounded ranked poset, then the flag `f`-polynomial of `P` is defined as the polynomial
.. MATH::
\sum_{\substack{p_0 < p_1 < \ldots < p_k, \\ p_0 = \min P, \ p_k = \max P}} x_{\rho(p_1)} x_{\rho(p_2)} \cdots x_{\rho(p_k)} \in \ZZ[x_1, x_2, \cdots, x_n]
where `\min P` and `\max P` are (respectively) the minimum and the maximum of `P`, where `\rho` is the rank function of `P` (normalized to satisfy `\rho(\min P) = 0`), and where `n` is the rank of `\max P`. (Note that the indeterminate `x_0` doesn't actually appear in the polynomial.)
For technical reasons, the polynomial is returned in the slightly larger ring `\ZZ[x_0, x_1, x_2, \cdots, x_{n+1}]` by this method.
See :wikipedia:`h-vector`.
EXAMPLES::
sage: P = posets.DiamondPoset(5) sage: P.flag_f_polynomial() 3*x1*x2 + x2
sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]}) sage: fl = P.flag_f_polynomial(); fl 2*x1*x2*x3 + 2*x1*x3 + 2*x2*x3 + x3 sage: q = polygen(ZZ,'q') sage: fl(q,q,q,q) == P.f_polynomial() True
sage: P = Poset({1: [2, 3, 4], 2: [5], 3: [5], 4: [5], 5: [6]}) sage: P.flag_f_polynomial() 3*x1*x2*x3 + 3*x1*x3 + x2*x3 + x3
.. SEEALSO:: :meth:`is_bounded`, :meth:`flag_h_polynomial`
TESTS::
sage: P = Poset({2: [3]}) sage: P.flag_f_polynomial() x1
sage: P = Poset({2: []}) sage: P.flag_f_polynomial() 1 """ raise ValueError("the poset is not bounded") raise ValueError("the poset is not ranked")
def flag_h_polynomial(self): r""" Return the flag `h`-polynomial of the poset.
The poset is expected to be bounded and ranked.
If `P` is a bounded ranked poset whose maximal element has rank `n` (where the minimal element is set to have rank `0`), then the flag `h`-polynomial of `P` is defined as the polynomial
.. MATH::
\prod_{k=1}^n (1-x_k) \cdot f \left(\frac{x_1}{1-x_1}, \frac{x_2}{1-x_2}, \cdots, \frac{x_n}{1-x_n}\right) \in \ZZ[x_1, x_2, \cdots, x_n],
where `f` is the flag `f`-polynomial of `P` (see :meth:`flag_f_polynomial`).
For technical reasons, the polynomial is returned in the slightly larger ring `\QQ[x_0, x_1, x_2, \cdots, x_{n+1}]` by this method.
See :wikipedia:`h-vector`.
EXAMPLES::
sage: P = posets.DiamondPoset(5) sage: P.flag_h_polynomial() 2*x1*x2 + x2
sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]}) sage: fl = P.flag_h_polynomial(); fl -x1*x2*x3 + x1*x3 + x2*x3 + x3 sage: q = polygen(ZZ,'q') sage: fl(q,q,q,q) == P.h_polynomial() True
sage: P = Poset({1: [2, 3, 4], 2: [5], 3: [5], 4: [5], 5: [6]}) sage: P.flag_h_polynomial() 2*x1*x3 + x3
sage: P = posets.ChainPoset(4) sage: P.flag_h_polynomial() x3
.. SEEALSO:: :meth:`is_bounded`, :meth:`flag_f_polynomial`
TESTS::
sage: P = Poset({2: [3]}) sage: P.flag_h_polynomial() x1
sage: P = Poset({2: []}) sage: P.flag_h_polynomial() 1 """ raise ValueError("the poset is not bounded") raise ValueError("the poset is not ranked") * sum(prod(x[rk(i)]/(1-x[rk(i)]) for i in ch) for ch in hasse.chains(exclude=[mini, maxi]))
def characteristic_polynomial(self): r""" Return the characteristic polynomial of the poset.
The poset is expected to be graded and have a bottom element.
If `P` is a graded poset with rank `n` and a unique minimal element `\hat{0}`, then the characteristic polynomial of `P` is defined to be
.. MATH::
\sum_{x \in P} \mu(\hat{0}, x) q^{n-\rho(x)} \in \ZZ[q],
where `\rho` is the rank function, and `\mu` is the Möbius function of `P`.
See section 3.10 of [EnumComb1]_.
EXAMPLES::
sage: P = posets.DiamondPoset(5) sage: P.characteristic_polynomial() q^2 - 3*q + 2
sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6], 6: [7]}) sage: P.characteristic_polynomial() q^4 - 2*q^3 + q
TESTS::
sage: P = Poset({1: []}) sage: P.characteristic_polynomial() 1 """ raise ValueError("the poset is not graded") raise ValueError("the poset has not a bottom element")
def chain_polynomial(self): """ Return the chain polynomial of the poset.
The coefficient of `q^k` is the number of chains of `k` elements in the poset. List of coefficients of this polynomial is also called a *f-vector* of the poset.
.. note::
This is not what has been called the chain polynomial in [St1986]_. The latter is identical with the order polynomial in SageMath (:meth:`order_polynomial`).
EXAMPLES::
sage: P = posets.ChainPoset(3) sage: t = P.chain_polynomial(); t q^3 + 3*q^2 + 3*q + 1 sage: t(1) == len(list(P.chains())) True
sage: P = posets.BooleanLattice(3) sage: P.chain_polynomial() 6*q^4 + 18*q^3 + 19*q^2 + 8*q + 1
sage: P = posets.AntichainPoset(5) sage: P.chain_polynomial() 5*q + 1
TESTS::
sage: P = Poset() sage: P.chain_polynomial() 1 sage: parent(P.chain_polynomial()) Univariate Polynomial Ring in q over Integer Ring
sage: R = Poset({1: []}) sage: R.chain_polynomial() q + 1 """ # chain_polys[i] will be the generating function for the # chains with topmost vertex i (in the labelling of the # Hasse diagram). for j in hasse.principal_order_ideal(i))
def order_polynomial(self): """ Return the order polynomial of the poset.
The order polynomial `\Omega_P(q)` of a poset `P` is defined as the unique polynomial `S` such that for each integer `m \geq 1`, `S(m)` is the number of order-preserving maps from `P` to `\{1,\ldots,m\}`.
See sections 3.12 and 3.15 of [EnumComb1]_, and also [St1986]_.
EXAMPLES::
sage: P = posets.AntichainPoset(3) sage: P.order_polynomial() q^3
sage: P = posets.ChainPoset(3) sage: f = P.order_polynomial(); f 1/6*q^3 + 1/2*q^2 + 1/3*q sage: [f(i) for i in range(4)] [0, 1, 4, 10]
.. SEEALSO:: :meth:`order_polytope` """
def degree_polynomial(self): r""" Return the generating polynomial of degrees of vertices in ``self``.
This is the sum
.. MATH::
\sum_{v \in P} x^{\operatorname{in}(v)} y^{\operatorname{out}(v)},
where ``in(v)`` and ``out(v)`` are the number of incoming and outgoing edges at vertex `v` in the Hasse diagram of `P`.
Because this polynomial is multiplicative for Cartesian product of posets, it is useful to help see if the poset can be isomorphic to a Cartesian product.
EXAMPLES::
sage: P = posets.PentagonPoset() sage: P.degree_polynomial() x^2 + 3*x*y + y^2
sage: P = posets.BooleanLattice(4) sage: P.degree_polynomial().factor() (x + y)^4
.. SEEALSO::
:meth:`cardinality` for the value at `(x, y) = (1, 1)` """
def promotion(self, i=1): r""" Compute the (extended) promotion on the linear extension of the poset ``self``.
INPUT:
- ``i`` -- an integer between `1` and `n` (default: `1`)
OUTPUT:
- an isomorphic poset, with the same default linear extension
The extended promotion is defined on a poset ``self`` of size `n` by applying the promotion operator `\tau_i \tau_{i+1} \cdots \tau_{n-1}` to the default linear extension `\pi` of ``self`` (see :meth:`~sage.combinat.posets.linear_extensions.LinearExtensionOfPoset.promotion`), and relabeling ``self`` accordingly. For more details see [Stan2009]_.
When the elements of the poset ``self`` are labelled by `\{1,2,\ldots,n\}`, the linear extension is the identity, and `i=1`, the above algorithm corresponds to the promotion operator on posets defined by Schützenberger as follows. Remove `1` from ``self`` and replace it by the minimum `j` of all labels covering `1` in the poset. Then, remove `j` and replace it by the minimum of all labels covering `j`, and so on. This process ends when a label is a local maximum. Place the label `n+1` at this vertex. Finally, decrease all labels by `1`.
EXAMPLES::
sage: P = Poset(([1,2], [[1,2]]), linear_extension=True, facade=False) sage: P.promotion() Finite poset containing 2 elements with distinguished linear extension sage: P == P.promotion() True
sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]])) sage: P.list() [1, 2, 3, 5, 6, 4, 7] sage: Q = P.promotion(4); Q Finite poset containing 7 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 6], [2, 3], [2, 5], [3, 7], [5, 7], [6, 4]]
Note that if one wants to obtain the promotion defined by Schützenberger's algorithm directly on the poset, one needs to make sure the linear extension is the identity::
sage: P = P.with_linear_extension([1,2,3,4,5,6,7]) sage: P.list() [1, 2, 3, 4, 5, 6, 7] sage: Q = P.promotion(4); Q Finite poset containing 7 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 6], [2, 3], [2, 4], [3, 5], [4, 5], [6, 7]] sage: Q = P.promotion() sage: Q.cover_relations() [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [4, 7], [5, 7]]
Here is an example for a poset not labelled by `\{1, 2, \ldots, n\}`::
sage: P = Poset((divisors(30), attrcall("divides")), linear_extension=True) sage: P.list() [1, 2, 3, 5, 6, 10, 15, 30] sage: P.cover_relations() [[1, 2], [1, 3], [1, 5], [2, 6], [2, 10], [3, 6], [3, 15], [5, 10], [5, 15], [6, 30], [10, 30], [15, 30]] sage: Q = P.promotion(4); Q Finite poset containing 8 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 3], [1, 6], [2, 5], [2, 15], [3, 5], [3, 10], [5, 30], [6, 10], [6, 15], [10, 30], [15, 30]]
.. SEEALSO::
- :meth:`linear_extension` - :meth:`with_linear_extension` and the ``linear_extension`` option of :func:`Poset` - :meth:`~sage.combinat.posets.linear_extensions.LinearExtensionOfPoset.promotion` - :meth:`evacuation`
AUTHOR:
- Anne Schilling (2012-02-18) """
def evacuation(self): r""" Compute evacuation on the linear extension associated to the poset ``self``.
OUTPUT:
- an isomorphic poset, with the same default linear extension
Evacuation is defined on a poset ``self`` of size `n` by applying the evacuation operator `(\tau_1 \cdots \tau_{n-1}) (\tau_1 \cdots \tau_{n-2}) \cdots (\tau_1)`, to the default linear extension `\pi` of ``self`` (see :meth:`~sage.combinat.posets.linear_extensions.LinearExtensionOfPoset.evacuation`), and relabeling ``self`` accordingly. For more details see [Stan2009]_.
EXAMPLES::
sage: P = Poset(([1,2], [[1,2]]), linear_extension=True, facade=False) sage: P.evacuation() Finite poset containing 2 elements with distinguished linear extension sage: P.evacuation() == P True
sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]]), linear_extension=True, facade=False) sage: P.list() [1, 2, 3, 4, 5, 6, 7] sage: Q = P.evacuation(); Q Finite poset containing 7 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 3], [2, 5], [3, 4], [3, 6], [4, 7], [6, 7]]
Note that the results depend on the linear extension associated to the poset::
sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]])) sage: P.list() [1, 2, 3, 5, 6, 4, 7] sage: Q = P.evacuation(); Q Finite poset containing 7 elements with distinguished linear extension sage: Q.cover_relations() [[1, 2], [1, 5], [2, 3], [5, 6], [5, 4], [6, 7], [4, 7]]
Here is an example of a poset where the elements are not labelled by `\{1,2,\ldots,n\}`::
sage: P = Poset((divisors(15), attrcall("divides")), linear_extension = True) sage: P.list() [1, 3, 5, 15] sage: Q = P.evacuation(); Q Finite poset containing 4 elements with distinguished linear extension sage: Q.cover_relations() [[1, 3], [1, 5], [3, 15], [5, 15]]
.. SEEALSO::
- :meth:`linear_extension` - :meth:`with_linear_extension` and the ``linear_extension`` option of :func:`Poset` - :meth:`~sage.combinat.posets.linear_extensions.LinearExtensionOfPoset.evacuation` - :meth:`promotion`
AUTHOR:
- Anne Schilling (2012-02-18) """
def is_rank_symmetric(self): """ Return ``True`` if the poset is rank symmetric, and ``False`` otherwise.
The poset is expected to be graded and connected.
A poset of rank `h` (maximal chains have `h+1` elements) is rank symmetric if the number of elements are equal in ranks `i` and `h-i` for every `i` in `0, 1, \ldots, h`.
EXAMPLES::
sage: P = Poset({1:[3, 4, 5], 2:[3, 4, 5], 3:[6], 4:[7], 5:[7]}) sage: P.is_rank_symmetric() True sage: P = Poset({1:[2], 2:[3, 4], 3:[5], 4:[5]}) sage: P.is_rank_symmetric() False
TESTS::
sage: Poset().is_rank_symmetric() # Test empty poset True """ raise ValueError("the poset is not connected") raise ValueError("the poset is not graded")
def is_slender(self, certificate=False): r""" Return ``True`` if the poset is slender, and ``False`` otherwise.
A finite graded poset is *slender* if every rank 2 interval contains three or four elements, as defined in [Stan2009]_. (This notion of "slender" is unrelated to the eponymous notion defined by Graetzer and Kelly in "The Free $\mathfrak{m}$-Lattice on the Poset $H$", Order 1 (1984), 47--65.)
This function *does not* check if the poset is graded or not. Instead it just returns ``True`` if the poset does not contain 5 distinct elements `x`, `y`, `a`, `b` and `c` such that `x \lessdot a,b,c \lessdot y` where `\lessdot` is the covering relation.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return either ``(True, None)`` or ``(False, (a, b))`` so that the interval `[a, b]` has at least five elements. If ``certificate=False`` return ``True`` or ``False``.
EXAMPLES::
sage: P = Poset(([1, 2, 3, 4], [[1, 2], [1, 3], [2, 4], [3, 4]])) sage: P.is_slender() True sage: P = Poset(([1,2,3,4,5],[[1,2],[1,3],[1,4],[2,5],[3,5],[4,5]])) sage: P.is_slender() False
sage: W = WeylGroup(['A', 2]) sage: G = W.bruhat_poset() sage: G.is_slender() True sage: W = WeylGroup(['A', 3]) sage: G = W.bruhat_poset() sage: G.is_slender() True
sage: P = posets.IntegerPartitions(6) sage: P.is_slender(certificate=True) (False, ((6,), (3, 2, 1)))
TESTS::
sage: Poset().is_slender() # Test empty poset True
Correct certificate (:trac:`22373`)::
sage: P = Poset({0:[1,2,3],1:[4],2:[4],3:[4,5]}) sage: P.is_slender(True) (False, (0, 4)) """ return (True, None)
def is_eulerian(self, k=None, certificate=False): """ Return ``True`` if the poset is Eulerian, and ``False`` otherwise.
The poset is expected to be graded and bounded.
A poset is Eulerian if every non-trivial interval has the same number of elements of even rank as of odd rank. A poset is `k`-eulerian if every non-trivial interval up to rank `k` is Eulerian.
See :wikipedia:`Eulerian_poset`.
INPUT:
- ``k``, an integer -- only check if the poset is `k`-eulerian. If ``None`` (the default), check if the poset is Eulerian. - ``certificate``, a Boolean -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return either ``True, None`` or ``False, (a, b)``, where the interval ``(a, b)`` is not Eulerian. If ``certificate=False`` return ``True`` or ``False``.
EXAMPLES::
sage: P = Poset({0: [1, 2, 3], 1: [4, 5], 2: [4, 6], 3: [5, 6], ....: 4: [7, 8], 5: [7, 8], 6: [7, 8], 7: [9], 8: [9]}) sage: P.is_eulerian() True sage: P = Poset({0: [1, 2, 3], 1: [4, 5, 6], 2: [4, 6], 3: [5,6], ....: 4: [7], 5:[7], 6:[7]}) sage: P.is_eulerian() False
Canonical examples of Eulerian posets are the face lattices of convex polytopes::
sage: P = polytopes.cube().face_lattice() sage: P.is_eulerian() True
A poset that is 3- but not 4-eulerian::
sage: P = Poset(DiGraph('MWW@_?W?@_?W??@??O@_?W?@_?W?@??O??')); P Finite poset containing 14 elements sage: P.is_eulerian(k=3) True sage: P.is_eulerian(k=4) False
Getting an interval that is not Eulerian::
sage: P = posets.DivisorLattice(12) sage: P.is_eulerian(certificate=True) (False, (1, 4))
TESTS::
sage: Poset().is_eulerian() Traceback (most recent call last): ... ValueError: the poset is not bounded
sage: Poset({1: []}).is_eulerian() True
sage: posets.PentagonPoset().is_eulerian() Traceback (most recent call last): ... ValueError: the poset is not graded
sage: posets.BooleanLattice(3).is_eulerian(k=123, certificate=True) (True, None) """ except TypeError: raise TypeError("parameter 'k' must be an integer, not {0}".format(k)) raise ValueError("parameter 'k' must be positive, not {0}".format(k))
return False
# Every 2n -eulerian poset is always also 2n+1 -eulerian. Hence # we only check for even rank intervals. See for example # Richard Ehrenborg, k-Eulerian Posets (Order 18: 227-236, 2001) # http://www.ms.uky.edu/~jrge/Papers/k-Eulerian.pdf self._vertex_to_element(j)))
def is_greedy(self, certificate=False): """ Return ``True`` if the poset is greedy, and ``False`` otherwise.
A poset is *greedy* if every greedy linear extension has the same number of jumps.
INPUT:
- ``certificate`` -- (default: ``False``) whether to return a certificate
OUTPUT:
- If ``certificate=True`` return either ``(True, None)`` or ``(False, (A, B))`` where `A` and `B` are greedy linear extension so that `B` has more jumps. If ``certificate=False`` return ``True`` or ``False``.
EXAMPLES:
This is not a self-dual property::
sage: W = Poset({1: [3, 4], 2: [4, 5]}) sage: M = W.dual() sage: W.is_greedy() True sage: M.is_greedy() False
Getting a certificate::
sage: N = Poset({1: [3], 2: [3, 4]}) sage: N.is_greedy(certificate=True) (False, ([1, 2, 4, 3], [2, 4, 1, 3]))
TESTS::
sage: Poset().is_greedy() True sage: posets.AntichainPoset(3).is_greedy() True sage: posets.ChainPoset(3).is_greedy() True """
(self.linear_extension([self[v] for v in A]), self.linear_extension([self[v] for v in B])))
def frank_network(self): r""" Return Frank's network of the poset.
This is defined in Section 8 of [BF1999]_.
OUTPUT:
A pair `(G, e)`, where `G` is Frank's network of `P` encoded as a :class:`DiGraph`, and `e` is the cost function on its edges encoded as a dictionary (indexed by these edges, which in turn are encoded as tuples of 2 vertices).
.. NOTE::
Frank's network of `P` is a certain directed graph with `2|P| + 2` vertices, defined in Section 8 of [BF1999]_. Its set of vertices consists of two vertices `(0, p)` and `(1, p)` for each element `p` of `P`, as well as two vertices `(-1, 0)` and `(2, 0)`. (These notations are not the ones used in [BF1999]_; see the table below for their relation.) The edges are:
- for each `p` in `P`, an edge from `(-1, 0)` to `(0, p)`;
- for each `p` in `P`, an edge from `(1, p)` to `(2, 0)`;
- for each `p` and `q` in `P` such that `p \geq q`, an edge from `(0, p)` to `(1, q)`.
We make this digraph into a network in the sense of flow theory as follows: The vertex `(-1, 0)` is considered as the source of this network, and the vertex `(2, 0)` as the sink. The cost function is defined to be `1` on the edge from `(0, p)` to `(1, p)` for each `p \in P`, and to be `0` on every other edge. The capacity is `1` on each edge. Here is how to translate this notations into that used in [BF1999]_::
our notations [BF1999] (-1, 0) s (0, p) x_p (1, p) y_p (2, 0) t a[e] a(e)
EXAMPLES::
sage: ps = [[16,12,14,-13],[[12,14],[14,-13],[12,16],[16,-13]]] sage: G, e = Poset(ps).frank_network() sage: G.edges() [((-1, 0), (0, -13), None), ((-1, 0), (0, 12), None), ((-1, 0), (0, 14), None), ((-1, 0), (0, 16), None), ((0, -13), (1, -13), None), ((0, -13), (1, 12), None), ((0, -13), (1, 14), None), ((0, -13), (1, 16), None), ((0, 12), (1, 12), None), ((0, 14), (1, 12), None), ((0, 14), (1, 14), None), ((0, 16), (1, 12), None), ((0, 16), (1, 16), None), ((1, -13), (2, 0), None), ((1, 12), (2, 0), None), ((1, 14), (2, 0), None), ((1, 16), (2, 0), None)] sage: e {((-1, 0), (0, -13)): 0, ((-1, 0), (0, 12)): 0, ((-1, 0), (0, 14)): 0, ((-1, 0), (0, 16)): 0, ((0, -13), (1, -13)): 1, ((0, -13), (1, 12)): 0, ((0, -13), (1, 14)): 0, ((0, -13), (1, 16)): 0, ((0, 12), (1, 12)): 1, ((0, 14), (1, 12)): 0, ((0, 14), (1, 14)): 1, ((0, 16), (1, 12)): 0, ((0, 16), (1, 16)): 1, ((1, -13), (2, 0)): 0, ((1, 12), (2, 0)): 0, ((1, 14), (2, 0)): 0, ((1, 16), (2, 0)): 0} sage: qs = [[1,2,3,4,5,6,7,8,9],[[1,3],[3,4],[5,7],[1,9],[2,3]]] sage: Poset(qs).frank_network() (Digraph on 20 vertices, {((-1, 0), (0, 1)): 0, ((-1, 0), (0, 2)): 0, ((-1, 0), (0, 3)): 0, ((-1, 0), (0, 4)): 0, ((-1, 0), (0, 5)): 0, ((-1, 0), (0, 6)): 0, ((-1, 0), (0, 7)): 0, ((-1, 0), (0, 8)): 0, ((-1, 0), (0, 9)): 0, ((0, 1), (1, 1)): 1, ((0, 2), (1, 2)): 1, ((0, 3), (1, 1)): 0, ((0, 3), (1, 2)): 0, ((0, 3), (1, 3)): 1, ((0, 4), (1, 1)): 0, ((0, 4), (1, 2)): 0, ((0, 4), (1, 3)): 0, ((0, 4), (1, 4)): 1, ((0, 5), (1, 5)): 1, ((0, 6), (1, 6)): 1, ((0, 7), (1, 5)): 0, ((0, 7), (1, 7)): 1, ((0, 8), (1, 8)): 1, ((0, 9), (1, 1)): 0, ((0, 9), (1, 9)): 1, ((1, 1), (2, 0)): 0, ((1, 2), (2, 0)): 0, ((1, 3), (2, 0)): 0, ((1, 4), (2, 0)): 0, ((1, 5), (2, 0)): 0, ((1, 6), (2, 0)): 0, ((1, 7), (2, 0)): 0, ((1, 8), (2, 0)): 0, ((1, 9), (2, 0)): 0})
AUTHOR:
- Darij Grinberg (2013-05-09) """
@combinatorial_map(name="Greene-Kleitman partition") def greene_shape(self): r""" Return the Greene-Kleitman partition of ``self``.
The Greene-Kleitman partition of a finite poset `P` is the partition `(c_1 - c_0, c_2 - c_1, c_3 - c_2, \ldots)`, where `c_k` is the maximum cardinality of a union of `k` chains of `P`. Equivalently, this is the conjugate of the partition `(a_1 - a_0, a_2 - a_1, a_3 - a_2, \ldots)`, where `a_k` is the maximum cardinality of a union of `k` antichains of `P`.
See many sources, e. g., [BF1999]_, for proofs of this equivalence.
EXAMPLES::
sage: P = Poset([[3,2,1],[[3,1],[2,1]]]) sage: P.greene_shape() [2, 1] sage: P = Poset([[1,2,3,4],[[1,4],[2,4],[4,3]]]) sage: P.greene_shape() [3, 1] sage: P = Poset([[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],[[1,4],[2,4],[4,3]]]) sage: P.greene_shape() [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] sage: P = Poset([[],[]]) sage: P.greene_shape() []
AUTHOR:
- Darij Grinberg (2013-05-09) """
def p_partition_enumerator(self, tup, R, weights=None, check=False): r""" Return a `P`-partition enumerator of ``self``.
Given a total order `\prec` on the elements of a finite poset `P` (the order of `P` and the total order `\prec` can be unrelated; in particular, the latter does not have to extend the former), a `P`-partition enumerator is the quasisymmetric function `\sum_f \prod_{p \in P} x_{f(p)}`, where the first sum is taken over all `P`-partitions `f`.
A `P`-partition is a function `f : P \to \{1,2,3,...\}` satisfying the following properties for any two elements `i` and `j` of `P` satisfying `i <_P j`:
- if `i \prec j` then `f(i) \leq f(j)`,
- if `j \prec i` then `f(i) < f(j)`.
The optional argument ``weights`` allows constructing a generalized ("weighted") version of the `P`-partition enumerator. Namely, ``weights`` should be a dictionary whose keys are the elements of ``P``. Then, the generalized `P`-partition enumerator corresponding to weights ``weights`` is `\sum_f \prod_{p \in P} x_{f(p)}^{w(p)}`, where the sum is again over all `P`-partitions `f`. Here, `w(p)` is ``weights[p]``. The classical `P`-partition enumerator is the particular case obtained when all `p` satisfy `w(p) = 1`.
In the language of [Grinb2016a]_, the generalized `P`-partition enumerator is the quasisymmetric function `\Gamma\left(\mathbf{E}, w\right)`, where `\mathbf{E}` is the special double poset `(P, <_P, \prec)`, and where `w` is the dictionary ``weights`` (regarded as a function from `P` to the positive integers).
INPUT:
- ``tup`` -- the tuple containing all elements of `P` (each of them exactly once), in the order dictated by the total order `\prec`
- ``R`` -- a commutative ring
- ``weights`` -- (optional) a dictionary of positive integers, indexed by elements of `P`; any missing item will be understood as `1`
OUTPUT:
The `P`-partition enumerator of ``self`` according to ``tup`` in the algebra `QSym` of quasisymmetric functions over the base ring `R`.
EXAMPLES::
sage: P = Poset([[1,2,3,4],[[1,4],[2,4],[4,3]]]) sage: FP = P.p_partition_enumerator((3,1,2,4), QQ, check=True); FP 2*M[1, 1, 1, 1] + 2*M[1, 2, 1] + M[2, 1, 1] + M[3, 1]
sage: expansion = FP.expand(5) sage: xs = expansion.parent().gens() sage: expansion == sum([xs[a]*xs[b]*xs[c]*xs[d] for a in range(5) for b in range(5) for c in range(5) for d in range(5) if a <= b and c <= b and b < d]) True
sage: P = Poset([[],[]]) sage: FP = P.p_partition_enumerator((), QQ, check=True); FP M[]
With the ``weights`` parameter::
sage: P = Poset([[1,2,3,4],[[1,4],[2,4],[4,3]]]) sage: FP = P.p_partition_enumerator((3,1,2,4), QQ, weights={1: 1, 2: 2, 3: 1, 4: 1}, check=True); FP M[1, 2, 1, 1] + M[1, 3, 1] + M[2, 1, 1, 1] + M[2, 2, 1] + M[3, 1, 1] + M[4, 1] sage: FP = P.p_partition_enumerator((3,1,2,4), QQ, weights={2: 2}, check=True); FP M[1, 2, 1, 1] + M[1, 3, 1] + M[2, 1, 1, 1] + M[2, 2, 1] + M[3, 1, 1] + M[4, 1]
sage: P = Poset([['a','b','c'], [['a','b'], ['a','c']]]) sage: FP = P.p_partition_enumerator(('b','c','a'), QQ, weights={'a': 3, 'b': 5, 'c': 7}, check=True); FP M[3, 5, 7] + M[3, 7, 5] + M[3, 12]
sage: P = Poset([['a','b','c'], [['a','c'], ['b','c']]]) sage: FP = P.p_partition_enumerator(('b','c','a'), QQ, weights={'a': 3, 'b': 5, 'c': 7}, check=True); FP M[3, 5, 7] + M[3, 12] + M[5, 3, 7] + M[8, 7] sage: FP = P.p_partition_enumerator(('a','b','c'), QQ, weights={'a': 3, 'b': 5, 'c': 7}, check=True); FP M[3, 5, 7] + M[3, 12] + M[5, 3, 7] + M[5, 10] + M[8, 7] + M[15] """ raise ValueError("the elements of tup are not those of P") # The simple case: ``weights == None``.
def cuts(self): r""" Return the list of cuts of the poset ``self``.
A cut is a subset `A` of ``self`` such that the set of lower bounds of the set of upper bounds of `A` is exactly `A`.
The cuts are computed here using the maximal independent sets in the auxiliary graph defined as `P \times [0,1]` with an edge from `(x, 0)` to `(y, 1)` if and only if `x \not\geq_P y`. See the end of section 4 in [JRJ94]_.
EXAMPLES::
sage: P = posets.AntichainPoset(3) sage: Pc = P.cuts() sage: [list(c) for c in Pc] [[0], [0, 1, 2], [], [1], [2]] sage: Pc[0] frozenset({0})
.. SEEALSO::
:meth:`completion_by_cuts` """ for u in self}, format="dict_of_lists") for c in IndependentSets(auxg, maximal=True)]
def completion_by_cuts(self): """ Return the completion by cuts of ``self``.
This is the smallest lattice containing the poset. This is also called the Dedekind-MacNeille completion.
See the :wikipedia:`Dedekind-MacNeille completion`.
OUTPUT:
- a finite lattice
EXAMPLES::
sage: P = posets.PentagonPoset() sage: P.completion_by_cuts().is_isomorphic(P) True
sage: Y = Poset({1: [2], 2: [3, 4]}) sage: trafficsign = LatticePoset({1: [2], 2: [3, 4], 3: [5], 4: [5]}) sage: L = Y.completion_by_cuts() sage: L.is_isomorphic(trafficsign) True
sage: P = posets.SymmetricGroupBruhatOrderPoset(3) sage: Q = P.completion_by_cuts(); Q Finite lattice containing 7 elements
.. SEEALSO::
:meth:`cuts`, :meth:`~sage.categories.finite_lattice_posets.FiniteLatticePosets.ParentMethods.irreducibles_poset`
TESTS::
sage: Poset().completion_by_cuts() Finite lattice containing 0 elements """
def incidence_algebra(self, R, prefix='I'): r""" Return the incidence algebra of ``self`` over ``R``.
OUTPUT:
An instance of :class:`sage.combinat.posets.incidence_algebras.IncidenceAlgebra`.
EXAMPLES::
sage: P = posets.BooleanLattice(4) sage: P.incidence_algebra(QQ) Incidence algebra of Finite lattice containing 16 elements over Rational Field """
def _kl_poly(self, x=None, y=None, canonical_labels=None): r""" Cached Kazhdan-Lusztig polynomial of ``self`` for generic `q`.
EXAMPLES::
sage: L = posets.SymmetricGroupWeakOrderPoset(4) sage: L._kl_poly() 1 sage: x = '2314' sage: y = '3421' sage: L._kl_poly(x, y) -q + 1
.. SEEALSO::
:meth:`kazhdan_lusztig_polynomial`
AUTHORS:
- Travis Scrimshaw (27-12-2014) """
# Handle some special cases return q.parent().zero()
x = self.minimal_elements()[0] y = self.maximal_elements()[0] return q.parent().zero()
else: sublat(self.order_filter([x])).kazhdan_lusztig_polynomial() for x in self if x != min_elt)
def kazhdan_lusztig_polynomial(self, x=None, y=None, q=None, canonical_labels=None): r""" Return the Kazhdan-Lusztig polynomial `P_{x,y}(q)` of the poset.
The poset is expected to be ranked.
We follow the definition given in [EPW14]_. Let `G` denote a graded poset with unique minimal and maximal elements and `\chi_G` denote the characteristic polynomial of `G`. Let `I_x` and `F^x` denote the principal order ideal and filter of `x` respectively. Define the *Kazhdan-Lusztig polynomial* of `G` as the unique polynomial `P_G(q)` satisfying the following:
1. If `\operatorname{rank} G = 0`, then `P_G(q) = 1`. 2. If `\operatorname{rank} G > 0`, then `\deg P_G(q) < \frac{1}{2} \operatorname{rank} G`. 3. We have
.. MATH::
q^{\operatorname{rank} G} P_G(q^{-1}) = \sum_{x \in G} \chi_{I_x}(q) P_{F^x}(q).
We then extend this to `P_{x,y}(q)` by considering the subposet corresponding to the (closed) interval `[x, y]`. We also define `P_{\emptyset}(q) = 0` (so if `x \not\leq y`, then `P_{x,y}(q) = 0`).
INPUT:
- ``q`` -- (default: `q \in \ZZ[q]`) the indeterminate `q` - ``x`` -- (default: the minimal element) the element `x` - ``y`` -- (default: the maximal element) the element `y` - ``canonical_labels`` -- (optional) for subposets, use the canonical labeling (this can limit recursive calls for posets with large amounts of symmetry, but producing the labeling takes time); if not specified, this is ``True`` if ``x`` and ``y`` are both not specified and ``False`` otherwise
EXAMPLES::
sage: L = posets.BooleanLattice(3) sage: L.kazhdan_lusztig_polynomial() 1
::
sage: L = posets.SymmetricGroupWeakOrderPoset(4) sage: L.kazhdan_lusztig_polynomial() 1 sage: x = '2314' sage: y = '3421' sage: L.kazhdan_lusztig_polynomial(x, y) -q + 1 sage: L.kazhdan_lusztig_polynomial(x, y, var('t')) -t + 1
AUTHORS:
- Travis Scrimshaw (27-12-2014) """ raise ValueError("the poset is not ranked")
def is_induced_subposet(self, other): r""" Return ``True`` if the poset is an induced subposet of ``other``, and ``False`` otherwise.
A poset `P` is an induced subposet of `Q` if every element of `P` is an element of `Q`, and `x \le_P y` iff `x \le_Q y`. Note that "induced" here has somewhat different meaning compared to that of graphs.
INPUT:
- ``other``, a poset.
.. NOTE::
This method does not check whether the poset is a *isomorphic* (i.e., up to relabeling) subposet of ``other``, but only if ``other`` directly contains the poset as an induced subposet. For isomorphic subposets see :meth:`has_isomorphic_subposet`.
EXAMPLES::
sage: P = Poset({1:[2, 3]}) sage: Q = Poset({1:[2, 4], 2:[3]}) sage: P.is_induced_subposet(Q) False sage: R = Poset({0:[1], 1:[3, 4], 3:[5], 4:[2]}) sage: P.is_induced_subposet(R) True
TESTS::
sage: P = Poset({2:[1]}) sage: Poset().is_induced_subposet(P) True sage: Poset().is_induced_subposet(Poset()) True sage: P.is_induced_subposet(Poset()) False
Bad input::
sage: Poset().is_induced_subposet('junk') Traceback (most recent call last): ... AttributeError: 'str' object has no attribute 'subposet' """ (isinstance(other, FinitePoset) and not other._is_facade)): raise TypeError("the function is not defined on non-facade posets") # TODO: When we have decided if # Poset({'x':[42]}) == LatticePoset({'x':[42]}) # or not, either remove this note or remove .hasse_diagram() below. other.subposet(self).hasse_diagram() == self.hasse_diagram())
FinitePoset._dual_class = FinitePoset
##### Posets #####
class FinitePosets_n(UniqueRepresentation, Parent): r""" The finite enumerated set of all posets on `n` elements, up to an isomorphism.
EXAMPLES::
sage: P = Posets(3) sage: P.cardinality() 5 sage: for p in P: print(p.cover_relations()) [] [[1, 2]] [[0, 1], [0, 2]] [[0, 1], [1, 2]] [[1, 2], [0, 2]] """
def __init__(self, n): r""" EXAMPLES::
sage: P = Posets(3); P Posets containing 3 elements sage: P.category() Category of finite enumerated sets sage: P.__class__ <class 'sage.combinat.posets.posets.FinitePosets_n_with_category'> sage: TestSuite(P).run() """
def _repr_(self): r""" EXAMPLES::
sage: P = Posets(3) sage: P._repr_() 'Posets containing 3 elements' """
def __contains__(self, P): """ EXAMPLES::
sage: posets.PentagonPoset() in Posets(5) True sage: posets.PentagonPoset() in Posets(3) False sage: 1 in Posets(3) False """
def __iter__(self): """ Returns an iterator of representatives of the isomorphism classes of finite posets of a given size.
.. note::
This uses the DiGraph iterator as a backend to construct transitively-reduced, acyclic digraphs.
EXAMPLES::
sage: P = Posets(2) sage: list(P) [Finite poset containing 2 elements, Finite poset containing 2 elements] """ # We need to relabel the digraph since range(self._n) must be a linear # extension. Too bad we need to compute this again. TODO: Fix this.
def cardinality(self, from_iterator=False): r""" Return the cardinality of this object.
.. note::
By default, this returns pre-computed values obtained from the On-Line Encyclopedia of Integer Sequences (:oeis:`A000112`). To override this, pass the argument ``from_iterator=True``.
EXAMPLES::
sage: P = Posets(3) sage: P.cardinality() 5 sage: P.cardinality(from_iterator=True) 5 """ # Obtained from The On-Line Encyclopedia of Integer Sequences; # this is sequence number A000112. 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087] else:
# For backward compatibility of pickles of the former Posets() Posets_all = Posets
##### Miscellaneous functions #####
def is_poset(dig): r""" Return ``True`` if a directed graph is acyclic and transitively reduced, and ``False`` otherwise.
EXAMPLES::
sage: from sage.combinat.posets.posets import is_poset sage: dig = DiGraph({0:[2, 3], 1:[3, 4, 5], 2:[5], 3:[5], 4:[5]}) sage: is_poset(dig) False sage: is_poset(dig.transitive_reduction()) True """
def _ford_fulkerson_chronicle(G, s, t, a): r""" Iterate through the Ford-Fulkerson algorithm for an acyclic directed graph with all edge capacities equal to `1`. This is an auxiliary algorithm for use by the :meth:`FinitePoset.greene_shape` method of finite posets, and is lacking some of the functionality that a general Ford-Fulkerson algorithm implementation should have.
INPUT:
- ``G`` -- an acyclic directed graph
- ``s`` -- a vertex of `G` as the source
- ``t`` -- a vertex of `G` as the sink
- ``a`` -- a cost function (on the set of edges of ``G``) encoded as a dictionary. The keys of this dictionary are encoded as pairs of vertices.
OUTPUT:
An iterator which iterates through the values `(p, v)` during the application of the Ford-Fulkerson algorithm applied to the graph `G` with source `s`, sink `t`, cost function `a` and capacity `1` on each edge. Here, `p` denotes the value of the potential, and `v` denotes the value of the flow at every moment during the execution of the algorithm. The algorithm starts at `(p, v) = (0, 0)`. Every time ``next()`` is called, the iterator performs one step of the algorithm (incrementing either `p` or `v`) and yields the resulting pair `(p, v)`. Note that `(0, 0)` is never yielded. The iterator goes on for eternity, since the stopping condition is not implemented. This is OK for use in the ``greene_partition`` function, since that one knows when to stop.
The notation used here is that of Section 7 of [BF1999]_.
.. WARNING::
This method is tailor-made for its use in the :meth:`FinitePoset.greene_shape()` method of a finite poset. It's not very useful in general. First of all, as said above, the iterator does not know when to halt. Second, `G` needs to be acyclic for it to correctly work. This must be amended if this method is ever to be used outside the Greene-Kleitman partition construction. For the Greene-Kleitman partition, this is a non-issue since Frank's network is always acyclic.
EXAMPLES::
sage: from sage.combinat.posets.posets import _ford_fulkerson_chronicle sage: G = DiGraph({1: [3,6,7], 2: [4], 3: [7], 4: [], 6: [7,8], 7: [9], 8: [9,12], 9: [], 10: [], 12: []}) sage: s = 1 sage: t = 9 sage: (1, 6, None) in G.edges() True sage: (1, 6) in G.edges() False sage: a = {(1, 6): 4, (2, 4): 0, (1, 3): 4, (1, 7): 1, (3, 7): 6, (7, 9): 1, (6, 7): 3, (6, 8): 1, (8, 9): 0, (8, 12): 2} sage: ffc = _ford_fulkerson_chronicle(G, s, t, a) sage: next(ffc) (1, 0) sage: next(ffc) (2, 0) sage: next(ffc) (2, 1) sage: next(ffc) (3, 1) sage: next(ffc) (4, 1) sage: next(ffc) (5, 1) sage: next(ffc) (5, 2) sage: next(ffc) (6, 2) sage: next(ffc) (7, 2) sage: next(ffc) (8, 2) sage: next(ffc) (9, 2) sage: next(ffc) (10, 2) sage: next(ffc) (11, 2) """
# pi: potential function as a dictionary. # p: value of the potential pi.
# f: flow function as a dictionary. # val: value of the flow f. (Can't call it v due to Python's asinine # handling of for loops.)
# capacity: capacity function as a dictionary. Here, just the # indicator function of the set of arcs of G.
# Step MC1 in Britz-Fomin, Algorithm 7.2.
# Gprime: directed graph G' from Britz-Fomin, Section 7.
# X: list of vertices of G' reachable from s, along with # the shortest paths from s to them. # Step MC2a in Britz-Fomin, Algorithm 7.2. else: else: # Step MC2b in Britz-Fomin, Algorithm 7.2.
|