# Hasse diagrams of posets¶

class sage.combinat.posets.hasse_diagram.HasseDiagram(data=None, pos=None, loops=None, format=None, boundary=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)

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 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()

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 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)]

are_incomparable(i, j)

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)]

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 #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

chains(element_class=<type 'list'>, exclude=None)

Return all chains of self, organized as a prefix tree.

INPUT:

• element_class – (default: list) an iterable type
• exclude – 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 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,)]

antichains()

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 in self.linear_extension.

INPUT:

• x – any element of the poset
• y – 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()

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()

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

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, 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

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 in self.linear_extension.

INPUT:

• x – any element of the poset
• y – 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_lattice()

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

is_distributive_lattice()

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

is_gequal(x, y)

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


Deprecated, has conflicting definition of “graded” vs. “ranked” with posets.

Return True if the Hasse diagram is ranked. For definition of ranked see rank_function().

is_greater_than(x, y)

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

is_join_semilattice()

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

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 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

is_linear_extension(lin_ext=None)

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 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

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() 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

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.

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=...

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.

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()

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()

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]

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.

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=...

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(i, j)

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!"

mobius_function_matrix()

Returns the matrix of the Mobius function of this poset

This returns the sparse matrix over $$\ZZ$$ 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

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 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)
[]

order_filter(elements)

Returns 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)

Returns 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]

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]

rank(element=None)

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

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)

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))
[]


#### Previous topic

Elements of posets, lattices, semilattices, etc.

#### Next topic

Finite semilattices and lattices