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 ofFinitePoset
, or aDiGraph
that is transitively-reduced, acyclic, loop-free, and multiedge-free.elements
– an optional list of elements, withelement[i]
corresponding to vertexi
. Ifelements
isNone
, then it is set to be the vertex set of the digraph. Note that if this option is set, thenelements
is considered as a specified linear extension of the poset and the \(linear_extension\) attribute is set.category
–FinitePosets
, or a subcategory thereof.facade
– a boolean orNone
(default); whether theFinitePoset
’s elements should be wrapped to make them aware of the Poset they belong to.- If
facade = True
, theFinitePoset
’s elements are exactly those given as input. - If
facade = False
, theFinitePoset
’s elements will becomePosetElement
objects. - If
facade = None
(default) the expected behaviour is the behaviour offacade = True
, unless the opposite can be deduced from the context (i.e. for instance if aFinitePoset
is built from anotherFinitePoset
, itself built withfacade = False
)
- If
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
isPosetElement
. It can also define_dual_class
which is the class of dual posets of this class. E.g.FiniteMeetSemilattice._dual_class
isFiniteJoinSemilattice
.
-
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:A two-element list or tuple
(E, R)
, whereE
is a collection of elements of the poset andR
is a collection of relationsx <= 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. Ifcover_relations=True
, thenR
is assumed to contain exactly the cover relations of the poset. IfE
is empty, thenE
is taken to be the set of elements appearing in the relationsR
.A two-element list or tuple
(E, f)
, whereE
is the set of elements of the poset andf
is a function such that, for any pairx, y
of elements ofE
,f(x, y)
returns whetherx <= y
. Ifcover_relations=True
, thenf(x, y)
should instead return whetherx
is covered byy
.A dictionary of upper covers:
data[x]
is a list of the elements that cover the element \(x\) in the poset.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.
An acyclic, loop-free and multi-edge free
DiGraph
. Ifcover_relations
isTrue
, then the edges of the digraph are assumed to correspond to the cover relations of the poset. Otherwise, the cover relations are computed.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)
, thenE
is taken to be the linear extension.facade
– a boolean orNone
(default); whether thePoset()
’s elements should be wrapped to make them aware of the Poset they belong to.- If
facade = True
, thePoset()
’s elements are exactly those given as input. - If
facade = False
, thePoset()
’s elements will becomePosetElement
objects. - If
facade = None
(default) the expected behaviour is the behaviour offacade = True
, unless the opposite can be deduced from the context (i.e. for instance if aPoset()
is built from anotherPoset()
, itself built withfacade = False
)
- If
OUTPUT:
FinitePoset
– an instance of theFinitePoset
class.If
category
is specified, then the poset is created in this category instead ofFinitePosets
.See also
Posets
,Posets
,FinitePosets
EXAMPLES:
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]]
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
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, 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.
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 aDiGraph
are converted to plain Pythonint
’s if they areInteger
’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 areint
’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 (seeUniqueRepresentation
). 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 toUniqueRepresentation
. 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, andFalse
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