This module implements finite partialy 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
antichains_iterator() | Returns an iterator over the antichains of the poset. |
antichains() | Returns the antichains of the poset. |
bottom() | Returns the bottom element of the poset, if it exists. |
cardinality() | Returns the number of elements in the poset. |
chains() | Returns all the chains of self |
chain_polytope() | Returns the chain polytope of the poset. |
closed_interval() | Returns a list of the elements ![]() ![]() |
compare_elements() | Compare ![]() ![]() |
cover_relations_iterator() | Returns an iterator for the cover relations of the poset. |
cover_relations() | Returns the list of pairs [u,v] which are cover relations |
covers() | Returns True if y covers x and False otherwise. |
coxeter_transformation() | Returns the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules |
dual() | Returns the dual poset of the given poset. |
evacuation() | Computes evacuation on the linear extension associated to the poset self. |
graphviz_string() | Returns a representation in the DOT language, ready to render in graphviz. |
has_bottom() | Returns True if the poset has a unique minimal element. |
hasse_diagram() | Returns the Hasse diagram of self as a Sage DiGraph. |
has_top() | Returns True if the poset contains a unique maximal element, and False otherwise. |
interval() | Returns a list of the elements ![]() ![]() |
is_bounded() | Returns True if the poset contains a unique maximal element and a unique minimal element, and False otherwise. |
is_chain() | Returns True if the poset is totally ordered, and False otherwise. |
is_EL_labelling() | Returns whether f is an EL labelling of self |
is_gequal() | Returns True if ![]() ![]() |
is_graded() | Returns whether this poset is graded. |
is_greater_than() | Returns True if ![]() ![]() |
is_isomorphic() | Returns True if both posets are isomorphic. |
is_join_semilattice() | Returns True is the poset has a join operation, and False otherwise. |
is_lequal() | Returns True if ![]() ![]() |
is_less_than() | Returns True if ![]() ![]() |
is_linear_extension() | Returns whether l is a linear extension of self |
is_meet_semilattice() | Returns True if self has a meet operation, and False otherwise. |
join_matrix() | Returns a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the join (least upper bound) of self.linear_extension()[i] and self.linear_extension()[j]. |
is_ranked() | Returns whether this poset is ranked. |
is_slender() | Returns whether the poset self is slender or not. |
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() | Returns 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() | Returns a linear extension of this poset. |
linear_extensions() | Returns 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(). |
lower_covers_iterator() | 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. |
lower_covers() | 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. |
maximal_chains() | Returns all maximal chains of this poset. Each chain is listed in increasing order. |
maximal_elements() | Returns a list of the maximal elements of the poset. |
meet_matrix() | Returns a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the meet (greatest lower bound) of self.linear_extension()[i] and self.linear_extension()[j]. |
minimal_elements() | Returns a list of the minimal elements of the poset. |
mobius_function_matrix() | Returns 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() | Returns the value of the Mobius function of the poset on the elements x and y. |
open_interval() | Returns a list of the elements ![]() ![]() |
order_complex() | Returns the order complex associated to this poset. |
order_filter() | Returns the order filter generated by a list of elements. |
order_ideal() | Returns the order ideal generated by a list of elements. |
order_polytope() | Returns the order polytope of the poset. |
plot() | Returns a Graphic object corresponding the Hasse diagram of the poset. |
product() | Returns the cartesian product of self and other. |
promotion() | Computes the (extended) promotion on the linear extension of the poset self |
random_subposet() | Returns a random subposet that contains each element with probability p. |
rank_function() | Returns a rank function of the poset, if it exists. |
rank() | Returns the rank of an element, or the rank of the poset if element is None. |
relabel() | Returns a copy of this poset with its elements relabelled |
relations_iterator() | Returns an iterator for all the relations of the poset. |
relations() | Returns a list of all relations of the poset. |
show() | Shows the Graphics object corresponding the Hasse diagram of the poset. |
subposet() | Returns the poset containing elements with partial order induced by that of self. |
top() | Returns the top element of the poset, if it exists. |
unwrap() | Unwraps an element of this poset |
upper_covers_iterator() | 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. |
upper_covers() | 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. |
with_linear_extension() | Returns a copy of self with a different default linear extension |
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Constructs a (finite) -element poset from a set of elements and a
directed acyclic graph or poset.
INPUT:
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()
[[0, 2], [0, 3], [2, 1], [3, 1], [4, 1], [5, 3], [5, 4]]
sage: TestSuite(P).run()
sage: P.category()
Category of finite posets
sage: P.__class__
<class 'sage.combinat.posets.posets.FinitePoset_with_category'>
sage: Q = sage.combinat.posets.posets.FinitePoset(P, facade = False); Q
Finite poset containing 6 elements
sage: Q is P
True
We keep the same underlying hasse diagram, but change the elements:
sage: Q = sage.combinat.posets.posets.FinitePoset(P, elements=[1,2,3,4,5,6], facade = False); Q
Finite poset containing 6 elements
sage: Q.cover_relations()
[[1, 3], [1, 4], [3, 2], [4, 2], [5, 2], [6, 4], [6, 5]]
We test the facade argument:
sage: P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade = False)
sage: P.category()
Category of finite posets
sage: parent(P[0]) is P
True
sage: Q = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade = True)
sage: Q.category()
Category of facade finite posets
sage: parent(Q[0]) is str
True
sage: TestSuite(Q).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented
Changing a non facade poset to a facade poset:
sage: PQ = Poset(P, facade = True)
sage: PQ.category()
Category of facade finite posets
sage: parent(PQ[0]) is str
True
sage: PQ is Q
True
Changing a facade poset to a non facade poset:
sage: QP = Poset(Q, facade = False)
sage: QP.category()
Category of finite posets
sage: parent(QP[0]) is QP
True
Note
A class that inherits from this class needs to define Element. This is the class of the elements that the inheriting class contains. For example, for this class, FinitePoset, Element is PosetElement. It can also define _dual_class which is the class of dual posets of this class. E.g. FiniteMeetSemilattice._dual_class is FiniteJoinSemilattice.
TESTS:
Equality is derived from 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]]
alias of PosetElement
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([]), set([0]), set([1]), set([2])]
Note
this function used to return a list; this change is slightly backward incompatible; e.g. len(A) does not work.
Note
Internally, this uses sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets and SearchForest. At this point, iterating through this set is about twice slower than using antichains_iterator() (tested on posets.AntichainPoset(15)). The algorithm is the same (depth first search through the tree), but antichains_iterator() manually inlines things which apparently avoids some infrastructure overhead.
On the other hand, this returns a full featured enumerated set, with containment testing, etc.
Returns an iterator over the antichains of the poset.
EXAMPLES:
sage: Posets.PentagonPoset().antichains_iterator()
<generator object antichains_iterator at ...>
See also
Returns the bottom 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
Returns the number of elements in the poset.
EXAMPLES:
sage: Poset([[1,2,3],[4],[4],[4],[]]).cardinality()
5
Returns the chain polytope of the poset
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
Returns all the chains of self
INPUT:
- element_constructor – a function taking an iterable as argument (default: list)
OUTPUT: an enumerated set
A chain of a poset is a collection 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]]
Eventually the following syntax will be accepted:
sage: A.subset(size = 2) # todo: not implemented
See also
Returns a list of the elements such that
.
The order is that induced by the ordering in
self.linear_extension().
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
Compare and
in the poset.
If x = y, then 0 is returned; if x < y, then -1 is returned; if x > y, then 1 is returned; and if x and y are not comparable, then None 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)
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]]
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]]
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
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
Returns the dual poset of the given poset.
EXAMPLE:
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()
Category of facade finite lattice posets
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'>
Computes evacuation on the linear extension associated to the poset self.
OUTPUT:
Evacuation is defined on a poset self of size by
applying the evacuation operator
,
to the default linear extension
of self
(see evacuation()),
and relabelling self accordingly. For more details see [Stan2009].
See also
REFERENCES:
[Stan2009] 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]]), facade = False)
sage: P.evacuation()
Finite poset containing 2 elements
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
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
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
sage: Q.cover_relations()
[[1, 3], [1, 5], [3, 15], [5, 15]]
AUTHOR:
Returns True if is 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
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";
}
Returns True if is 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
Returns True if the poset has a unique minimal element.
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
Returns True if the poset contains a unique maximal element, and False otherwise.
EXAMPLES:
sage: P = Poset({0:[3],1:[3],2:[3],3:[4,5],4:[],5:[]})
sage: P.has_top()
False
sage: Q = Poset({0:[1],1:[]})
sage: Q.has_top()
True
Returns the Hasse diagram of self as a Sage DiGraph.
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
sage: view(H, tight_page=True, pdflatex = True) # optional
Returns a list of the elements such that
.
The order is that induced by the ordering in
self.linear_extension().
INPUT:
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, c, b, d]
Returns an iterator over all pairs in self.
EXAMPLES:
sage: list(Posets.PentagonPoset().interval_iterator())
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 4]]
See also
Returns True if f is an EL labelling of self.
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:
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, 1), (1, 1)): [0], ((1, 0), (1, 1)): [1], ((0, 0), (1, 1)): [0, 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
Returns True if the poset contains a unique maximal element and a unique minimal element, and False otherwise.
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
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
Returns True if is 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
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.
See also
Todo
The current algorithm has exponential complexity (in time and memory). Someone should really implement a better algorithm. See trac ticket #13223.
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
TESTS:
Here we test that the empty poset is graded:
sage: Poset([[],[]]).is_graded()
True
Returns True if is 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
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
Returns True is 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
Returns True if is 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
Returns True if is 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
Returns whether l is a linear extension of self
INPUT:
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
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
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
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
Returns whether the poset self is slender or not.
It is assumed for this method that self is a finite graded poset.
A finite poset is called slender if every rank 2 interval contains three
or four elements. See [Sta2009].
REFERENCES:
[Sta2009] 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,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
Returns a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the join (least upper bound) of self.linear_extension()[i] and self.linear_extension()[j].
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
sage: J = P.join_matrix(); J
[0 1 2 3 4 5 6 7]
[1 1 3 3 7 7 7 7]
[2 3 2 3 4 6 6 7]
[3 3 3 3 7 7 7 7]
[4 7 4 7 4 7 7 7]
[5 7 6 7 7 5 6 7]
[6 7 6 7 7 6 6 7]
[7 7 7 7 7 7 7 7]
sage: J[P(4).vertex,P(3).vertex] == P(7).vertex
True
sage: J[P(5).vertex,P(2).vertex] == P(5).vertex
True
sage: J[P(5).vertex,P(2).vertex] == P(2).vertex
False
Returns True if is 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
Computes the matrix whose (i,j) entry is 1 if self.linear_extension()[i] < self.linear_extension()[j] and 0 otherwise.
INPUT:
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
Returns 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].
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]
Returns a linear extension of this poset.
INPUT:
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
Returns the enumerated set of all the linear extensions of this poset
INPUT:
facade – a boolean (default: False); whether to return the linear extensions as plain lists
Warning
The facade option is not yet fully functional:
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True)
sage: L = P.linear_extensions(facade=True); L
The set of all linear extensions of Finite poset containing 6 elements
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
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 of L 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 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'>
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: map(Q.lower_covers,Q.list())
[[], [], [1, 0], [2], [3]]
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'>
Returns True if is 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
Returns all maximal chains of this poset. Each chain is listed in increasing order.
INPUT:
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]]
Returns a 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]
Returns a matrix whose (i,j) entry is k, where self.linear_extension()[k] is the meet (greatest lower bound) of self.linear_extension()[i] and self.linear_extension()[j].
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
sage: M = P.meet_matrix(); M
[0 0 0 0 0 0 0 0]
[0 1 0 1 0 0 0 1]
[0 0 2 2 2 0 2 2]
[0 1 2 3 2 0 2 3]
[0 0 2 2 4 0 2 4]
[0 0 0 0 0 5 5 5]
[0 0 2 2 2 5 6 6]
[0 1 2 3 4 5 6 7]
sage: M[P(4).vertex,P(3).vertex] == P(0).vertex
True
sage: M[P(5).vertex,P(2).vertex] == P(2).vertex
True
sage: M[P(5).vertex,P(2).vertex] == P(5).vertex
False
Returns a 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
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
Returns a matrix whose (i,j) entry is the value of the Mobius function evaluated at self.linear_extension()[i] and self.linear_extension()[j].
INPUT:
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
Returns a list of the elements such that
. The
order is that induced by the ordering in
self.linear_extension().
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")
[c, b]
Returns 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:
EXAMPLES:
sage: P = Posets.BooleanLattice(3)
sage: S = P.order_complex(); S
Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6, 7) and 6 facets
sage: S.f_vector()
[1, 8, 19, 18, 6]
sage: S.homology() # S is contractible
{0: 0, 1: 0, 2: 0, 3: 0}
sage: Q = P.subposet([1,2,3,4,5,6])
sage: Q.order_complex().homology() # a circle
{0: 0, 1: Z}
sage: P = Poset((divisors(15), attrcall("divides")), facade = True)
sage: P.order_complex()
Simplicial complex with vertex set (1, 3, 5, 15) and facets {(1, 3, 15), (1, 5, 15)}
If on_ints, then the elements of the poset are labelled
in the chain complex:
sage: P.order_complex(on_ints=True)
Simplicial complex with vertex set (0, 1, 2, 3) and facets {(0, 2, 3), (0, 1, 3)}
Returns the order filter generated by a list of 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]
Returns the order ideal generated by a list of 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]
Returns the order polytope of the poset
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) Richard Stanley. Two poset polytopes, Discrete Comput. Geom. (1986), doi:10.1007/BF02187680 |
Returns a Graphic object for the Hasse diagram of the poset.
The poset is increasing from bottom to top.
By default, the vertices are labelled.
If the poset is ranked, the plot uses the rank function for the heights of the vertices.
INPUT:
EXAMPLES:
sage: D = Poset({ 1:[2,3], 2:[4], 3:[4,5] })
sage: D.plot(label_elements=False)
sage: D.plot()
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)
Plot of the empy poset:
sage: P = Poset({})
sage: P.plot()
Plot of a ranked poset:
sage: P = Poset(DiGraph('E@ACA@?'))
sage: P.is_ranked()
True
sage: P.plot()
TESTS:
We check that label_elements and element_labels are honored:
sage: def get_plot_labels(P): return sorted(t.string for t in P if isinstance(t, sage.plot.text.Text))
sage: P1 = Poset({ 0:[1,2], 1:[3], 2:[3,4] })
sage: P2 = Poset({ 0:[1,2], 1:[3], 2:[3,4] }, facade=True)
sage: get_plot_labels(P1.plot(label_elements=False))
[]
sage: get_plot_labels(P1.plot(label_elements=True))
['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']
Returns the cartesian product of self and other.
EXAMPLES:
sage: P = Posets.ChainPoset(3)
sage: Q = Posets.ChainPoset(4)
sage: PQ = P.product(Q) ; PQ
Finite poset 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
Computes the (extended) promotion on the linear extension of the poset self
INPUT:
OUTPUT:
The extended promotion is defined on a poset self of size
by applying the promotion operator
to the default linear extension
of self
(see promotion()),
and relabelling self accordingly. For more details see [St2009].
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
minimum
of 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
.
REFERENCES:
[St2009] 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]]), facade = False)
sage: P.promotion()
Finite poset containing 2 elements
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
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
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
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
AUTHOR:
Returns a random subposet that contains each element with probability p.
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]])
sage: Q = P.random_subposet(.25)
Returns the rank of an element, or the rank of the poset if element is None. (The rank of a poset is the length of the longest chain of elements of the poset.)
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
sage: P.rank(5)
2
sage: P.rank()
3
sage: Q = Poset([[1,2],[3],[],[]])
sage: P = Posets.SymmetricGroupBruhatOrderPoset(4)
sage: [(v,P.rank(v)) for v in P]
[('1234', 0),
('1324', 1),
...
('4231', 5),
('4321', 6)]
Returns a 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 smallest value is
.
When the Hasse diagram of
has several components,
this is done for each component separately.
OUTPUT:
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
Returns a copy of this poset with its elements relabelled
INPUT:
relabelling – a function or dictionnary
This 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 {0,1,2, ...}, using a dictionary:
sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True, facade = False)
sage: relabelling = {c.element:i for (i,c) in enumerate(P)}; relabelling
{1: 0, 2: 1, 3: 2, 4: 3, 6: 4, 12: 5}
sage: Q = P.relabel(relabelling)
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 relabelling is applied to the elements of the poset without the wrapping. Thanks to this convention, the same relabelling 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]]
Note
As can be seen in the above examples, the default linear extension of Q is that of P after relabelling. In particular, P and Q share the same internal Hasse diagram.
Returns a list of all relations of the poset.
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.
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:
Returns an iterator for all the relations of the poset.
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.
Pairs are produced in a rough sort of lexicographic order, where earlier elements are from lower levels of the poset.
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]]
AUTHOR:
Shows the Graphics object corresponding the Hasse diagram of the poset. Optionally, it is labelled.
INPUT:
EXAMPLES:
sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(label_elements=False)
sage: D.show()
sage: elm_labs = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'}
sage: D.show(element_labels=elm_labs)
Deprecated: Use cardinality() instead. See trac ticket #8735 for details.
Returns 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
Returns the top 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
Unwraps an element of this poset
INPUT:
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.
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: map(Q.upper_covers,Q.list())
[[2], [2], [3], [4], []]
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'>
Returns 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,6,2,4,12])
sage: list(Q)
[1, 3, 6, 2, 4, 12]
sage: Q.cover_relations()
[[1, 3], [1, 2], [3, 6], [6, 12], [2, 6], [2, 4], [4, 12]]
TESTS:
We check that we can pass in a list of elements of P instead:
sage: Q = P.with_linear_extension(map(P, [1,3,6,2,4,12]))
sage: list(Q)
[1, 3, 6, 2, 4, 12]
sage: Q.cover_relations()
[[1, 3], [1, 2], [3, 6], [6, 12], [2, 6], [2, 4], [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,6,2,4,12])
sage: list(Q)
[1, 3, 6, 2, 4, 12]
sage: Q.cover_relations()
[[1, 3], [1, 2], [3, 6], [6, 12], [2, 6], [2, 4], [4, 12]]
sage: sorted(Q.cover_relations()) == sorted(P.cover_relations())
True
Note
With the current implementation, this requires relabelling
the internal Dynkin diagram which is , where
is the number of elements and
the number of cover
relations.
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]]
[[0, 2], [1, 2]]
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
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
, where
is a collection of elements of the poset and
is a collection of relations
, each represented as a two-element lists/tuples/iterables such as [x,y]. The poset is then the transitive closure of the provided relations. If cover_relations=True, then
is assumed to contain exactly the cover relations of the poset. If
is empty, then
is taken to be the set of elements appearing in the relations
.
A two-element list or tuple
, where
is the set of elements of the poset and
is a function such that, for any pair
of elements of
,
returns whether
. If cover_relations=True, then
should return whether
is covered by
.
A dictionary, list or tuple of upper covers: data[x] is a list of the elements that cover the element
in 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. If cover_relations is True, then the edges of the digraph are assumed to correspond to the cover relations of the poset. Otherwise, the cover relations are computed.
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.
facade – a boolean or None (default); whether the Poset()‘s elements should be wrapped to make them aware of the Poset they belong to.
OUTPUT:
FinitePoset – an instance of the FinitePoset` class.
If category is specified, then the poset is created in this category instead of FinitePosets.
See also
EXAMPLES:
Elements and cover relations:
sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: Poset((elms, rels), cover_relations = True, facade = False)
Finite poset containing 7 elements
Elements and non-cover relations:
sage: elms = [1,2,3,4]
sage: rels = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
sage: P = Poset( [elms,rels] ,cover_relations=False); P
Finite poset containing 4 elements
sage: P.cover_relations()
[[1, 2], [2, 3], [3, 4]]
Elements and function: the standard permutations of [1, 2, 3, 4] with the Bruhat order:
sage: elms = Permutations(4)
sage: fcn = lambda p,q : p.bruhat_lequal(q)
sage: Poset((elms, fcn))
Finite poset containing 24 elements
With a function that identifies the cover relations: the set partitions of {1, 2, 3} ordered by refinement:
sage: elms = SetPartitions(3)
sage: def fcn(A, B):
... if len(A) != len(B)+1:
... return False
... for a in A:
... if not any(set(a).issubset(b) for b in B):
... return False
... return True
sage: Poset((elms, fcn), cover_relations=True)
Finite poset containing 5 elements
A dictionary of upper covers:
sage: Poset({'a':['b','c'], 'b':['d'], 'c':['d'], 'd':[]})
Finite poset containing 4 elements
A list of upper covers:
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 anoying 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
'ac'
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', 'b', 'c', 'a']
sage: P.principal_order_ideal('a')
['d', 'b', 'c', 'a']
sage: P.principal_order_ideal('b')
['d', 'b']
sage: P.principal_order_ideal('d')
['d']
sage: TestSuite(P).run()
Warning
DiGraph is used to construct the poset, and the vertices of a DiGraph are converted to plain Python int‘s if they are Integer‘s:
sage: G = DiGraph({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]})
sage: type(G.vertices()[0])
<type 'int'>
This is worked around by systematically converting back the vertices of a poset to Integer‘s if they are int‘s:
sage: P = Poset((divisors(15), attrcall("divides")), facade = False)
sage: type(P.an_element().element)
<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 (see UniqueRepresentation. Namely if two posets are created from two equal data, then they are not only equal but actually identical:
sage: data1 = [[1,2],[3],[3]]
sage: data2 = [[1,2],[3],[3]]
sage: P1 = Poset(data1)
sage: P2 = Poset(data2)
sage: P1 == P2
True
sage: P1 is P2
True
In situations where this behaviour is not desired, one can use the key option:
sage: P1 = Poset(data1, key = "foo")
sage: P2 = Poset(data2, key = "bar")
sage: P1 is P2
False
sage: P1 == P2
False
key can be any hashable value and is passed down to UniqueRepresentation. It is otherwise ignored by the poset constructor.
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: elements_label should be a dict or a list if different from None. (Did you intend data to be equal to a pair ?)
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