Hasse diagrams of posets¶
antichains() |
Returns all antichains of self , organized as a prefix tree |
antichains_iterator() |
Return an iterator over the antichains of the poset. |
are_comparable() |
Returns whether i and j are comparable in the poset |
are_incomparable() |
Returns whether i and j are incomparable in the poset |
bottom() |
Returns the bottom element of the poset, if it exists. |
cardinality() |
Returns the number of elements in the poset. |
chains() |
Return all chains of self , organized as a prefix tree. |
complements() |
Deprecated. |
cover_relations() |
Return the list of cover relations. |
cover_relations_iterator() |
Iterate over cover relations. |
covers() |
Returns True if y covers x and False otherwise. |
dual() |
Returns a poset that is dual to the given poset. |
find_nonsemidistributive_elements() |
Check if the lattice is semidistributive or not. |
find_nonsemimodular_pair() |
Return pair of elements showing the lattice is not modular. |
frattini_sublattice() |
Return the list of elements of the Frattini sublattice of the lattice. |
has_bottom() |
Returns True if the poset has a unique minimal element. |
has_top() |
Returns True if the poset contains a unique maximal element, and False otherwise. |
interval() |
Return a list of the elements \(z\) of self such that \(x \leq z \leq y\). The order is that induced by the ordering in self.linear_extension . |
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_complemented() |
Return an element of the lattice that has no complement. |
is_convex_subset() |
Return True if \(S\) is a convex subset of the poset, and False otherwise. |
is_distributive_lattice() |
Returns True if self is the Hasse diagram of a distributive lattice, and False otherwise. |
is_gequal() |
Returns True if x is greater than or equal to y , and False otherwise. |
is_graded() |
Deprecated, has conflicting definition of “graded” vs. “ranked” with posets. |
is_greater_than() |
Returns True if x is greater than but not equal to y , and False otherwise. |
is_join_semilattice() |
Returns True if self has a join operation, and False otherwise. |
is_lequal() |
Returns True if i is less than or equal to j in the poset, and False otherwise. |
is_less_than() |
Returns True if x is less than or equal to y in the poset, and False otherwise. |
is_linear_extension() |
Test if an ordering is a linear extension. |
is_meet_semilattice() |
Returns True if self has a meet operation, and False otherwise. |
is_ranked() |
Returns True if the poset is ranked, and False otherwise. |
join_matrix() |
Returns the matrix of joins of self . The (x,y) -entry of this matrix is the join of x and y in self . |
lequal_matrix() |
Returns the matrix whose (i,j) entry is 1 if i is less than j in the poset, and 0 otherwise; and redefines __lt__ to use this matrix. |
linear_extension() |
Return a linear extension |
linear_extensions() |
Return all linear extensions |
lower_covers_iterator() |
Returns the list of elements that are covered by element . |
maximal_elements() |
Returns a list of the maximal elements of the poset. |
maximal_sublattices() |
Return maximal sublattices of the lattice. |
meet_matrix() |
Returns the matrix of meets of self . The (x,y) -entry of this matrix is the meet of x and y in self . |
minimal_elements() |
Returns a list of the minimal elements of the poset. |
moebius_function() |
Returns the value of the Möbius function of the poset on the elements i and j . |
moebius_function_matrix() |
Returns the matrix of the Möbius function of this poset |
open_interval() |
Return a list of the elements \(z\) of self such that \(x < z < y\). The order is that induced by the ordering in self.linear_extension . |
order_filter() |
Return the order filter generated by a list of elements. |
order_ideal() |
Return the order ideal generated by a list of elements. |
orthocomplementations_iterator() |
Return an iterator over orthocomplementations of the lattice. |
principal_order_filter() |
Returns the order filter generated by i . |
principal_order_ideal() |
Returns the order ideal generated by \(i\). |
pseudocomplement() |
Return the pseudocomplement of element , if it exists. |
rank() |
Returns the rank of 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.) |
rank_function() |
Return the (normalized) rank function of the poset, if it exists. |
sublattices_iterator() |
Return an iterator over sublattices of the Hasse diagram. |
top() |
Returns the top element of the poset, if it exists. |
upper_covers_iterator() |
Returns the list of elements that cover element . |
vertical_decomposition() |
Return vertical decomposition of the lattice. |
-
class
sage.combinat.posets.hasse_diagram.
HasseDiagram
(data=None, pos=None, loops=None, format=None, weighted=None, implementation='c_graph', data_structure='sparse', vertex_labels=True, name=None, multiedges=None, convert_empty_dict_labels_to_None=None, sparse=True, immutable=False)¶ Bases:
sage.graphs.digraph.DiGraph
The Hasse diagram of a poset. This is just a transitively-reduced, directed, acyclic graph without loops or multiple edges.
Note
We assume that
range(n)
is a linear extension of the poset. That is,range(n)
is the vertex set and a topological sort of the digraph.This should not be called directly, use Poset instead; all type checking happens there.
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]}); H Hasse diagram of a poset containing 4 elements sage: TestSuite(H).run()
-
antichains
(element_class=<type 'list'>)¶ Returns all antichains of
self
, organized as a prefix treeINPUT:
element_class
– (default:list) an iterable type
EXAMPLES:
sage: P = posets.PentagonPoset() sage: H = P._hasse_diagram sage: A = H.antichains() sage: list(A) [[], [0], [1], [1, 2], [1, 3], [2], [3], [4]] sage: A.cardinality() 8 sage: [1,3] in A True sage: [1,4] in A False
TESTS:
sage: TestSuite(A).run(skip = "_test_pickling")
Note
It’s actually the pickling of the cached method
coxeter_transformation()
that fails ...TESTS:
sage: A = Poset()._hasse_diagram.antichains() sage: list(A) [[]] sage: TestSuite(A).run()
-
antichains_iterator
()¶ Return an iterator over the antichains of the poset.
Note
The algorithm is based on Freese-Jezek-Nation p. 226. It does a depth first search through the set of all antichains organized in a prefix tree.
EXAMPLES:
sage: P = posets.PentagonPoset() sage: H = P._hasse_diagram sage: H.antichains_iterator() <generator object antichains_iterator at ...> sage: list(H.antichains_iterator()) [[], [4], [3], [2], [1], [1, 3], [1, 2], [0]] sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2],1:[4],2:[3],3:[4]}) sage: list(H.antichains_iterator()) [[], [4], [3], [2], [1], [1, 3], [1, 2], [0]] sage: H = HasseDiagram({0:[],1:[],2:[]}) sage: list(H.antichains_iterator()) [[], [2], [1], [1, 2], [0], [0, 2], [0, 1], [0, 1, 2]] sage: H = HasseDiagram({0:[1],1:[2],2:[3],3:[4]}) sage: list(H.antichains_iterator()) [[], [4], [3], [2], [1], [0]]
TESTS:
sage: H = Poset()._hasse_diagram sage: list(H.antichains_iterator()) [[]]
-
are_comparable
(i, j)¶ Returns whether
i
andj
are comparable in the posetINPUT:
i
,j
– vertices of this Hasse diagram
EXAMPLES:
sage: P = posets.PentagonPoset() sage: H = P._hasse_diagram sage: H.are_comparable(1,2) False sage: [ (i,j) for i in H.vertices() for j in H.vertices() if H.are_comparable(i,j)] [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 4), (2, 0), (2, 2), (2, 3), (2, 4), (3, 0), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]
-
are_incomparable
(i, j)¶ Returns whether
i
andj
are incomparable in the posetINPUT:
i
,j
– vertices of this Hasse diagram
EXAMPLES:
sage: P = posets.PentagonPoset() sage: H = P._hasse_diagram sage: H.are_incomparable(1,2) True sage: [ (i,j) for i in H.vertices() for j in H.vertices() if H.are_incomparable(i,j)] [(1, 2), (1, 3), (2, 1), (3, 1)]
-
bottom
()¶ 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
-
cardinality
()¶ Returns the number of elements in the poset.
EXAMPLES:
sage: Poset([[1,2,3],[4],[4],[4],[]]).cardinality() 5
TESTS:
For a time, this function was named
size()
, which would override the same-named method of the underlying digraph. trac ticket #8735 renamed this method tocardinality()
with a deprecation warning. trac ticket #11214 removed the warning since code for graphs was raising the warning inadvertently. This tests thatsize()
for a Hasse diagram returns the number of edges in the digraph.sage: L = Posets.BooleanLattice(5) sage: H = L.hasse_diagram() sage: H.size() 80 sage: H.size() == H.num_edges() True
-
chains
(element_class=<type 'list'>, exclude=None)¶ Return all chains of
self
, organized as a prefix tree.INPUT:
element_class
– (default:list
) an iterable typeexclude
– elements of the poset to be excluded (default:None
)
OUTPUT:
The enumerated set (with a forest structure given by prefix ordering) consisting of all chains of
self
, each of which is given as anelement_class
.EXAMPLES:
sage: P = posets.PentagonPoset() sage: H = P._hasse_diagram sage: A = H.chains() 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]] sage: A.cardinality() 20 sage: [1,3] in A False sage: [1,4] in A True
One can exclude some vertices:
sage: list(H.chains(exclude=[4, 3])) [[], [0], [0, 1], [0, 2], [1], [2]]
The
element_class
keyword determines how the chains are being returned:sage: P = Poset({1: [2, 3], 2: [4]}) sage: list(P._hasse_diagram.chains(element_class=tuple)) [(), (0,), (0, 1), (0, 1, 2), (0, 2), (0, 3), (1,), (1, 2), (2,), (3,)] sage: list(P._hasse_diagram.chains()) [[], [0], [0, 1], [0, 1, 2], [0, 2], [0, 3], [1], [1, 2], [2], [3]](Note that taking the Hasse diagram has renamed the vertices.)
sage: list(P._hasse_diagram.chains(element_class=tuple, exclude=[0])) [(), (1,), (1, 2), (2,), (3,)]See also
-
closed_interval
(x, y)¶ Return a list of the elements \(z\) of
self
such that \(x \leq z \leq y\). The order is that induced by the ordering inself.linear_extension
.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: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram(dag) sage: I = set([2,5,6,4,7]) sage: I == set(H.interval(2,7)) True
-
complements
()¶ Deprecated.
-
cover_relations
()¶ Return the list of cover relations.
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}) sage: H.cover_relations() [(0, 2), (0, 3), (1, 3), (1, 4), (2, 5), (3, 5), (4, 5)]
-
cover_relations_iterator
()¶ Iterate over cover relations.
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2,3], 1:[3,4], 2:[5], 3:[5], 4:[5]}) sage: list(H.cover_relations_iterator()) [(0, 2), (0, 3), (1, 3), (1, 4), (2, 5), (3, 5), (4, 5)]
-
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, in the basis of simple modules.
EXAMPLES:
sage: M = Posets.PentagonPoset()._hasse_diagram.coxeter_transformation(); M [ 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()._hasse_diagram.coxeter_transformation() sage: M**8 == 1 True
-
dual
()¶ Returns a poset that is dual to the given poset.
EXAMPLES:
sage: P = Posets.IntegerPartitions(4) sage: H = P._hasse_diagram; H Hasse diagram of a poset containing 5 elements sage: H.dual() Hasse diagram of a poset containing 5 elements
TESTS:
sage: H = Posets.IntegerPartitions(4)._hasse_diagram sage: H.is_isomorphic( H.dual().dual() ) True sage: H.is_isomorphic( H.dual() ) False
-
find_nonsemidistributive_elements
(meet_or_join)¶ Check if the lattice is semidistributive or not.
INPUT:
meet_or_join
– string'meet'
or'join'
to decide if to check for join-semidistributivity or meet-semidistributivity
OUTPUT:
None
if the lattice is semidistributive OR- tuple
(u, e, x, y)
such that \(u = e \vee x = e \vee y\) but \(u \neq e \vee (x \wedge y)\) ifmeet_or_join=='join'
and \(u = e \wedge x = e \wedge y\) but \(u \neq e \wedge (x \vee y)\) ifmeet_or_join=='meet'
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1, 2], 1:[3, 4], 2:[4, 5], 3:[6], ....: 4:[6], 5:[6]}) sage: H.find_nonsemidistributive_elements('join') is None False sage: H.find_nonsemidistributive_elements('meet') is None True
-
find_nonsemimodular_pair
(upper)¶ Return pair of elements showing the lattice is not modular.
INPUT:
- upper, a Boolean – if
True
, test wheter the lattice is upper semimodular; otherwise test whether the lattice is lower semimodular.
OUTPUT:
None
, if the lattice is semimodular. Pair \((a, b)\) violating semimodularity otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1, 2], 1:[3, 4], 2:[4, 5], 3:[6], 4:[6], 5:[6]}) sage: H.find_nonsemimodular_pair(upper=True) is None True sage: H.find_nonsemimodular_pair(upper=False) (5, 3) sage: H_ = HasseDiagram(H.reverse().relabel(lambda x: 6-x, inplace=False)) sage: H_.find_nonsemimodular_pair(upper=True) (3, 1) sage: H_.find_nonsemimodular_pair(upper=False) is None True
- upper, a Boolean – if
-
frattini_sublattice
()¶ Return the list of elements of the Frattini sublattice of the lattice.
EXAMPLES:
sage: H = Posets.PentagonPoset()._hasse_diagram sage: H.frattini_sublattice() [0, 4]
-
has_bottom
()¶ 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
-
has_top
()¶ Returns
True
if the poset contains 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
-
interval
(x, y)¶ Return a list of the elements \(z\) of
self
such that \(x \leq z \leq y\). The order is that induced by the ordering inself.linear_extension
.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: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram(dag) sage: I = set([2,5,6,4,7]) sage: I == set(H.interval(2,7)) True
-
is_bounded
()¶ 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
-
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
TESTS:
Check trac ticket #15330:
sage: p = Poset(DiGraph({0:[1],2:[1]})) sage: p.is_chain() False
-
is_complemented
()¶ Return an element of the lattice that has no complement.
If the lattice is complemented, return
None
.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1, 2], 1:[3], 2:[3], 3:[4]}) sage: H.is_complemented() 1 sage: H = HasseDiagram({0:[1, 2, 3], 1:[4], 2:[4], 3:[4]}) sage: H.is_complemented() is None True
-
is_convex_subset
(S)¶ Return
True
if \(S\) is a convex subset of the poset, andFalse
otherwise.A subset \(S\) is convex in the poset if \(b \in S\) whenever \(a, c \in S\) and \(a \le b \le c\).
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: B3 = HasseDiagram({0: [1, 2, 4], 1: [3, 5], 2: [3, 6], ....: 3: [7], 4: [5, 6], 5: [7], 6: [7]}) sage: B3.is_convex_subset([1, 3, 5, 4]) # Also connected True sage: B3.is_convex_subset([1, 3, 4]) # Not connected True sage: B3.is_convex_subset([0, 1, 2, 3, 6]) # No, 0 < 4 < 6 False sage: B3.is_convex_subset([0, 1, 2, 7]) # No, 1 < 3 < 7. False
TESTS:
sage: B3.is_convex_subset([]) True sage: B3.is_convex_subset([6]) True
-
is_distributive_lattice
()¶ Returns
True
ifself
is the Hasse diagram of a distributive lattice, andFalse
otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.is_distributive_lattice() False sage: H = HasseDiagram({0:[1,2],1:[3],2:[3]}) sage: H.is_distributive_lattice() True sage: H = HasseDiagram({0:[1,2,3],1:[4],2:[4],3:[4]}) sage: H.is_distributive_lattice() False
-
is_gequal
(x, y)¶ Returns
True
ifx
is greater than or equal toy
, andFalse
otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: Q = HasseDiagram({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = 0,1,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
()¶ Deprecated, has conflicting definition of “graded” vs. “ranked” with posets.
Return
True
if the Hasse diagram is ranked. For definition of ranked seerank_function()
.
-
is_greater_than
(x, y)¶ Returns
True
ifx
is greater than but not equal toy
, andFalse
otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: Q = HasseDiagram({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = 0,1,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_join_semilattice
()¶ Returns
True
ifself
has a join operation, andFalse
otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.is_join_semilattice() True sage: H = HasseDiagram({0:[2,3],1:[2,3]}) sage: H.is_join_semilattice() False sage: H = HasseDiagram({0:[2,3],1:[2,3],2:[4],3:[4]}) sage: H.is_join_semilattice() False
-
is_lequal
(i, j)¶ Returns True if i is less than or equal to j in the poset, and False otherwise.
Note
If the
lequal_matrix()
has been computed, then this method is redefined to use the cached matrix (see_alternate_is_lequal()
).TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = 0, 1, 4 sage: H.is_lequal(x,y) False sage: H.is_lequal(y,x) False sage: H.is_lequal(x,z) True sage: H.is_lequal(y,z) True sage: H.is_lequal(z,z) True
-
is_less_than
(x, y)¶ Returns True if
x
is less than or equal toy
in the poset, and False otherwise.TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2], 1:[2], 2:[3], 3:[4], 4:[]}) sage: x,y,z = 0, 1, 4 sage: H.is_less_than(x,y) False sage: H.is_less_than(y,x) False sage: H.is_less_than(x,z) True sage: H.is_less_than(y,z) True sage: H.is_less_than(z,z) False
-
is_linear_extension
(lin_ext=None)¶ Test if an ordering is a linear extension.
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]}) sage: H.is_linear_extension(range(4)) True sage: H.is_linear_extension([3,2,1,0]) False
-
is_meet_semilattice
()¶ Returns
True
ifself
has a meet operation, andFalse
otherwise.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.is_meet_semilattice() True sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]}) sage: H.is_meet_semilattice() True sage: H = HasseDiagram({0:[2,3],1:[2,3]}) sage: H.is_meet_semilattice() False
-
is_ranked
()¶ Returns True if the poset is ranked, and False otherwise.
A poset is ranked if it admits a rank function. For more information about the rank function, see
rank_function()
andis_graded()
.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
-
join_matrix
()¶ Returns the matrix of joins of
self
. The(x,y)
-entry of this matrix is the join ofx
andy
inself
.This algorithm is modelled after the algorithm of Freese-Jezek-Nation (p217). It can also be found on page 140 of [Gec81].
Note
Once the matrix has been computed, it is stored in
_join_matrix()
. Delete this attribute if you want to recompute the matrix.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.join_matrix() [0 1 2 3 4 5 6 7] [1 1 4 7 4 7 7 7] [2 4 2 6 4 5 6 7] [3 7 6 3 7 7 6 7] [4 4 4 7 4 7 7 7] [5 7 5 7 7 5 7 7] [6 7 6 6 7 7 6 7] [7 7 7 7 7 7 7 7]
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2,3],1:[2,3]}) sage: H.join_matrix() Traceback (most recent call last): ... ValueError: not a join-semilattice: no top element sage: H = HasseDiagram({0:[2,3],1:[2,3],2:[4],3:[4]}) sage: H.join_matrix() Traceback (most recent call last): ... LatticeError: no join for ...
-
lequal_matrix
()¶ Returns the matrix whose
(i,j)
entry is 1 ifi
is less thanj
in the poset, and 0 otherwise; and redefines__lt__
to use this matrix.EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]) sage: H = P._hasse_diagram sage: H.lequal_matrix() [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]
TESTS:
sage: H.lequal_matrix().is_immutable() True
-
linear_extension
()¶ Return a linear extension
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]}) sage: H.linear_extension() [0, 1, 2, 3]
-
linear_extensions
()¶ Return all linear extensions
TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]}) sage: H.linear_extensions() [[0, 1, 2, 3], [0, 2, 1, 3]]
-
lower_covers_iterator
(element)¶ Returns the list of elements that are covered by
element
.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: list(H.lower_covers_iterator(0)) [] sage: list(H.lower_covers_iterator(4)) [1, 2]
-
maximal_elements
()¶ 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]
-
maximal_sublattices
()¶ Return maximal sublattices of the lattice.
EXAMPLES:
sage: L = Posets.PentagonPoset() sage: ms = L._hasse_diagram.maximal_sublattices() sage: sorted(ms, key=sorted) [{0, 1, 2, 4}, {0, 1, 3, 4}, {0, 2, 3, 4}]
-
meet_matrix
()¶ Returns the matrix of meets of
self
. The(x,y)
-entry of this matrix is the meet ofx
andy
inself
.This algorithm is modelled after the algorithm of Freese-Jezek-Nation (p217). It can also be found on page 140 of [Gec81].
Note
Once the matrix has been computed, it is stored in
_meet_matrix()
. Delete this attribute if you want to recompute the matrix.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.meet_matrix() [0 0 0 0 0 0 0 0] [0 1 0 0 1 0 0 1] [0 0 2 0 2 2 2 2] [0 0 0 3 0 0 3 3] [0 1 2 0 4 2 2 4] [0 0 2 0 2 5 2 5] [0 0 2 3 2 2 6 6] [0 1 2 3 4 5 6 7]
REFERENCE:
[Gec81] (1, 2) Fundamentals of Computation Theory Gecseg, F. Proceedings of the 1981 International Fct-Conference Szeged, Hungaria, August 24-28, vol 117 Springer-Verlag, 1981 TESTS:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[2,3],1:[2,3]}) sage: H.meet_matrix() Traceback (most recent call last): ... ValueError: not a meet-semilattice: no bottom element sage: H = HasseDiagram({0:[1,2],1:[3,4],2:[3,4]}) sage: H.meet_matrix() Traceback (most recent call last): ... LatticeError: no meet for ...
-
minimal_elements
()¶ 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
-
mobius_function
(*args, **kwds)¶ Deprecated: Use
moebius_function()
instead. See trac ticket #19855 for details.
-
mobius_function_matrix
(*args, **kwds)¶ Deprecated: Use
moebius_function_matrix()
instead. See trac ticket #19855 for details.
-
moebius_function
(i, j)¶ Returns the value of the Möbius function of the poset on the elements
i
andj
.EXAMPLES:
sage: P = Poset([[1,2,3],[4],[4],[4],[]]) sage: H = P._hasse_diagram sage: H.moebius_function(0,4) 2 sage: for u,v in P.cover_relations_iterator(): ....: if P.moebius_function(u,v) != -1: ....: print("Bug in moebius_function!")
-
moebius_function_matrix
()¶ Returns the matrix of the Möbius function of this poset
This returns the sparse matrix over \(\ZZ\) whose
(x, y)
entry is the value of the Möbius function ofself
evaluated onx
andy
, and redefinesmoebius_function()
to use it.Note
The result is cached in
_moebius_function_matrix()
.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.moebius_function_matrix() [ 1 -1 -1 -1 1 0 1 0] [ 0 1 0 0 -1 0 0 0] [ 0 0 1 0 -1 -1 -1 2] [ 0 0 0 1 0 0 -1 0] [ 0 0 0 0 1 0 0 -1] [ 0 0 0 0 0 1 0 -1] [ 0 0 0 0 0 0 1 -1] [ 0 0 0 0 0 0 0 1]
TESTS:
sage: H.moebius_function_matrix().is_immutable() True sage: hasattr(H,'_moebius_function_matrix') True sage: H.moebius_function == H._moebius_function_from_matrix True
-
open_interval
(x, y)¶ Return a list of the elements \(z\) of
self
such that \(x < z < y\). The order is that induced by the ordering inself.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: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram(dag) sage: set([5,6,4]) == set(H.open_interval(2,7)) True sage: H.open_interval(7,2) []
-
order_filter
(elements)¶ Return the order filter generated by a list of elements.
\(I\) is an order filter if, for any \(x\) in \(I\) and \(y\) such that \(y \ge x\), then \(y\) is in \(I\).
EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram sage: H.order_filter([3,8]) [3, 7, 8, 9, 10, 11, 12, 13, 14, 15]
-
order_ideal
(elements)¶ Return the order ideal generated by a list of elements.
\(I\) is an order ideal if, for any \(x\) in \(I\) and \(y\) such that \(y \le x\), then \(y\) is in \(I\).
EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram sage: H.order_ideal([7,10]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 10]
-
orthocomplementations_iterator
()¶ Return an iterator over orthocomplementations of the lattice.
OUTPUT:
An iterator that gives plain list of integers.
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,2], 1:[3,4], 3:[5], 4:[5], 2:[6,7], ....: 6:[8], 7:[8], 5:[9], 8:[9]}) sage: list(H.orthocomplementations_iterator()) [[9, 8, 5, 6, 7, 2, 3, 4, 1, 0], [9, 8, 5, 7, 6, 2, 4, 3, 1, 0]]
ALGORITHM:
As
DiamondPoset(2*n+2)
has \((2n)!/(n!2^n)\) different orthocomplementations, the complexity of listing all of them is necessarily \(O(n!)\).An orthocomplemented lattice is self-dual, so that for example orthocomplement of an atom is a coatom. This function basically just computes list of possible orthocomplementations for every element (i.e. they must be complements and “duals”), and then tries to fit them all.
TESTS:
Special and corner cases:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram() # Empty sage: list(H.orthocomplementations_iterator()) [[]] sage: H = HasseDiagram({0:[]}) # One element sage: list(H.orthocomplementations_iterator()) [[0]] sage: H = HasseDiagram({0:[1]}) # Two elements sage: list(H.orthocomplementations_iterator()) [[1, 0]]
Trivial cases: odd number of elements, not self-dual, not complemented:
sage: H = Posets.DiamondPoset(5)._hasse_diagram sage: list(H.orthocomplementations_iterator()) [] sage: H = Posets.ChainPoset(4)._hasse_diagram sage: list(H.orthocomplementations_iterator()) [] sage: H = HasseDiagram( ([[0, 1], [0, 2], [0, 3], [1, 4], [1, 8], [4, 6], [4, 7], [6, 9], [7, 9], [2, 5], [3, 5], [5, 8], [8, 9]]) ) sage: list(H.orthocomplementations_iterator()) [] sage: H = HasseDiagram({0:[1, 2, 3], 1: [4], 2:[4], 3: [5], 4:[5]}) sage: list(H.orthocomplementations_iterator()) []
Complemented, self-dual and even number of elements, but not orthocomplemented:
sage: H = HasseDiagram( ([[0, 1], [1, 2], [2, 3], [0, 4], [4, 5], [0, 6], [3, 7], [5, 7], [6, 7]]) ) sage: list(H.orthocomplementations_iterator()) []
Unique orthocomplementations; second is not uniquely complemented, but has only one orthocomplementation.
sage: H = Posets.BooleanLattice(4)._hasse_diagram # Uniquely complemented sage: len(list(H.orthocomplementations_iterator())) 1 sage: H = HasseDiagram({0:[1, 2], 1:[3], 2:[4], 3:[5], 4:[5]}) sage: len([_ for _ in H.orthocomplementations_iterator()]) 1“Lengthening diamond” must keep the number of orthocomplementations:
sage: H = HasseDiagram( ([[0, 1], [0, 2], [0, 3], [0, 4], [1, 5], [2, 5], [3, 5], [4, 5]]) ) sage: n = len([_ for _ in H.orthocomplementations_iterator()]); n 3 sage: H = HasseDiagram('M]??O?@??C??OA???OA??@?A??C?A??O??') sage: len([_ for _ in H.orthocomplementations_iterator()]) == n True
This lattice has an unique “possible orthocomplement” for every element, but they can not be fit together; orthocomplement pairs would be 0-11, 1-7, 2-4, 3-10, 5-9 and 6-8, and then orthocomplements for chain 0-1-6-11 would be 11-7-8-0, which is not a chain:
sage: H = HasseDiagram('KTGG_?AAC?O?o?@?@?E?@?@??') sage: list([_ for _ in H.orthocomplementations_iterator()]) []
-
principal_order_filter
(i)¶ Returns the order filter generated by
i
.EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram sage: H.principal_order_filter(2) [2, 3, 6, 7, 10, 11, 14, 15]
-
principal_order_ideal
(i)¶ Returns the order ideal generated by \(i\).
EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram sage: H.principal_order_ideal(6) [0, 2, 4, 6]
-
pseudocomplement
(element)¶ Return the pseudocomplement of
element
, if it exists.The pseudocomplement is the greatest element whose meet with given element is the bottom element. It may not exist, and then the function returns
None
.INPUT:
element
– an element of the lattice.
OUTPUT:
An element of the Hasse diagram, i.e. an integer, or
None
if the pseudocomplement does not exist.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]}) sage: H.pseudocomplement(2) 3 sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4], 3: [4]}) sage: H.pseudocomplement(2) is None True
-
rank
(element=None)¶ Returns the rank of
element
, 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: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: H.rank(5) 2 sage: H.rank() 3 sage: Q = HasseDiagram({0:[1,2],1:[3],2:[],3:[]}) sage: Q.rank() 2 sage: Q.rank(1) 1
-
rank_function
()¶ Return the (normalized) rank function of the poset, if it exists.
A rank function of a poset \(P\) is a function \(r\) that maps elements of \(P\) to integers and satisfies: \(r(x) = r(y) + 1\) if \(x\) covers \(y\). The function \(r\) is normalized such that its minimum value on every connected component of the Hasse diagram of \(P\) is \(0\). This determines the function \(r\) uniquely (when it exists).
OUTPUT:
- a lambda function, if the poset admits a rank function
None
, if the poset does not admit a rank function
EXAMPLES:
sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]) sage: P.rank_function() is not None True 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
test for ticket trac ticket #14006:
sage: H = Poset()._hasse_diagram sage: s = dumps(H) sage: f = H.rank_function() sage: s = dumps(H)
-
sublattices_iterator
(elms, min_e)¶ Return an iterator over sublattices of the Hasse diagram.
INPUT:
elms
– elements already in sublattice; use set() at startmin_e
– smallest new element to add for new sublattices
OUTPUT:
List of sublattices as sets of integers.
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0: [1, 2], 1:[3], 2:[3]}) sage: it = H.sublattices_iterator(set(), 0); it <generator object sublattices_iterator at ...> sage: next(it) set() sage: next(it) {0}
-
top
()¶ 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
-
upper_covers_iterator
(element)¶ Returns the list of elements that cover
element
.EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]}) sage: list(H.upper_covers_iterator(0)) [1, 2, 3] sage: list(H.upper_covers_iterator(7)) []
-
vertical_decomposition
(return_list=False)¶ Return vertical decomposition of the lattice.
This is the backend function for vertical decomposition functions of lattices.
The property of being vertically decomposable is defined for lattices. This is not checked, and the function works with any bounded poset.
INPUT:
return_list
, a boolean. IfFalse
(the default), returnTrue
if the lattice is vertically decomposable andFalse
otherwise. IfTrue
, return list of decomposition elements.
EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram sage: H.vertical_decomposition() False sage: P = Poset( ([1,2,3,6,12,18,36], attrcall("divides")) ) sage: P._hasse_diagram.vertical_decomposition() True sage: P._hasse_diagram.vertical_decomposition(return_list=True) [3]
-
-
exception
sage.combinat.posets.hasse_diagram.
LatticeError
(fail, x, y)¶ Bases:
exceptions.ValueError
Helper exception class to forward elements without meet or join to upper level, so that the user will see “No meet for a and b” instead of “No meet for 1 and 2”.