Finite posets

This module implements finite partially ordered sets. It defines:

FinitePoset A class for finite posets
FinitePosets_n A class for finite posets up to isomorphism (i.e. unlabeled posets)
Poset() Construct a finite poset from various forms of input data.
is_poset() Return True if a directed graph is acyclic and transitively reduced.

List of Poset methods

Comparing, intervals and relations

is_less_than() Return True if \(x\) is strictly less than \(y\) in the poset.
is_greater_than() Return True if \(x\) is strictly greater than \(y\) in the poset.
is_lequal() Return True if \(x\) is less than or equal to \(y\) in the poset.
is_gequal() Return True if \(x\) is greater than or equal to \(y\) in the poset.
compare_elements() Compare two element of the poset.
closed_interval() Return the list of elements in a closed interval of the poset.
open_interval() Return the list of elements in an open interval of the poset.
relations() Return the list of relations in the poset.
relations_iterator() Return an iterator over relations in the poset.
order_filter() Return the upper set generated by elements.
order_ideal() Return the lower set generated by elements.

Covering

covers() Return True if y covers x.
lower_covers() Return elements covered by given element.
upper_covers() Return elements covering given element.
cover_relations() Return the list of cover relations.
lower_covers_iterator() Return an iterator over elements covered by given element.
upper_covers_iterator() Return an iterator over elements covering given element.
cover_relations_iterator() Return an iterator over cover relations of the poset.

Properties of the poset

cardinality() Return the number of elements in the poset.
height() Return the number of elements in a longest chain of the poset.
width() Return the number of elements in a longest antichain of the poset.
relations_number() Return the number of relations in the poset.
dimension() Return the dimension of the poset.
jump_number() Return the jump number of the poset.
has_bottom() Return True if the poset has a unique minimal element.
has_top() Return True if the poset has a unique maximal element.
is_bounded() Return True if the poset has both unique minimal and unique maximal element.
is_chain() Return True if the poset is totally ordered.
is_connected() Return True if the poset is connected.
is_graded() Return True if all maximal chains of the poset has same length.
is_ranked() Return True if the poset has a rank function.
is_rank_symmetric() Return True if the poset is rank symmetric.
is_series_parallel() Return True if the poset can be built by ordinal sums and disjoint unions.
is_greedy() Return True if all greedy linear extensions have equal number of jumps.
is_jump_critical() Return True if removal of any element reduces the jump number.
is_eulerian() Return True if the poset is Eulerian.
is_incomparable_chain_free() Return True if the poset is (m+n)-free.
is_slender() Return True if the poset is slender.
is_join_semilattice() Return True is the poset has a join operation.
is_meet_semilattice() Return True if the poset has a meet operation.

Minimal and maximal elements

bottom() Return the bottom element of the poset, if it exists.
top() Return the top element of the poset, if it exists.
maximal_elements() Return the list of the maximal elements of the poset.
minimal_elements() Return the list of the minimal elements of the poset.

New posets from old ones

disjoint_union() Return the disjoint union of the poset with other poset.
ordinal_sum() Return the ordinal sum of the poset with other poset.
product() Return the Cartesian product of the poset with other poset.
ordinal_product() Return the ordinal product of the poset with other poset.
lexicographic_sum() Return the lexicographic sum of posets.
star_product() Return the star product of the poset with other poset.
with_bounds() Return the poset with bottom and top element adjoined.
without_bounds() Return the poset with bottom and top element removed.
dual() Return the dual of the poset.
completion_by_cuts() Return the Dedekind-MacNeille completion of the poset.
intervals_poset() Return the poset of intervals of the poset.
connected_components() Return the connected components of the poset as subposets.
factor() Return the decomposition of the poset as a Cartesian product.
ordinal_summands() Return the ordinal summands of the poset.
subposet() Return the subposet containing elements with partial order induced by this poset.
random_subposet() Return a random subposet that contains each element with given probability.
relabel() Return a copy of this poset with its elements relabelled.
canonical_label() Return copy of the poset canonically (re)labelled to integers.

Chains & antichains

is_chain_of_poset() Return True if elements in the given list are comparable.
is_antichain_of_poset() Return True if elements in the given list are incomparable.
chains() Return the chains of the poset.
antichains() Return the antichains of the poset.
maximal_chains() Return the maximal chains of the poset.
maximal_antichains() Return the maximal antichains of the poset.
antichains_iterator() Return an iterator over the antichains of the poset.
random_maximal_chain() Return a random maximal chain.
random_maximal_antichain() Return a random maximal antichain.

Drawing

show() Display the Hasse diagram of the poset.
plot() Return a Graphic object corresponding the Hasse diagram of the poset.
graphviz_string() Return a representation in the DOT language, ready to render in graphviz.

Comparing posets

is_isomorphic() Return True if both posets are isomorphic.
is_induced_subposet() Return True if given poset is an induced subposet of this poset.

Polynomials

chain_polynomial() Return the chain polynomial of the poset.
characteristic_polynomial() Return the characteristic polynomial of the poset.
f_polynomial() Return the f-polynomial of the poset.
flag_f_polynomial() Return the flag f-polynomial of the poset.
h_polynomial() Return the h-polynomial of the poset.
flag_h_polynomial() Return the flag h-polynomial of the poset.
order_polynomial() Return the order polynomial of the poset.
zeta_polynomial() Return the zeta polynomial of the poset.
kazhdan_lusztig_polynomial() Return the Kazhdan-Lusztig polynomial of the poset.
coxeter_polynomial() Return the characteristic polynomial of the Coxeter transformation.
degree_polynomial() Return the generating polynomial of degrees of vertices in the Hasse diagram.
p_partition_enumerator() Return a \(P\)-partition enumerator of the poset.

Polytopes

chain_polytope() Return the chain polytope of the poset.
order_polytope() Return the order polytope of the poset.

Graphs

hasse_diagram() Return the Hasse diagram of the poset as a directed graph.
cover_relations_graph() Return the (undirected) graph of cover relations.
comparability_graph() Return the comparability graph of the poset.
incomparability_graph() Return the incomparability graph of the poset.
frank_network() Return Frank’s network of the poset.
linear_extensions_graph() Return the linear extensions graph of the poset.

Linear extensions

is_linear_extension() Return True if the given list is a linear extension of the poset.
linear_extension() Return a linear extension of the poset.
linear_extensions() Return the enumerated set of all the linear extensions of the poset.
promotion() Return the (extended) promotion on the linear extension of the poset.
evacuation() Return evacuation on the linear extension associated to the poset.
with_linear_extension() Return a copy of self with a different default linear extension.
random_linear_extension() Return a random linear extension.

Matrices

lequal_matrix() Computes the matrix whose (i,j) entry is 1 if self.linear_extension()[i] < self.linear_extension()[j] and 0 otherwise.
moebius_function() Return the value of Möbius function of given elements in the poset.
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].
coxeter_transformation() Return the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules.
coxeter_smith_form() Return the Smith form of the Coxeter transformation.

Miscellanous

sorted() Return given list sorted by the poset.
isomorphic_subposets() Return all subposets isomorphic to another poset.
isomorphic_subposets_iterator() Return an iterator over the subposets isomorphic to another poset.
has_isomorphic_subposet() Return True if the poset contains a subposet isomorphic to another poset.
list() List the elements of the poset.
cuts() Return the cuts of the given poset.
dilworth_decomposition() Return a partition of the points into the minimal number of chains.
greene_shape() Computes the Greene-Kleitman partition aka Greene shape of the poset self.
incidence_algebra() Return the incidence algebra of self.
is_EL_labelling() Return whether f is an EL labelling of the poset.
isomorphic_subposets_iterator() Return an iterator over the subposets isomorphic to another poset.
isomorphic_subposets() Return all subposets isomorphic to another poset.
level_sets() Return elements grouped by maximal number of cover relations from a minimal element.
order_complex() Return the order complex associated to this poset.
random_order_ideal() Return a random order ideal of self with uniform probability.
rank() Return the rank of an element, or the rank of the poset.
rank_function() Return a rank function of the poset, if it exists.
unwrap() Unwraps an element of this poset.

Classes and functions

sage.combinat.posets.posets.FinitePoset

A (finite) \(n\)-element poset constructed from a directed acyclic graph.

INPUT:

  • hasse_diagram – an instance of FinitePoset, or a 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.
  • categoryFinitePosets, or a subcategory thereof.
  • facade – a boolean or None (default); whether the FinitePoset’s elements should be wrapped to make them aware of the Poset they belong to.
    • If facade = True, the FinitePoset’s elements are exactly those given as input.
    • If facade = False, the FinitePoset’s elements will become 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 FinitePoset is built from another 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.

sage.combinat.posets.posets.FinitePosets_n

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]]
sage.combinat.posets.posets.Poset(data=None, element_labels=None, cover_relations=False, linear_extension=False, category=None, facade=None, key=None)

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 of upper covers: data[x] is a list of the elements that cover the element \(x\) in the poset.

    4. A list or tuple of upper covers: data[x] is a list of the elements that cover the element \(x\) in the poset.

      If the set of elements is not a set of consecutive integers starting from zero, then:

      • every element must appear in the data, for example in its own entry.
      • data must be ordered in the same way as sorted elements.

      Warning

      If data is a list or tuple of length \(2\), then it is handled by the case 2 above.

    5. 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.

    6. 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 Poset()’s elements should be wrapped to make them aware of the Poset they belong to.

    • If facade = True, the Poset()’s elements are exactly those given as input.
    • If facade = False, the Poset()’s elements will become 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 Poset() is built from another Poset(), itself built with facade = False)

OUTPUT:

FinitePoset – an instance of the FinitePoset class.

If category is specified, then the poset is created in this category instead of FinitePosets.

See also

Posets, Posets, 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
    
  4. A list of upper covers, with range(5) as set of vertices:

    sage: Poset([[1,2],[4],[3],[4],[]])
    Finite poset containing 5 elements
    

    A list of upper covers, with letters as vertices:

    sage: Poset([["a","b"],["b","c"],["c"]])
    Finite poset containing 3 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 case 2. So you cannot use this method to input a 2-element poset.

  5. 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
    

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.

See also

FinitePoset.linear_extensions()

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

DiGraph is used to construct the poset, and the vertices of a DiGraph are converted to plain Python int’s if they are 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 Integer’s if they are 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

Unique representation

As most parents, Poset have unique representation (see 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 UniqueRepresentation. It is otherwise ignored by the poset constructor.

sage.combinat.posets.posets.is_poset(dig)

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