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() |
Tests whether a directed graph is acyclic and transitively reduced. |
List of Poset methods¶
Comparing & intervals
is_greater_than() |
Return True if ![]() ![]() False otherwise. |
is_gequal() |
Return True if ![]() ![]() False otherwise. |
is_less_than() |
Return True if ![]() ![]() False otherwise. |
is_lequal() |
Return True if ![]() ![]() False otherwise. |
compare_elements() |
Compares ![]() ![]() |
closed_interval() |
Return a list of the elements ![]() ![]() |
open_interval() |
Return a list of the elements ![]() ![]() |
intervals() |
Return a list of all intervals of the poset. |
intervals_iterator() |
Return an iterator for all the intervals of the poset. |
order_filter() |
Return the order filter generated by a list of elements. |
order_ideal() |
Return the order ideal generated by a list of elements. |
Covering
covers() |
Return True if y covers x and False otherwise. |
lower_covers() |
Return a list of lower covers of the element y. |
upper_covers() |
Return a list of upper covers of the element y. An upper cover of y is an element x such that y x is a cover relation. |
cover_relations() |
Return the list of pairs ![]() |
lower_covers_iterator() |
Return an iterator for the lower covers of the element y. An lower cover of y is an element x such that y x is a cover relation. |
upper_covers_iterator() |
Return an iterator for the upper covers of the element y. An upper cover of y is an element x such that y x is a cover relation. |
cover_relations_iterator() |
Return an iterator for the cover relations of the poset. |
Properties of the poset
cardinality() |
Return the number of elements in the poset. |
height() |
Return the height (number of elements in the longest chain) of the poset. |
width() |
Return the width of the poset (the size of its longest antichain). |
dimension() |
Return the dimension of the poset. |
relations_number() |
Return the number of relations in 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 contains a unique maximal element and a unique minimal element, and False otherwise. |
is_chain() |
Return True if the poset is totally ordered, and False otherwise. |
is_connected() |
Return True if the poset is connected, and False otherwise. |
is_graded() |
Return whether this poset is graded. |
is_ranked() |
Return whether this poset is ranked. |
is_incomparable_chain_free() |
Return whether the poset is ![]() |
is_slender() |
Return whether the poset self is slender or not. |
is_join_semilattice() |
Return True is the poset has a join operation, and False otherwise. |
is_meet_semilattice() |
Return True if self has a meet operation, and False otherwise. |
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. |
ordinal_product() |
Return the ordinal product of the poset with other poset. |
product() |
Return the cartesian product of the poset with other poset. |
dual() |
Return the dual poset of this poset. |
completion_by_cuts() |
Return the Dedekind-MacNeille completion of the poset. |
connected_components() |
Return the connected components of the poset as subposets. |
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. |
canonical_label() |
Return copy of the poset canonically (re)labelled with elements ![]() |
relabel() |
Return a copy of this poset with its elements relabelled. |
Chains & antichains
is_chain_of_poset() |
Return True if given iterable is a chain of the poset. |
chains() |
Return all the chains of self . |
antichains() |
Return the antichains of the poset. |
maximal_chains() |
Return all maximal chains of the poset. |
maximal_antichains() |
Return all maximal antichains of the poset. |
antichains_iterator() |
Return an iterator over the antichains of the poset. |
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. |
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 a bounded poset. |
flag_f_polynomial() |
Return the flag f-polynomial of a bounded and ranked poset. |
flag_h_polynomial() |
Return the flag h-polynomial of a bounded and ranked poset. |
h_polynomial() |
Return the h-polynomial of a bounded poset. |
order_polynomial() |
Return the order polynomial of the poset. |
zeta_polynomial() |
Return the zeta polynomial of the poset. |
Polytopes
chain_polytope() |
Return the chain polytope of the poset. |
order_polytope() |
Return the order polytope of the poset. |
Other & not yet classified
comparability_graph() |
Return the comparability graph of the poset. |
cover_relations_graph() |
Return the graph of cover relations. |
coxeter_transformation() |
Return the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules. |
cuts() |
Return the cuts of the given poset. |
dilworth_decomposition() |
Return a partition of the points into the minimal number of chains. |
evacuation() |
Computes evacuation on the linear extension associated to the poset self . |
frank_network() |
Return Frank’s network (a DiGraph along with a cost function on its edges) associated to self . |
greene_shape() |
Computes the Greene-Kleitman partition aka Greene shape of the poset self . |
hasse_diagram() |
Return the Hasse diagram of self as a Sage DiGraph . |
has_isomorphic_subposet() |
Return True if the poset contains a subposet isomorphic to another poset, and False otherwise. |
incidence_algebra() |
Return the indicence algebra of self . |
incomparability_graph() |
Return the incomparability graph of the poset. |
is_EL_labelling() |
Return whether f is an EL labelling of the poset. |
is_linear_extension() |
Return whether l is a linear extension of self . |
isomorphic_subposets_iterator() |
Return an iterator over the subposets isomorphic to another poset. |
isomorphic_subposets() |
Return all subposets isomorphic to another poset. |
lequal_matrix() |
Computes the matrix whose (i,j) entry is 1 if self.linear_extension()[i] < self.linear_extension()[j] and 0 otherwise. |
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]. |
linear_extension() |
Return a linear extension of this poset. |
linear_extensions() |
Return the enumerated set of all the linear extensions of this poset. |
list() |
List the elements of the poset. This just returns the result of linear_extension() . |
mobius_function_matrix() |
Return a matrix whose (i,j) entry is the value of the Mobius function evaluated at self.linear_extension()[i] and self.linear_extension()[j] . |
mobius_function() |
Return the value of the Mobius function of the poset on the elements x and y. |
order_complex() |
Return the order complex associated to this poset. |
p_partition_enumerator() |
Return a ![]() |
promotion() |
Computes the (extended) promotion on the linear extension of the poset self . |
random_order_ideal() |
Return a random order ideal of self with uniform probability. |
rank_function() |
Return a rank function of the poset, if it exists. |
rank() |
Return the rank of an element, or the rank of the poset if element is None. |
unwrap() |
Unwraps an element of this poset. |
with_linear_extension() |
Return a copy of self with a different default linear extension. |
Classes and functions¶
-
class
sage.combinat.posets.posets.
FinitePoset
(hasse_diagram, elements, category, facade, key)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
A (finite)
-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 theattribute 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() Join of Category of finite posets and Category of finite enumerated sets 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() Join of Category of finite posets and Category of finite enumerated sets sage: parent(P[0]) is P True sage: Q = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=True) sage: Q.category() Join of Category of finite posets and Category of finite enumerated sets and Category of facade sets 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() Join of Category of finite posets and Category of finite enumerated sets and Category of facade sets 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() Join of Category of finite posets and Category of finite enumerated sets 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
.TESTS:
Equality is derived from
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
-
Element
¶ alias of
PosetElement
-
antichains
(element_constructor=<type 'list'>)¶ Returns the antichains of the poset.
INPUT:
element_constructor
– a function taking an iterable as argument (default: list)
OUTPUT: an enumerated set
An antichain of a poset is a collection of elements of the poset that are pairwise incomparable.
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] sage: list(Posets.AntichainPoset(3).antichains()) [[], [2], [2, 1], [2, 1, 0], [2, 0], [1], [1, 0], [0]] sage: list(Posets.ChainPoset(3).antichains()) [[], [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
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}]
Note
Internally, this uses
sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets
andSearchForest
. At this point, iterating through this set is about twice slower than usingantichains_iterator()
(tested onposets.AntichainPoset(15)
). The algorithm is the same (depth first search through the tree), butantichains_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.
See also
-
antichains_iterator
()¶ Returns an iterator over the antichains of the poset.
EXAMPLES:
sage: Posets.PentagonPoset().antichains_iterator() <generator object antichains_iterator at ...>
See also
-
bottom
()¶ 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
See also
-
canonical_label
()¶ Return the unique poset on the labels
(where
is the number of elements in the poset) that is isomorphic to this poset and invariant in the isomorphism class.
See also
- Canonical labeling of directed graphs:
canonical_label()
EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True, facade=False) 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.canonical_label() sage: Q.list() # random [0, 1, 2, 3, 4, 5] sage: Q.is_isomorphic(P) True
As a facade:
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, 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.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
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
- Canonical labeling of directed graphs:
-
cardinality
()¶ Returns the number of elements in the poset.
EXAMPLES:
sage: Poset([[1,2,3],[4],[4],[4],[]]).cardinality() 5
-
chain_polynomial
()¶ Return the chain polynomial of
self
.The coefficient of
is the number of chains of length
in
self
. The length of a chain is the number of elements.Warning
This is not what has been called the chain polynomial in [St1986]. The latter is identical with the order polynomial (
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 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_polytope
()¶ Return the chain polytope of the poset
self
.The chain polytope of a finite poset
is defined as the subset of
consisting of all maps
satisfying
and
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 QQ^3 defined as the convex hull of 8 vertices sage: P = posets.PentagonPoset() sage: Q = P.chain_polytope();Q A 5-dimensional polyhedron in QQ^5 defined as the convex hull of 8 vertices
-
chains
(element_constructor=<type 'list'>, exclude=None)¶ Return all the chains of
self
.INPUT:
element_constructor
– a function taking an iterable asargument (default:
list
)
exclude
– elements of the poset to be excluded (default:None
)
OUTPUT:
The enumerated set of all chains of
self
, each of which is given as anelement_constructor
.A chain of a poset is a set of elements of the poset that are pairwise comparable.
EXAMPLES:
sage: A = Posets.PentagonPoset().chains(); A Set of chains of Finite lattice containing 5 elements sage: list(A) [[], [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]]
To get the chains of a given size one can currently use:
sage: list(A.elements_of_depth_iterator(2)) [[0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 4]]
For bounded posets, one can exclude the bounds as follows:
sage: P = Posets.DiamondPoset(5) sage: list(P.chains(exclude=[0, 4])) [[], [1], [2], [3]]
Another example of exclusion of vertices:
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,)]
Eventually the following syntax will be accepted:
sage: A.subset(size = 2) # todo: not implemented
See also
-
characteristic_polynomial
()¶ Return the characteristic polynomial of a graded poset
self
.If
is a graded poset with rank
and a unique minimal element
, then the characteristic polynomial of
is defined to be
where
is the rank function, and
is the Moebius function of
.
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 sage: P = Poset({1: []}) sage: P.characteristic_polynomial() 1
-
closed_interval
(x, y)¶ Return a list of the elements
such that
.
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.closed_interval(2,7)) True
-
comparability_graph
()¶ Returns the comparability graph of
self
.See Wikipedia article Comparability_graph
EXAMPLES:
sage: p = posets.ChainPoset(4) sage: p.comparability_graph().is_isomorphic(graphs.CompleteGraph(4)) True sage: p = posets.DiamondPoset(5) sage: g = p.comparability_graph(); g Comparability graph on 5 vertices sage: g.size() 7
-
compare_elements
(x, y)¶ Compare
and
in the poset.
If
x
=y
, then0
is returned; ifx
<y
, then-1
is returned; ifx
>y
, then1
is returned; and ifx
andy
are not comparable, thenNone
is returned.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)
-
completion_by_cuts
()¶ Return the completion by cuts of
self
.This is a lattice, also called the Dedekind-MacNeille completion.
See the Wikipedia article Dedekind-MacNeille completion.
OUTPUT:
- a finite lattice
EXAMPLES:
sage: P = posets.PentagonPoset() sage: P.completion_by_cuts().is_isomorphic(P) True sage: P = posets.AntichainPoset(3) sage: Q = P.completion_by_cuts() sage: Q.is_isomorphic(posets.DiamondPoset(5)) True sage: P = posets.SymmetricGroupBruhatOrderPoset(3) sage: Q = P.completion_by_cuts(); Q Finite lattice containing 7 elements
See also
-
connected_components
()¶ Return the connected components of
self
as subposets.EXAMPLES:
sage: P = Poset({1:[2,3], 3:[4,5]}) sage: CC = P.connected_components() sage: CC is P True sage: P = Poset({1:[2,3], 3:[4,5], 6:[7,8]}) sage: sorted(P.connected_components(), key=len) [Finite poset containing 3 elements, Finite poset containing 5 elements]
-
cover_relations
()¶ Returns the list of pairs [u,v] of elements of the poset such that u v is a cover relation (that is, u v and there does not exist z such that u z v).
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: Q.cover_relations() [[1, 2], [0, 2], [2, 3], [3, 4]]
-
cover_relations_graph
()¶ Return the graph of cover relations.
EXAMPLES:
sage: P = Poset({0:[1,2],1:[3],2:[3],3:[]}) sage: G = P.cover_relations_graph(); G Graph on 4 vertices sage: S = Poset() sage: H = S.cover_relations_graph(); H Graph on 0 vertices
Check that it is hashable and coincides with the Hasse diagram as a graph:
sage: hash(G) == hash(G) True sage: G == Graph(P.hasse_diagram()) True
-
cover_relations_iterator
()¶ Returns an iterator for the cover relations of the poset.
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(Q.cover_relations_iterator()) <type 'generator'> sage: [z for z in Q.cover_relations_iterator()] [[1, 2], [0, 2], [2, 3], [3, 4]]
-
covers
(x, y)¶ Returns True if y covers x and False otherwise.
EXAMPLES:
sage: Q = Poset([[1,5],[2,6],[3],[4],[],[6,3],[4]]) sage: Q.covers(Q(1),Q(6)) True sage: Q.covers(Q(1),Q(4)) False
-
coxeter_transformation
()¶ Returns the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules on the poset
self
, 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]
TESTS:
sage: M = Posets.PentagonPoset().coxeter_transformation() sage: M**8 == 1 True
-
cuts
()¶ Return the list of cuts of the poset
self
.A cut is a subset
of
self
such that the set of lower bounds of the set of upper bounds ofis exactly
.
The cuts are computed here using the maximal independent sets in the auxiliary graph defined as
with an edge from
to
if and only if
. 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})
See also
REFERENCES:
[JRJ94] Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), “Computing on-line the lattice of maximal antichains of posets”, Order 11 (3) p. 197-210, doi:10.1007/BF02115811
-
dilworth_decomposition
()¶ 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
chains, where
is the cardinality of its largest antichain. This method returns such a partition.
See Wikipedia article Dilworth’s_theorem.
See also
width()
– return the width of the poset.ALGORITHM:
We build a bipartite graph in which a vertex
of the poset is represented by two vertices
. For any two
such that
in the poset we add an edge
.
A matching in this graph is equivalent to a partition of the poset into chains: indeed, a chain
gives rise to the matching
, and from a matching one can build the union of chains.
- According to Dilworth’s theorem, the number of chains is equal to
(the posets’ width).
EXAMPLE:
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]]
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
-
dimension
(certificate=False)¶ Return the dimension of the Poset.
The (Dushnik-Miller) dimension of a Poset defined on a set
of points is the smallest integer
such that there exists
linear extensions of
satisfying the following property:
For more information, see the Wikipedia article 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
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
be the set of (ordered) pairs of incomparable elements of
, i.e. all
and
such that
and
. Any linear extension of
is a total order on
that can be seen as the union of relations from
along with some relations from
. Thus, the dimension of
is the smallest number of linear extensions of
which cover all points of
.
Consequently,
is equal to the chromatic number of the hypergraph
, where
is the hypergraph defined on
whose sets are all
such that
is not acyclic.
We solve this problem through a
Mixed Integer Linear Program
.EXAMPLES:
According to Wikipedia, the poset (of height 2) of a graph is
if and only if the graph is a path:
sage: G = graphs.PathGraph(6) sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()})) sage: P.dimension() 2
The actual linear extensions can be obtained with
certificate=True
:sage: P.dimension(certificates=True) # not tested -- architecture-dependent [[(0, 1), 0, (1, 2), 1, (2, 3), 2, (3, 4), 3, (4, 5), 4, 5], [(4, 5), 5, (3, 4), 4, (2, 3), 3, (1, 2), 2, (0, 1), 1, 0]]
According to Schnyder’s theorem, the poset (of height 2) of a graph has dimension
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=1) []
References:
[FT00] Stefan Felsner, William T. Trotter, Dimension, Graph and Hypergraph Coloring, Order, 2000, Volume 17, Issue 2, pp 167-177, http://link.springer.com/article/10.1023%2FA%3A1006429830221
-
disjoint_union
(other, labels='pairs')¶ Return a poset isomorphic to disjoint union (also called direct sum) of the poset with
other
.The disjoint union of
and
is a poset that contains every element and relation from both
and
, and where every element of
is incomparable to every element of
.
Mathematically, it is only defined when
and
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 elementv
in this poset will be named(0,v)
and each elementu
inother
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'], [['a', 'b']]) ) sage: P2 = Poset( (['c', 'd'], [['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']]
-
dual
()¶ Return the dual poset of the given poset.
EXAMPLES:
sage: P = Poset(([1,2,3],[[1,2],[1,3]])) sage: P.cover_relations() [[1, 2], [1, 3]] sage: Q = P.dual() sage: Q.cover_relations() [[3, 1], [2, 1]] sage: P = LatticePoset([[1,2],[3],[3]], facade = True) sage: P.cover_relations() [[0, 1], [0, 2], [1, 3], [2, 3]] sage: Q = P.dual() sage: Q.cover_relations() [[3, 2], [3, 1], [2, 0], [1, 0]] sage: Q.category() Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets sage: Q.__class__ <class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'> sage: P = MeetSemilattice([[1,2],[3],[3]]) sage: P.dual().__class__ <class 'sage.combinat.posets.lattices.FiniteJoinSemilattice_with_category'> sage: P = JoinSemilattice([[1,2],[3],[3]]) sage: P.dual().__class__ <class 'sage.combinat.posets.lattices.FiniteMeetSemilattice_with_category'>
-
evacuation
()¶ 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 sizeby applying the evacuation operator
, to the default linear extension
of
self
(seeevacuation()
), and relabelingself
accordingly. For more details see [Stan2009].See also
linear_extension()
with_linear_extension()
and thelinear_extension
option ofPoset()
evacuation()
promotion()
REFERENCES:
[Stan2009] (1, 2, 3) Richard Stanley, Promotion and evacuation, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Björner, Research Paper 9, 24 pp. 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 vertices are not labelled by
:
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]]
AUTHOR:
- Anne Schilling (2012-02-18)
-
f_polynomial
()¶ Return the
-polynomial of a bounded poset
self
.This is the
-polynomial of the order complex of the poset minus its bounds.
The coefficient of
is the number of chains of
elements containing both bounds of the poset.
See also
is_bounded()
,h_polynomial()
,order_complex()
,sage.homology.cell_complex.GenericCellComplex.f_vector()
Warning
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 sage: P = Poset({2: []}) sage: P.f_polynomial() 1
-
flag_f_polynomial
()¶ Return the flag
-polynomial of a bounded and ranked poset
self
.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
is a bounded ranked poset, then the flag
-polynomial of
is defined as the polynomial
where
and
are (respectively) the minimum and the maximum of
, where
is the rank function of
(normalized to satisfy
), and where
is the rank of
. (Note that the indeterminate
doesn’t actually appear in the polynomial.)
For technical reasons, the polynomial is returned in the slightly larger ring
by this method.
See Wikipedia article h-vector.
See also
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 sage: P = Poset({2: [3]}) sage: P.flag_f_polynomial() x1 sage: P = Poset({2: []}) sage: P.flag_f_polynomial() 1
-
flag_h_polynomial
()¶ Return the flag
-polynomial of a bounded and ranked poset
self
.If
is a bounded ranked poset whose maximal element has rank
(where the minimal element is set to have rank
), then the flag
-polynomial of
is defined as the polynomial
where
is the flag
-polynomial of
(see
flag_f_polynomial()
).For technical reasons, the polynomial is returned in the slightly larger ring
by this method.
See Wikipedia article h-vector.
See also
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 sage: P = Poset({2: [3]}) sage: P.flag_h_polynomial() x1 sage: P = Poset({2: []}) sage: P.flag_h_polynomial() 1
-
frank_network
()¶ Computes Frank’s network of the poset
self
. This is defined in Section 8 of [BF1999].OUTPUT:
A pair
, where
is Frank’s network of
encoded as a
DiGraph
, andis 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
is a certain directed graph with
vertices, defined in Section 8 of [BF1999]. Its set of vertices consists of two vertices
and
for each element
of
, as well as two vertices
and
. (These notations are not the ones used in [BF1999]; see the table below for their relation.) The edges are:
- for each
in
, an edge from
to
;
- for each
in
, an edge from
to
;
- for each
and
in
such that
, an edge from
to
.
We make this digraph into a network in the sense of flow theory as follows: The vertex
is considered as the source of this network, and the vertex
as the sink. The cost function is defined to be
on the edge from
to
for each
, and to be
on every other edge. The capacity is
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)
REFERENCES:
[BF1999] (1, 2, 3, 4, 5) Thomas Britz, Sergey Fomin, Finite posets and Ferrers shapes, Advances in Mathematics 158, pp. 86-127 (2001), Arxiv math/9912126 (the arXiv version has less errors). 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)
- for each
-
ge
(x, y)¶ Returns
True
ifis greater than or equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_gequal(x,y) False sage: Q.is_gequal(y,x) False sage: Q.is_gequal(x,z) False sage: Q.is_gequal(z,x) True sage: Q.is_gequal(z,y) True sage: Q.is_gequal(z,z) True
-
graphviz_string
(graph_string='graph', edge_string='--')¶ Returns a representation in the DOT language, ready to render in graphviz.
REFERENCES:
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"; }
-
greene_shape
()¶ Return the Greene-Kleitman partition of
self
.The Greene-Kleitman partition of a finite poset
is the partition
, where
is the maximum cardinality of a union of
chains of
. Equivalently, this is the conjugate of the partition
, where
is the maximum cardinality of a union of
antichains of
.
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)
-
gt
(x, y)¶ Returns
True
ifis greater than but not equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_greater_than(x,y) False sage: Q.is_greater_than(y,x) False sage: Q.is_greater_than(x,z) False sage: Q.is_greater_than(z,x) True sage: Q.is_greater_than(z,y) True sage: Q.is_greater_than(z,z) False
-
h_polynomial
()¶ Return the
-polynomial of a bounded poset
self
.This is the
-polynomial of the order complex of the poset minus its bounds.
This is related to the
-polynomial by a simple change of variables:
where
and
denote the
-polynomial and the
-polynomial, respectively.
See Wikipedia article h-vector.
See also
is_bounded()
,f_polynomial()
,order_complex()
,sage.homology.simplicial_complex.SimplicialComplex.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
-
has_bottom
()¶ Return
True
if the poset has a unique minimal element, andFalse
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
-
has_isomorphic_subposet
(other)¶ Return
True
if the poset contains a subposet isomorphic toother
.By subposet we mean that there exist a set
X
of elements such thatself.subposet(X)
is isomorphic toother
.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
-
has_top
()¶ Return
True
if the poset has a unique maximal element, andFalse
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:[1],1:[]}) sage: Q.has_top() True
See also
-
hasse_diagram
(wrapped=True)¶ Return the Hasse diagram of
self
as a SageDiGraph
. Ifdot2tex
is installed, then this sets the Hasse diagram’s latex options to use thedot2tex
formatting.Todo
Should the vertices of the diagram have the poset as parent?
EXAMPLES:
sage: Q = Poset({5:[2,3], 1:[3,4], 2:[0], 3:[0], 4:[0]}, facade = False) sage: Q.hasse_diagram() Digraph on 6 vertices sage: P = Poset({'a':['b'],'b':['d'],'c':['d'],'d':['f'],'e':['f'],'f':[]}, facade = False) sage: H = P.hasse_diagram() sage: P.cover_relations() [[e, f], [c, d], [a, b], [b, d], [d, f]] sage: H.edges() [(a, b, None), (c, d, None), (b, d, None), (e, f, None), (d, f, None)] sage: P = Poset((divisors(15), attrcall("divides")), facade = False) sage: H = P.hasse_diagram() sage: H.vertices() [1, 5, 3, 15] sage: H.edges() [(1, 3, None), (1, 5, None), (5, 15, None), (3, 15, None)] sage: H.set_latex_options(format="dot2tex") # optional - dot2tex sage: view(H, tight_page=True) # optional - dot2tex, not tested (opens external window)
-
height
()¶ Return the height (number of elements in the longest chain) of the poset.
EXAMPLES:
sage: P = Poset({0:[1],2:[3,4],4:[5,6]}) sage: P.height() 3 sage: Posets.PentagonPoset().height() 4 sage: Poset({}).height() 0
-
incidence_algebra
(R, prefix='I')¶ Return the incidence algebra of
self
overR
.EXAMPLES:
sage: P = posets.BooleanLattice(4) sage: P.incidence_algebra(QQ) Incidence algebra of Finite lattice containing 16 elements over Rational Field
-
incomparability_graph
()¶ Returns the incomparability graph of
self
.This is the complement of the comparability graph.
EXAMPLES:
sage: p = posets.ChainPoset(4) sage: p.incomparability_graph().size() 0 sage: p = posets.DiamondPoset(5) sage: g = p.incomparability_graph(); g Incomparability graph on 5 vertices sage: g.size() 3
-
interval
(x, y)¶ Return a list of the elements
such that
.
INPUT:
x
– any element of the posety
– 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]
-
intervals
()¶ Returns a list of all relations of the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals 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.
Pairs are produced in a rough sort of lexicographic order, where earlier elements are from lower levels of the poset.
See also
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: Q.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]]
AUTHOR:
- Rob Beezer (2011-05-04)
-
intervals_iterator
(strict=False)¶ Returns an iterator for all the relations of the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.
INPUT:
strict
– boolean (defaultFalse
) ifTrue
, returns an iterator over relations, excluding all relations
.
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.
See also
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(Q.relations_iterator()) <type 'generator'> sage: [z for z in Q.relations_iterator()] [[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]] 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]] sage: len(list(P.relations_iterator())) 13
AUTHOR:
- Rob Beezer (2011-05-04)
-
intervals_number
()¶ Return the number of relations in the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.
See also
EXAMPLES:
sage: from sage.combinat.tamari_lattices import TamariLattice sage: TamariLattice(4).relations_number() 68 sage: P = posets.BooleanLattice(3) sage: P.relations_number() 27
-
is_EL_labelling
(f, return_raising_chains=False)¶ Returns
True
iff
is an EL labelling ofself
.A labelling
of the edges of the Hasse diagram of a poset is called an EL labelling (edge lexicographic labelling) if for any two elements
and
with
,
- there is a unique
-raising chain from
to
in the Hasse diagram, and this chain is lexicographically first among all chains from
to
.
For more details, see [Bj1980].
INPUT:
f
– a function taking two elementsa
andb
inself
such thatb
coversa
and returning elements in a totally ordered set.return_raising_chains
(optional; default:False
) ifTrue
, returns the set of all raising chains inself
, 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]}
REFERENCES:
[Bj1980] Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159-183, doi:10.1090/S0002-9947-1980-0570784-2 - there is a unique
-
is_bounded
()¶ Return
True
if the posetself
is bounded, andFalse
otherwise.We call a poset bounded if it contains 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 = Poset({0:[1],1:[]}) sage: Q.is_bounded() True
-
is_chain
()¶ Returns True if the poset is totally ordered, and False otherwise.
EXAMPLES:
sage: L = Poset({0:[1],1:[2],2:[3],3:[4]}) sage: L.is_chain() True sage: V = Poset({0:[1,2]}) sage: V.is_chain() False
-
is_chain_of_poset
(o, ordered=False)¶ Return whether an iterable
o
is a chain ofself
, including a check foro
being ordered from smallest to largest element if the keywordordered
is set toTrue
.INPUT:
o
– an iterable (e. g., list, set, or tuple) containing some elements ofself
ordered
– a Boolean (default:False
) which decides whether the notion of a chain includes being ordered
OUTPUT:
If
ordered
is set toFalse
, the truth value of the following assertion is returned: The subset ofself
formed by the elements ofo
is a chain inself
.If
ordered
is set toTrue
, the truth value of the following assertion is returned: Every element of the listo
is (strictly!) smaller than its successor inself
. (This makes no sense ifordered
is a set.)EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides"))) sage: sorted(P.list()) [1, 2, 3, 4, 6, 12] sage: P.is_chain_of_poset([2, 4]) True sage: P.is_chain_of_poset([12, 6]) True sage: P.is_chain_of_poset([12, 6], ordered=True) False sage: P.is_chain_of_poset([6, 12], ordered=True) True sage: P.is_chain_of_poset(()) True sage: P.is_chain_of_poset((), ordered=True) True sage: P.is_chain_of_poset((3, 4, 12)) False sage: P.is_chain_of_poset((3, 6, 12, 1)) True sage: P.is_chain_of_poset((3, 6, 12, 1), ordered=True) False sage: P.is_chain_of_poset((3, 6, 12), ordered=True) True 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 sage: P.is_chain_of_poset((6, 1, 1, 3)) True sage: P.is_chain_of_poset((2, 1, 1, 3)) False
-
is_connected
()¶ Return
True
if the poset is connected, andFalse
otherwise.Poset is not connected if it can be divided to disjoint parts
and
so that every element of
is incomparable to every element of
.
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
-
is_gequal
(x, y)¶ Returns
True
ifis greater than or equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_gequal(x,y) False sage: Q.is_gequal(y,x) False sage: Q.is_gequal(x,z) False sage: Q.is_gequal(z,x) True sage: Q.is_gequal(z,y) True sage: Q.is_gequal(z,z) True
-
is_graded
()¶ Returns whether this poset is graded.
A poset is graded if all its maximal chains have the same length. There are various competing definitions for graded posets (see Wikipedia article Graded_poset). This definition is from section 3.1 of Richard Stanley’s Enumerative Combinatorics, Vol. 1 [EnumComb1].
Note that every graded poset is ranked, but the converse is not true.
See also
EXAMPLES:
sage: P = Poset([[1],[2],[3],[4],[]]) sage: P.is_graded() True sage: Q = Poset([[1,5],[2,6],[3],[4],[],[6,3],[4]]) sage: Q.is_graded() False sage: P = Poset( ([1,2,3,4],[[1,2],[2,4],[3,4]] )) sage: P.is_graded() False sage: P = Poset({1: [2, 3], 4: [5]}) sage: P.is_graded() True sage: P = Poset({1: [2, 3], 3: [4]}) sage: P.is_graded() False sage: P = Poset({1: [2, 3], 4: []}) sage: P.is_graded() False sage: P = Posets.BooleanLattice(4) sage: P.is_graded() True sage: P = RootSystem(['D',4]).root_poset() sage: P.is_graded() True sage: P = Poset({}) sage: P.is_graded() True
TESTS:
Here we test that the empty poset is graded:
sage: Poset([[],[]]).is_graded() True
-
is_greater_than
(x, y)¶ Returns
True
ifis greater than but not equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_greater_than(x,y) False sage: Q.is_greater_than(y,x) False sage: Q.is_greater_than(x,z) False sage: Q.is_greater_than(z,x) True sage: Q.is_greater_than(z,y) True sage: Q.is_greater_than(z,z) False
-
is_incomparable_chain_free
(m, n=None)¶ Return
True
if the poset is-free (that is, there is no pair of incomparable chains of lengths
and
), and
False
if not.If
m
is a tuple of pairs of chain lengths, returnsTrue
if the poset does not contain a pair of incomparable chains whose lengths comprise one of the chain pairs, andFalse
if not. A poset is-free if it contains no induced subposet that is isomorphic to the poset consisting of two disjoint chains of lengths
and
. See, for example, Exercise 15 in Chapter 3 of [EnumComb1].
INPUT:
m
- tuple of pairs of nonnegative integersm
,n
- nonnegative integers
EXAMPLES:
sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: P.is_incomparable_chain_free(1, 1) False sage: P.is_incomparable_chain_free(2, 1) True
sage: P = Poset(((0, 1, 2, 3, 4), ((0, 1), (1, 2), (0, 3), (4, 2)))) sage: P.is_incomparable_chain_free(((3, 1), (2, 2))) True
sage: P = Poset((("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"), (("d", "a"), ("e", "a"), ("f", "a"), ("g", "a"), ("h", "b"), ("f", "b"), ("h", "c"), ("g", "c"), ("h", "d"), ("i", "d"), ("h", "e"), ("i", "e"), ("j", "f"), ("i", "f"), ("j", "g"), ("i", "g"), ("j", "h")))) sage: P.is_incomparable_chain_free(3, 1) True sage: P.is_incomparable_chain_free(2, 2) False
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]
TESTS:
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 nonnegative 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)
REFERENCES:
[EnumComb1] (1, 2, 3, 4, 5, 6) Richard P. Stanley, Enumerative Combinatorics, volume 1, Second Edition, Cambridge University Press (2011). http://math.mit.edu/~rstan/ec/ec1/
-
is_isomorphic
(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
-
is_join_semilattice
()¶ Returns True if the poset has a join operation, and False otherwise.
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,2],[3],[3],[]]) sage: P.is_join_semilattice() True sage: P = Poset({0:[2,3],1:[2,3]}) sage: P.is_join_semilattice() False
-
is_lequal
(x, y)¶ Returns
True
ifis less than or equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_lequal(x,y) False sage: Q.is_lequal(y,x) False sage: Q.is_lequal(x,z) True sage: Q.is_lequal(y,z) True sage: Q.is_lequal(z,z) True
-
is_less_than
(x, y)¶ Returns
True
ifis less than but not equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_less_than(x,y) False sage: Q.is_less_than(y,x) False sage: Q.is_less_than(x,z) True sage: Q.is_less_than(y,z) True sage: Q.is_less_than(z,z) False
-
is_linear_extension
(l)¶ Returns whether
l
is a linear extension ofself
INPUT:
l
– a list (or iterable) containing all of the elements ofself
exactly once
See also
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
LinearExtensionsOfPosets
TESTS:
Check that trac ticket #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
-
is_meet_semilattice
()¶ Returns True if self has a meet operation, and False otherwise.
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False) sage: P.is_meet_semilattice() True sage: P = Poset([[1,2],[3],[3],[]]) sage: P.is_meet_semilattice() True sage: P = Poset({0:[2,3],1:[2,3]}) sage: P.is_meet_semilattice() False
-
is_parent_of
(x)¶ 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_ranked
()¶ Returns whether this poset is ranked.
A poset is ranked if it admits a rank function. For more information about the rank function, see
rank_function()
.See also
EXAMPLES:
sage: P = Poset([[1],[2],[3],[4],[]]) sage: P.is_ranked() True sage: Q = Poset([[1,5],[2,6],[3],[4],[],[6,3],[4]]) sage: Q.is_ranked() False sage: P = Poset( ([1,2,3,4],[[1,2],[2,4],[3,4]] )) sage: P.is_ranked() True
-
is_slender
()¶ Return
True
if the poset is slender, andFalse
otherwise.A finite graded poset is called 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
-Lattice on the Poset
”, 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,
,
,
and
such that
where
is the covering relation.
EXAMPLES:
sage: P = Poset(([1,2,3,4],[[1,2],[1,3],[2,4],[3,4]]), facade = True) 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]]), facade = True) 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
-
isomorphic_subposets
(other)¶ Return a list of subposets of
isomorphic to
.
By subposet we mean
self.subposet(X)
which is isomorphic toother
and whereX
is a subset of elements ofself
.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
isomorphic_subposets_iterator()
.
-
isomorphic_subposets_iterator
(other)¶ Return an iterator over the subposets of
isomorphic to
.
By subposet we mean
self.subposet(X)
which is isomorphic toother
and whereX
is a subset of elements ofself
.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
subgraph_search_iterator()
returning labelled subgraphs. On the other hand, this function does not eat memory likeisomorphic_subposets()
does.
-
join_matrix
()¶ Deprecated as a function of posets, moved to lattices.
Convert a poset
to join-semilattice and use it like
JoinSemilattice(P).join_matrix()
.
-
le
(x, y)¶ Returns
True
ifis less than or equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_lequal(x,y) False sage: Q.is_lequal(y,x) False sage: Q.is_lequal(x,z) True sage: Q.is_lequal(y,z) True sage: Q.is_lequal(z,z) True
-
lequal_matrix
(ring=Integer Ring, sparse=False)¶ Computes the matrix whose
(i,j)
entry is 1 ifself.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
-
level_sets
()¶ Return a list
l
such thatl[i]
is the set of minimal elements of the poset obtained fromself
by removing the elements inl[0], l[1], ..., l[i-1]
. (In particular,l[0]
is the set of minimal elements ofself
.)EXAMPLES:
sage: P = Poset({0:[1,2],1:[3],2:[3],3:[]}) sage: [len(x) for x in P.level_sets()] [1, 2, 1]
sage: Q = Poset({0:[1,2], 1:[3], 2:[4], 3:[4]}) sage: [len(x) for x in Q.level_sets()] [1, 2, 1, 1]
-
linear_extension
(linear_extension=None, check=True)¶ Return a linear extension of this poset.
A linear extension of a finite poset
of size
is a total ordering
of its elements such that
whenever
in the poset
.
INPUT:
linear_extension
– (default:None
) a list of the elements ofself
check
– a boolean (default: True); whether to check thatlinear_extension
is indeed a linear extension ofself
.
See also
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]
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
-
linear_extensions
(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 listsWarning
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
See also
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
:
sage: type(l.parent()) <class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category'>
With
facade=True
, the elements ofL
are plain lists instead:sage: L = P.linear_extensions(facade=True) sage: l = L.an_element() sage: type(l) <type '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]) <type 'list'>
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]]
-
list
()¶ List the elements of the poset. This just returns the result of
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.elements.FinitePoset_with_category.element_class'>
-
lower_covers
(y)¶ Returns a list of lower covers of the element y. An lower cover of y is an element x such that y x is a cover relation.
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: [Q.lower_covers(_) for _ in Q.list()] [[], [], [1, 0], [2], [3]]
-
lower_covers_iterator
(y)¶ Returns an iterator for the lower covers of the element y. An lower cover of y is an element x such that y x is a cover relation.
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(Q.lower_covers_iterator(0)) <type 'generator'>
-
lt
(x, y)¶ Returns
True
ifis less than but not equal to
in the poset, and
False
otherwise.EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = Q(0),Q(1),Q(4) sage: Q.is_less_than(x,y) False sage: Q.is_less_than(y,x) False sage: Q.is_less_than(x,z) True sage: Q.is_less_than(y,z) True sage: Q.is_less_than(z,z) False
-
maximal_antichains
()¶ Return all maximal antichains of the poset.
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]]
See also
-
maximal_chains
(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]]
See also
-
maximal_elements
()¶ 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]
See also
-
meet_matrix
()¶ Deprecated as a function of posets, moved to lattices.
Convert a poset
to meet-semilattice and use it like
MeetSemilattice(P).join_matrix()
.
-
minimal_elements
()¶ 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
See also
-
mobius_function
(x, y)¶ Returns the value of the Mobius function of the poset on the elements x and y.
EXAMPLES:
sage: P = Poset([[1,2,3],[4],[4],[4],[]]) sage: P.mobius_function(P(0),P(4)) 2 sage: sum([P.mobius_function(P(0),v) for v in P]) 0 sage: sum([abs(P.mobius_function(P(0),v)) \ ....: for v in P]) 6 sage: for u,v in P.cover_relations_iterator(): ....: if P.mobius_function(u,v) != -1: ....: print "Bug in mobius_function!"
sage: Q = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]) sage: Q.mobius_function(Q(0),Q(7)) 0 sage: Q.mobius_function(Q(0),Q(5)) 0 sage: Q.mobius_function(Q(2),Q(7)) 2 sage: Q.mobius_function(Q(3),Q(3)) 1 sage: sum([Q.mobius_function(Q(0),v) for v in Q]) 0
-
mobius_function_matrix
(ring=Integer Ring, sparse=False)¶ Returns a matrix whose
(i,j)
entry is the value of the Mobius function evaluated atself.linear_extension()[i]
andself.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.mobius_function(x,y) -1 sage: M = P.mobius_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.mobius_function_matrix(ring=QQ, sparse=False).parent() Full MatrixSpace of 5 by 5 dense matrices over Rational Field
-
open_interval
(x, y)¶ Return a list of the elements
such that
.
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,[5,6,4])) sage: I == set(P.open_interval(2,7)) True
sage: dg = DiGraph({"a":["b","c"], "b":["d"], "c":["d"]}) sage: P = Poset(dg, facade = False) sage: P.open_interval("a","d") [b, c]
-
order_complex
(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)
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 labelledin 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)}
-
order_filter
(elements)¶ Returns the order filter generated by the elements of an iterable
elements
.is an order filter if, for any
in
and
such that
, then
is in
.
EXAMPLES:
sage: B = Posets.BooleanLattice(4) sage: B.order_filter([3,8]) [3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
-
order_ideal
(elements)¶ Returns the order ideal generated by the elements of an iterable
elements
.is an order ideal if, for any
in
and
such that
, then
is in
.
EXAMPLES:
sage: B = Posets.BooleanLattice(4) sage: B.order_ideal([7,10]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 10] sage: B.order_ideal(iter(range(4, 9))) [0, 1, 2, 3, 4, 5, 6, 7, 8]
-
order_polynomial
()¶ Return the order polynomial of
self
.The order polynomial
of a poset
is defined as the unique polynomial
such that for each integer
,
is the number of order-preserving maps from
to
.
See sections 3.12 and 3.15 of [EnumComb1], and also [St1986].
See also
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]
-
order_polytope
()¶ Return the order polytope of the poset
self
.The order polytope of a finite poset
is defined as the subset of
consisting of all maps
satisfying
and
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 QQ^3 defined as the convex hull of 8 vertices sage: P = posets.PentagonPoset() sage: Q = P.order_polytope();Q A 5-dimensional polyhedron in QQ^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
REFERENCES:
[St1986] (1, 2, 3, 4) Richard Stanley. Two poset polytopes, Discrete Comput. Geom. (1986), doi:10.1007/BF02187680
-
ordinal_product
(other, labels='pairs')¶ Return the ordinal product of
self
andother
.The ordinal product of two posets
and
is a partial order on the cartesian product of the underlying sets of
and
, defined as follows (see [EnumComb1], p. 284).
In the ordinal product,
if either
or
and
.
This construction is not symmetric in
and
.
INPUT:
other
– a posetlabels
– either'integers'
or'pairs'
(default); how the resulting poset will be labeled
See also
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')]]
TESTS:
sage: P1.ordinal_product(24) Traceback (most recent call last): ... ValueError: the input 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'
-
ordinal_sum
(other, labels='pairs')¶ Return a poset or (semi)lattice isomorphic to ordinal sum of the poset with
other
.The ordinal sum of
and
is a poset that contains every element and relation from both
and
, and where every element of
is smaller than every element of
.
Mathematically, it is only defined when
and
have no common element; here we force that by giving them different names in the resulting poset.
The ordinal sum on lattices is lattice; resp. for meet- and join-semilattices. Hence we check if we can return (semi)lattice instead of plain poset.
INPUT:
other
, a poset.labels
- (defaults to ‘pairs’) If set to ‘pairs’, each elementv
in this poset will be named(0,v)
and each elementu
inother
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
See also
-
p_partition_enumerator
(tup, R, check=False)¶ Return a
-partition enumerator of
self
.Given a total order
on the elements of a finite poset
(the order of
and the total order
can be unrelated; in particular, the latter does not have to extend the former), a
-partition enumerator is the quasisymmetric function
, where the first sum is taken over all
-partitions
.
A
-partition is a function
satisfying the following properties for any two elements
and
of
satisfying
:
- if
then
,
- if
then
.
INPUT:
tup
– the tuple containing all elements of(each of them exactly once), in the order dictated by the total order
R
– a commutative ring
OUTPUT:
The
-partition enumerator of
self
according totup
in the algebraof quasisymmetric functions over the base ring
.
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[]
- if
-
plot
(label_elements=True, element_labels=None, layout='acyclic', cover_labels=None, **kwds)¶ 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 vertices.
INPUT:
label_elements
(default:True
) - whether to display element labelselement_labels
(default:None
) - a dictionary of element labelscover_labels
- a dictionary, list or function representing labels of the covers ofself
. When set toNone
(default) no label is displayed on the edges of the Hasse Diagram.layout
– the type of layout used to display the Diagram. Set to'acyclic'
by default (seeGenericGraph.plot
for more information).
Note
All options of
GenericGraph.plot
are also available through this function.EXAMPLES:
sage: D = Poset({ 1:[2,3], 2:[4], 3:[4,5] }) sage: D.plot(label_elements=False) Graphics object consisting of 6 graphics primitives sage: D.plot() Graphics object consisting of 11 graphics primitives sage: type(D.plot()) <class 'sage.plot.graphics.Graphics'> sage: elm_labs = {1:'a', 2:'b', 3:'c', 4:'d', 5:'e'} sage: D.plot(element_labels=elm_labs) Graphics object consisting of 11 graphics primitives
Plot of a ranked poset:
sage: P = Poset(DiGraph('E@ACA@?')) sage: P.is_ranked() True sage: P.plot() Graphics object consisting of 12 graphics primitives
The keyword
cover_labels
can be used to decorate edges:sage: P = posets.ChainPoset(3) sage: P.plot(cover_labels=lambda a, b: a + b) Graphics object consisting of 8 graphics primitives sage: P = Poset({0: [1,2]}) sage: P.plot(cover_labels={(0,1): 'here', (0,2): 'there'}) Graphics object consisting of 8 graphics primitives sage: P = Poset({2: [1], 0: [1]}) sage: P.plot(cover_labels=[(2,1,'da'), (0,1,'niet')]) Graphics object consisting of 8 graphics primitives
TESTS:
We check that
label_elements
andelement_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)) ['0', '1', '2', '3', '4'] sage: element_labels = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'} sage: get_plot_labels(P1.plot(element_labels=element_labels)) ['a', 'b', 'c', 'd', 'e'] sage: get_plot_labels(P2.plot(element_labels=element_labels)) ['a', 'b', 'c', 'd', 'e']
Plot of the empy poset:
sage: P = Poset({}) sage: P.plot() Graphics object consisting of 0 graphics primitives
-
product
(other)¶ Return the cartesian product of
self
andother
.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.hasse_diagram().edges()) 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
-
promotion
(i=1)¶ Compute the (extended) promotion on the linear extension of the poset
self
.INPUT:
i
– an integer betweenand
(default:
)
OUTPUT:
- an isomorphic poset, with the same default linear extension
The extended promotion is defined on a poset
self
of sizeby applying the promotion operator
to the default linear extension
of
self
(seepromotion()
), and relabelingself
accordingly. For more details see [Stan2009].When the vertices of the poset
self
are labelled by, the linear extension is the identity, and
, the above algorithm corresponds to the promotion operator on posets defined by Schützenberger as follows. Remove
from
self
and replace it by the minimumof all labels covering
in the poset. Then, remove
and replace it by the minimum of all labels covering
, and so on. This process ends when a label is a local maximum. Place the label
at this vertex. Finally, decrease all labels by
.
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
:
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]]
See also
linear_extension()
with_linear_extension()
and thelinear_extension
option ofPoset()
promotion()
evacuation()
AUTHOR:
- Anne Schilling (2012-02-18)
-
random_order_ideal
(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 ifdirection='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
REFERENCES:
[Propp1997] James Propp, Generating Random Elements of Finite Distributive Lattices, Electron. J. Combin. 4 (1997), no. 2, The Wilf Festschrift volume, Research Paper 15.
-
random_subposet
(p)¶ Return a random subposet that contains each element with probability
p
.EXAMPLES:
sage: P = Posets.BooleanLattice(3) sage: set_random_seed(0) sage: Q = P.random_subposet(0.5) sage: Q.cover_relations() [[0, 2], [0, 5], [2, 3], [3, 7], [5, 7]]
-
rank
(element=None)¶ Return the rank of an element
element
in the posetself
, or the rank of the poset ifelement
isNone
.(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)]
-
rank_function
()¶ Return the (normalized) rank function of the poset, if it exists.
A rank function of a poset
is a function
that maps elements of
to integers and satisfies:
if
covers
. The function
is normalized such that its minimum value on every connected component of the Hasse diagram of
is
. This determines the function
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
-
relabel
(relabeling)¶ Return a copy of this poset with its elements relabelled.
INPUT:
relabeling
– a function or dictionnaryThis function should map each (non-wrapped) element of
self
to some distinct object.
EXAMPLES:
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True, facade = False) 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: 12/x) sage: Q.list() [12, 6, 4, 3, 2, 1] sage: Q.cover_relations() [[12, 6], [12, 4], [6, 3], [6, 2], [4, 2], [3, 1], [2, 1]]
Here we relabel the elements of a poset by
, 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)}; 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:sage: P = Poset((divisors(12), attrcall("divides")), facade = True, linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: Q = P.relabel(lambda x: 12/x) sage: Q.list() [12, 6, 4, 3, 2, 1] sage: Q.cover_relations() [[12, 6], [12, 4], [6, 3], [6, 2], [4, 2], [3, 1], [2, 1]]
Relabeling a (semi)lattice gives a (semi)lattice:
sage: P=JoinSemilattice({0:[1]}) sage: type(P.relabel(lambda n: n+1)) <class ‘sage.combinat.posets.lattices.FiniteJoinSemilattice_with_category’>Note
As can be seen in the above examples, the default linear extension of
Q
is that ofP
after relabeling. In particular,P
andQ
share the same internal Hasse diagram.TESTS:
The following checks that trac ticket #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
-
relations
()¶ Returns a list of all relations of the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals 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.
Pairs are produced in a rough sort of lexicographic order, where earlier elements are from lower levels of the poset.
See also
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: Q.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]]
AUTHOR:
- Rob Beezer (2011-05-04)
-
relations_iterator
(strict=False)¶ Returns an iterator for all the relations of the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.
INPUT:
strict
– boolean (defaultFalse
) ifTrue
, returns an iterator over relations, excluding all relations
.
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.
See also
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(Q.relations_iterator()) <type 'generator'> sage: [z for z in Q.relations_iterator()] [[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]] 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]] sage: len(list(P.relations_iterator())) 13
AUTHOR:
- Rob Beezer (2011-05-04)
-
relations_number
()¶ Return the number of relations in the poset.
A relation is a pair of elements
and
such that
in
self
.Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.
See also
EXAMPLES:
sage: from sage.combinat.tamari_lattices import TamariLattice sage: TamariLattice(4).relations_number() 68 sage: P = posets.BooleanLattice(3) sage: P.relations_number() 27
-
show
(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 labelselement_labels
(default:None
) - a dictionary of element labelscover_labels
- a dictionary, list or function representing labels of the covers ofself
. When set toNone
(default) no label is displayed on the edges of the Hasse Diagram.
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)
-
subposet
(elements)¶ Return the poset containing elements with partial order induced by that of
self
.EXAMPLES:
sage: P = Poset({"a":["c","d"], "b":["d","e"], "c":["f"], "d":["f"], "e":["f"]}, facade = False) 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 facade poset is again a facade poset:
sage: P = Poset({"a":["c","d"], "b":["d","e"], "c":["f"], "d":["f"], "e":["f"]}, facade=True) sage: Q = P.subposet(["a","b","f"]); Q Finite poset containing 3 elements sage: Q.cover_relations() [['b', 'f'], ['a', 'f']]
One may specified wrapped elements or not:
sage: P = Poset({"a":["c","d"], "b":["d","e"], "c":["f"], "d":["f"], "e":["f"]}, facade = False) sage: Q = P.subposet([P("a"),P("b"),P("f")]); Q Finite poset containing 3 elements sage: Q.cover_relations() [[b, f], [a, f]] sage: B = posets.BooleanLattice(2) sage: above = B.principal_order_filter(0) sage: Q = B.subposet(above) sage: above_new = Q.principal_order_filter(Q.list()[0]) sage: Q.subposet(above_new) Finite poset containing 4 elements
TESTS:
sage: P.subposet(("a","b","f")) Finite poset containing 3 elements sage: P.subposet(["a","b","x"]) Traceback (most recent call last): ... ValueError: <type '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
-
to_graph
(*args, **kwds)¶ Deprecated: Use
cover_relations_graph()
instead. See trac ticket #17449 for details.
-
top
()¶ 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
TESTS:
sage: R = Poset([[0],[]]) sage: R.list() [0] sage: R.top() #Trac #10776 0
-
unwrap
(element)¶ Return the element
element
of the posetself
in unwrapped form.INPUT:
element
– an element ofself
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.
-
upper_covers
(y)¶ Returns a list of upper covers of the element y. An upper cover of y is an element x such that y x is a cover relation.
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: [Q.upper_covers(_) for _ in Q.list()] [[2], [2], [3], [4], []]
-
upper_covers_iterator
(y)¶ Returns an iterator for the upper covers of the element y. An upper cover of y is an element x such that y x is a cover relation.
EXAMPLES:
sage: Q = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: type(Q.upper_covers_iterator(0)) <type 'generator'>
-
width
()¶ Return the width of the poset (the size of its longest antichain).
It is computed through a matching in a bipartite graph. See Wikipedia article Dilworth’s_theorem for more information.
See also
dilworth_decomposition()
– return a partition of the poset into the smallest number of chains.EXAMPLE:
sage: p = posets.BooleanLattice(4) sage: p.width() 6
-
with_linear_extension
(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]) 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
Note
With the current implementation, this requires relabeling the internal
DiGraph
which is, where
is the number of elements and
the number of cover relations.
-
zeta_polynomial
()¶ Return the zeta polynomial of the poset
self
.The zeta polynomial of a poset is the unique polynomial
such that for every integer
,
is the number of weakly increasing sequences
of elements of the poset.
The polynomial
is integral-valued, but generally doesn’t have integer coefficients. It can be computed as
where
is the number of all chains of length
in the poset.
For more information, see section 3.12 of [EnumComb1].
In particular,
is the number of vertices and
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
-
class
sage.combinat.posets.posets.
FinitePosets_n
(n)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The finite enumerated set of all posets on
vertices, 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]]
-
cardinality
(from_iterator=False)¶ Return the cardinality of this object.
Note
By default, this returns pre-computed values obtained from the On-Line Encyclopedia of Integer Sequences (OEIS sequence 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
-
-
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 lists/tuples/iterables 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 return whetherx
is covered byy
.A dictionary, list or tuple of upper covers:
data[x]
is a list of the elements that cover the elementin the poset.
Warning
If data is a list or tuple of length
, then it is handled by the above case..
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
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
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:
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.
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
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
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
:
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 type(s) for +: 'FinitePoset_with_category.element_class' and 'FinitePoset_with_category.element_class' 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) <type 'str'>
Of course, those strings are not aware of
. So to compare two such strings, one needs to query
:
sage: a < b True sage: P.lt(a,b) False
which models the usual mathematical notation
.
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]) <type '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) <type 'sage.rings.integer.Integer'> sage: P = Poset((divisors(15), attrcall("divides")), facade=True) sage: type(P.an_element()) <type '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.TESTS:
sage: P = Poset([[1,2],[3],[3]]) sage: type(hash(P)) <type 'int'>
Bad input:
sage: Poset([1,2,3], lambda x,y : x<y) Traceback (most recent call last): ... ValueError: 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
-
sage.combinat.posets.posets.
is_poset
(dig)¶ Tests whether a directed graph is acyclic and transitively reduced.
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