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()
Returns all antichains of self, organized as a prefix tree
INPUT:
- 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()
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())
[[]]
Returns whether i and j are comparable in the poset
INPUT:
- 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)]
Returns whether i and j are incomparable in the poset
INPUT:
- 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)]
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
TESTS:
For a time, this function was named size(), which would override the same-named method of the underlying digraph. Trac #8735 renamed this method to cardinality() with a deprecation warning. Trac #11214 removed the warning since code for graphs was raising the warning inadvertently. This tests that size() 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
Return all chains of self, organized as a prefix tree.
INPUT:
OUTPUT:
The enumerated set (with a forest structure given by prefix ordering) consisting of all chains of self, each of which is given as an element_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
Return a list of the elements of self 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: 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
Return a list l such that l[i] is a complement of i in self, or None if no such complement exists.
A complement of x is an element y such that the meet of x and y is the bottom element of self and the join of x and y is the top element of self.
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: H.complements()
[4, 3, 3, 2, 0]
sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[4]})
sage: H.complements()
[4, None, None, None, 0]
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)]
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)]
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, 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
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
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
Return a list of the elements of self 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: 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
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
TESTS:
Check trac ticket #15330:
sage: p = Poset(DiGraph({0:[1],2:[1]}))
sage: p.is_chain()
False
Returns True if self is the Hasse diagram of a complemented lattice, and False otherwise.
EXAMPLES:
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: H.is_complemented_lattice()
True
sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[4]})
sage: H.is_complemented_lattice()
False
Returns True if self is the Hasse diagram of a distributive lattice, and False 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
Returns True if x is greater than or equal to y, and False 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
Returns True if the poset is graded, and False otherwise.
A poset is graded if it admits a rank function. For more information about the rank function, see rank_function() and is_ranked().
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
Returns True if x is greater than but not equal to y, and False 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
Returns True if self has a join operation, and False 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
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
Returns True if x is less than or equal to y 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
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
Returns True if self has a meet operation, and False 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
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() and is_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
Returns the matrix of joins of self. The (x,y)-entry of this matrix is the join of x and y in self.
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):
...
ValueError: No join for x=...
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.
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
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]
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]]
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]
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 the matrix of meets of self. The (x,y)-entry of this matrix is the meet of x and y in self.
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):
...
ValueError: No meet for x=...
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 M”obius function of the poset on the elements i and j.
EXAMPLES:
sage: P = Poset([[1,2,3],[4],[4],[4],[]])
sage: H = P._hasse_diagram
sage: H.mobius_function(0,4)
2
sage: for u,v in P.cover_relations_iterator():
... if P.mobius_function(u,v) != -1:
... print "Bug in mobius_function!"
Returns the matrix of the Mobius function of this poset
This returns the sparse matrix over whose (x, y) entry
is the value of the M”obius function of self evaluated on
x and y, and redefines mobius_function() to use
it.
Note
The result is cached in _mobius_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.mobius_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.mobius_function_matrix().is_immutable()
True
sage: hasattr(H,'_mobius_function_matrix')
True
sage: H.mobius_function == H._mobius_function_from_matrix
True
Return a list of the elements of self 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: 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)
[]
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: H = Posets.BooleanLattice(4)._hasse_diagram
sage: H.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: H = Posets.BooleanLattice(4)._hasse_diagram
sage: H.order_ideal([7,10])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]
Returns a Graphics object corresponding to the Hasse diagram.
EXAMPLES:
sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: elm_lbls = Permutations(3).list()
sage: P = Poset(uc,elm_lbls)
sage: H = P._hasse_diagram
sage: levels = H.level_sets()
sage: heights = dict([[i, levels[i]] for i in range(len(levels))])
sage: type(H.plot(label_elements=True))
<class 'sage.plot.graphics.Graphics'>
sage: P = Posets.SymmetricGroupBruhatIntervalPoset([1,2,3,4], [3,4,1,2])
sage: P._hasse_diagram.plot()
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]
Returns the order ideal generated by .
EXAMPLES:
sage: H = Posets.BooleanLattice(4)._hasse_diagram
sage: H.principal_order_ideal(6)
[0, 2, 4, 6]
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.)
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
Return the (normalized) rank function of the poset, if it exists.
A rank function of a poset is a function
that maps elements of
to integers and satisfies:
if
covers
. The function
is normalized such that its minimum value on every
connected component of the Hasse diagram of
is
. This determines the function
uniquely (when
it exists).
OUTPUT:
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)
Shows the Graphics object corresponding to the Hasse diagram. Optionally, it is labelled.
INPUT:
EXAMPLES:
sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: elm_lbls = Permutations(3).list()
sage: P = Poset(uc,elm_lbls)
sage: H = P._hasse_diagram
sage: levels = H.level_sets()
sage: heights = dict([[i, levels[i]] for i in range(len(levels))])
sage: H.show(label_elements=True)
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
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))
[]