Hasse diagrams of posets

antichains()	Return all antichains of self, organized as a prefix tree
antichains_iterator()	Return an iterator over the antichains of the poset.
are_comparable()	Return whether i and j are comparable in the poset
are_incomparable()	Return whether i and j are incomparable in the poset
atoms_of_congruence_lattice()	Return atoms of the congruence lattice.
bottom()	Return the bottom element of the poset, if it exists.
cardinality()	Return the number of elements in the poset.
chains()	Return all chains of self, organized as a prefix tree.
congruence()	Return the congruence start “extended” by parts.
congruences_iterator()	Return an iterator over all congruences of the lattice.
cover_relations()	Return the list of cover relations.
cover_relations_iterator()	Iterate over cover relations.
covers()	Return True if y covers x and False otherwise.
dual()	Return 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.
find_nontrivial_congruence()	Return a pair that generates non-trivial congruence or None if there is not any.
frattini_sublattice()	Return the list of elements of the Frattini sublattice of the lattice.
greedy_linear_extensions_iterator()	Return an iterator over greedy linear extensions of the Hasse diagram.
has_bottom()	Return True if the poset has a unique minimal element.
has_top()	Return 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_antichain_of_poset()	Return True if elms is an antichain of the Hasse diagram and False otherwise.
is_bounded()	Return True if the poset contains a unique maximal element and a unique minimal element, and False otherwise.
is_chain()	Return True if the poset is totally ordered, and False otherwise.
is_complemented()	Return an element of the lattice that has no complement.
is_congruence_normal()	Return True if the lattice can be constructed from the one-element lattice with Day doubling constructions of convex subsets.
is_convex_subset()	Return True if \(S\) is a convex subset of the poset, and False otherwise.
is_gequal()	Return True if x is greater than or equal to y, and False otherwise.
is_greater_than()	Return True if x is greater than but not equal to y, and False otherwise.
is_join_semilattice()	Return True if self has a join operation, and False otherwise.
is_lequal()	Return True if i is less than or equal to j in the poset, and False otherwise.
is_less_than()	Return 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()	Return True if self has a meet operation, and False otherwise.
is_ranked()	Return True if the poset is ranked, and False otherwise.
join_matrix()	Return the matrix of joins of self. The (x,y)-entry of this matrix is the join of x and y in self.
kappa()	Return the maximum element greater than the element covered by a but not greater than a.
kappa_dual()	Return the minimum element smaller than the element covering a but not smaller than a.
lequal_matrix()	Return a matrix whose (i,j) entry is 1 if i is less than j in the poset, and 0 otherwise; and redefines __lt__ to use the boolean version of this matrix.
linear_extension()	Return a linear extension
linear_extensions()	Return an iterator over all linear extensions.
lower_covers_iterator()	Return the list of elements that are covered by element.
maximal_elements()	Return a list of the maximal elements of the poset.
maximal_sublattices()	Return maximal sublattices of the lattice.
meet_matrix()	Return the matrix of meets of self. The (x,y)-entry of this matrix is the meet of x and y in self.
minimal_elements()	Return a list of the minimal elements of the poset.
moebius_function()	Return the value of the Möbius function of the poset on the elements i and j.
moebius_function_matrix()	Return the matrix of the Möbius function of this poset.
neutral_elements()	Return the list of neutral elements of the lattice.
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.
prime_elements()	Return the join-prime and meet-prime elements of the bounded poset.
principal_congruences_poset()	Return the poset of join-irreducibles of the congruence lattice.
principal_order_filter()	Return the order filter generated by i.
principal_order_ideal()	Return the order ideal generated by \(i\).
pseudocomplement()	Return the pseudocomplement of element, if it exists.
rank()	Return 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.
skeleton()	Return the skeleton of the lattice.
sublattices_iterator()	Return an iterator over sublattices of the Hasse diagram.
supergreedy_linear_extensions_iterator()	Return an iterator over supergreedy linear extensions of the Hasse diagram.
top()	Return the top element of the poset, if it exists.
upper_covers_iterator()	Return 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, 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'>)

Return 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

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

are_comparable(i, j)

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

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

atoms_of_congruence_lattice()

Return atoms of the congruence lattice.

In other words, return “minimal non-trivial” congruences: A congruence is minimal if the only finer (as a partition of set of elements) congruence is the trivial congruence where every block contains only one element.

See also

congruence()

OUTPUT:

List of congruences, every congruence as sage.combinat.set_partition.SetPartition

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: N5 = HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3:[4]})
sage: N5.atoms_of_congruence_lattice()
[{{0}, {1}, {2, 3}, {4}}]
sage: Hex = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [5], 4: [5]})
sage: Hex.atoms_of_congruence_lattice()
[{{0}, {1}, {2, 4}, {3}, {5}}, {{0}, {1, 3}, {2}, {4}, {5}}]

ALGORITHM:

Every atom is a join-irreducible. Every join-irreducible of \(\mathrm{Con}(L)\) is a principal congruence generated by a meet-irreducible element and the only element covering it (and also by a join-irreducible element and the only element covered by it). Hence we check those principal congruences to find the minimal ones.

bottom()

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

Return the number of elements in the poset.

EXAMPLES:

sage: Poset([[1,2,3],[4],[4],[4],[]]).cardinality()
5

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

See also

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

congruence(parts, start=None, stop_pairs=[])

Return the congruence start “extended” by parts.

start is assumed to be a valid congruence of the lattice, and this is not checked.

INPUT:

• parts – a list of lists; congruences to add
• start – a disjoint set; already computed congruence (or None)
• stop_pairs – a list of pairs; list of pairs for stopping computation

OUTPUT:

None, if the congruence generated by start and parts together contains a block that has elements \(a, b\) so that (a, b) is in the list stop_pairs. Otherwise the least congruence that contains a block whose subset is \(p\) for every \(p\) in parts or start, given as sage.sets.disjoint_set.DisjointSet_class.

ALGORITHM:

Use the quadrilateral argument from page 120 of [Dav1997].

Basically we take one block from todo-list, search quadrilateral blocks up and down against the block, and then complete them to closed intervals and add to todo-list.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]})
sage: cong = H.congruence([[0, 1]]); cong
{{0, 1, 3}, {2, 4}}
sage: H.congruence([[0, 2]], start=cong)
{{0, 1, 2, 3, 4}}

sage: H.congruence([[0, 1]], stop_pairs=[(1, 3)]) is None
True

congruences_iterator()

Return an iterator over all congruences of the lattice.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram('GY@OQ?OW@?O?')
sage: it = H.congruences_iterator(); it
<generator object ...>
sage: sorted([cong.number_of_subsets() for cong in it])
[1, 2, 2, 2, 4, 4, 4, 8]

cover_relations()

Return the list of cover relations.

cover_relations_iterator()

Iterate over cover relations.

covers(x, y)

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

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

See also

lequal_matrix(), moebius_function_matrix()

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]

dual()

Return 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

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)\) if meet_or_join=='join' and \(u = e \wedge x = e \wedge y\) but \(u \neq e \wedge (x \vee y)\) if meet_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

find_nontrivial_congruence()

Return a pair that generates non-trivial congruence or None if there is not any.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [5], 2: [3, 4], 3: [5], 4: [5]})
sage: H.find_nontrivial_congruence()
{{0, 1}, {2, 3, 4, 5}}

sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4], 3: [4]})
sage: H.find_nontrivial_congruence() is None
True

ALGORITHM:

See https://www.math.hawaii.edu/~ralph/Preprints/conlat.pdf:

If \(\Theta\) is a join irreducible element of a \(\mathrm{Con}(L)\), then there is at least one join-irreducible \(j\) and one meet-irreducible \(m\) such that \(\Theta\) is both the principal congruence generated by \((j^*, j)\), where \(j^*\) is the unique lower cover of \(j\), and the principal congruence generated by \((m, m^*)\), where \(m^*\) is the unique upper cover of \(m\).

So, we only check join irreducibles or meet irreducibles, whichever is a smaller set. To optimize more we stop computation whenever it finds a pair that we know to generate one-element congruence.

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]

greedy_linear_extensions_iterator()

Return an iterator over greedy linear extensions of the Hasse diagram.

A linear extension \([e_1, e_2, \ldots, e_n]\) is greedy if for every \(i\) either \(e_{i+1}\) covers \(e_i\) or all upper covers of \(e_i\) have at least one lower cover that is not in \([e_1, e_2, \ldots, e_i]\).

Informally said a linear extension is greedy if it “always goes up when possible” and so has no unnecessary jumps.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: N5 = HasseDiagram({0: [1, 2], 2: [3], 1: [4], 3: [4]})
sage: for l in N5.greedy_linear_extensions_iterator():
....:     print(l)
[0, 1, 2, 3, 4]
[0, 2, 3, 1, 4]

has_bottom()

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

Return 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_antichain_of_poset(elms)

Return True if elms is an antichain of the Hasse diagram 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_antichain_of_poset([1, 2, 3])
True
sage: H.is_antichain_of_poset([0, 2, 3])
False

is_bounded()

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

Return True if the poset is totally ordered, and False otherwise.

EXAMPLES:

sage: L = Poset({0:[1],1:[2],2:[3],3:[4]})
sage: L.is_chain()
True
sage: V = Poset({0:[1,2]})
sage: V.is_chain()
False

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

Return True if the lattice can be constructed from the one-element lattice with Day doubling constructions of convex subsets.

Subsets to double does not need to be lower nor upper pseudo-intervals. On the other hand they must be convex, i.e. doubling a non-convex but municipal subset will give a lattice that returns False from this function.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram('IX?Q@?AG?OG?W?O@??')
sage: H.is_congruence_normal()
True

The 5-element diamond is the smallest non-example:

sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4], 3: [4]})
sage: H.is_congruence_normal()
False

This is done by doubling a non-convex subset:

sage: H = HasseDiagram('OQC?a?@CO?G_C@?GA?O??_??@?BO?A_?G??C??_?@???')
sage: H.is_congruence_normal()
False

ALGORITHM:

See http://www.math.hawaii.edu/~jb/inflation.pdf

is_convex_subset(S)

Return True if \(S\) is a convex subset of the poset, and False 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

is_gequal(x, y)

Return 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

is_greater_than(x, y)

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

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

Return 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 data (see _alternate_is_lequal()).

is_less_than(x, y)

Return True if x is less than or equal to y in the poset, and False otherwise.

is_linear_extension(lin_ext=None)

Test if an ordering is a linear extension.

is_meet_semilattice()

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

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

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

kappa(a)

Return the maximum element greater than the element covered by a but not greater than a.

Define \(\kappa(a)\) as the maximum element of \((\uparrow a_*) \setminus (\uparrow a)\), where \(a_*\) is the element covered by \(a\). It is always a meet-irreducible element, if it exists.

Note

Element a is expected to be join-irreducible, and this is not checked.

INPUT:

• a – a join-irreducible element of the lattice

OUTPUT:

The element \(\kappa(a)\) or None if there is not a unique greatest element with given constraints.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [5], 4: [6], 5: [6]})
sage: H.kappa(1)
5
sage: H.kappa(2) is None
True

kappa_dual(a)

Return the minimum element smaller than the element covering a but not smaller than a.

Define \(\kappa^*(a)\) as the minimum element of \((\downarrow a_*) \setminus (\downarrow a)\), where \(a_*\) is the element covering \(a\). It is always a join-irreducible element, if it exists.

Note

Element a is expected to be meet-irreducible, and this is not checked.

INPUT:

• a – a join-irreducible element of the lattice

OUTPUT:

The element \(\kappa^*(a)\) or None if there is not a unique smallest element with given constraints.

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.kappa_dual(3)
2
sage: H.kappa_dual(4) is None
True

lequal_matrix(boolean=False)

Return a matrix whose (i,j) entry is 1 if i is less than j in the poset, and 0 otherwise; and redefines __lt__ to use the boolean version of this matrix.

INPUT:

• boolean – optional flag (default False) telling whether to return a matrix with coefficients in \(\GF(2)\) or in \(\ZZ\)

See also

moebius_function_matrix(), coxeter_transformation()

EXAMPLES:

sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]])
sage: H = P._hasse_diagram
sage: M = H.lequal_matrix(); M
[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: M.base_ring()
Integer Ring

sage: P = posets.DiamondPoset(6)
sage: H = P._hasse_diagram
sage: M = H.lequal_matrix(boolean=True)
sage: M.base_ring()
Finite Field of size 2

linear_extension()

Return a linear extension

linear_extensions()

Return an iterator over all linear extensions.

lower_covers_iterator(element)

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

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

Return 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

minimal_elements()

Return 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

moebius_function(i, j)

Return the value of the Möbius 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.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(algorithm='recursive')

Return 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 of self evaluated on x and y, and redefines moebius_function() to use it.

INPUT:

• algorithm – optional, 'recursive' (default) or 'matrix'

This uses either the recursive formula or one matrix inversion.

Note

The result is cached in _moebius_function_matrix().

Todo

Try to make a specific multimodular matrix inversion algorithm for this kind of sparse triangular matrices where the non-zero entries of the inverse are in known positions.

See also

lequal_matrix(), coxeter_transformation()

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]

neutral_elements()

Return the list of neutral elements of the lattice.

An element \(a\) in a lattice is neutral if the sublattice generated by \(a\), \(x\) and \(y\) is distributive for every \(x\), \(y\) in the lattice.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H= HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3: [4, 5],
....:                  4: [6], 5:[6]})
sage: sorted(H.neutral_elements())
[0, 4, 6]

ALGORITHM:

Basically we just check the distributivity against all element pairs \(x, y\) to see if element \(a\) is neutral or not.

If we found that \(a, x, y\) is not a distributive triple, we add all three to list of non-neutral elements. If we found \(a\) to be neutral, we add it to list of neutral elements. When testing we skip already found neutral elements, as they can’t be our \(x\) or \(y\).

We skip \(a, x, y\) as trivial if it is a chain. We do that by letting \(x\) to be a non-comparable to \(a\); \(y\) can be any element.

We first try to found \(x\) and \(y\) from elements not yet tested, so that we could get three birds with one stone.

And last, the top and bottom elements are always neutral and need not be tested.

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)

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.

prime_elements()

Return the join-prime and meet-prime elements of the bounded poset.

An element \(x\) of a poset \(P\) is join-prime if the subposet induced by \(\{y \in P \mid y \not\ge x\}\) has a top element. Meet-prime is defined dually.

Note

The poset is expected to be bounded, and this is not checked.

OUTPUT:

A pair \((j, m)\) where \(j\) is a list of join-prime elements and \(m\) is a list of meet-prime elements.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]})
sage: H.prime_elements()
([1, 2], [2, 3])

principal_congruences_poset()

Return the poset of join-irreducibles of the congruence lattice.

OUTPUT:

A pair \((P, D)\) where \(P\) is a poset and \(D\) is a dictionary.

Elements of \(P\) are pairs \((x, y)\) such that \(x\) is an element of the lattice and \(y\) is an element covering it. In the poset \((a, b)\) is less than \((c, d)\) iff the principal congruence generated by \((a, b)\) is refinement of the principal congruence generated by \((c, d)\).

\(D\) is a dictionary from pairs \((x, y)\) to the congruence (given as DisjointSet) generated by the pair.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: N5 = HasseDiagram({0: [1, 2], 1: [4], 2: [3], 3: [4]})
sage: P, D = N5.principal_congruences_poset()
sage: P
Finite poset containing 3 elements
sage: P.bottom()
(2, 3)
sage: D[(2, 3)]
{{0}, {1}, {2, 3}, {4}}

principal_order_filter(i)

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

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

Return 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

skeleton()

Return the skeleton of the lattice.

The lattice is expected to be pseudocomplemented and non-empty.

The skeleton of the lattice is the subposet induced by those elements that are the pseudocomplement to at least one element.

OUTPUT:

List of elements such that the subposet induced by them is the skeleton of the lattice.

EXAMPLES:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [3, 4], 2: [4],
....:                   3: [5], 4: [5]})
sage: H.skeleton()
[5, 2, 0, 3]

sublattices_iterator(elms, min_e)

Return an iterator over sublattices of the Hasse diagram.

INPUT:

• elms – elements already in sublattice; use set() at start
• min_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}

supergreedy_linear_extensions_iterator()

Return an iterator over supergreedy linear extensions of the Hasse diagram.

A linear extension \([e_1, e_2, \ldots, e_n]\) is supergreedy if, for every \(i\) and \(j\) where \(i > j\), \(e_i\) covers \(e_j\) if for every \(i > k > j\) at least one lower cover of \(e_k\) is not in \([e_1, e_2, \ldots, e_k]\).

Informally said a linear extension is supergreedy if it “always goes as high possible, and withdraw so less as possible”. These are also called depth-first linear extensions.

EXAMPLES:

We show the difference between “only greedy” and supergreedy extensions:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 2: [3, 4]})
sage: G_ext = list(H.greedy_linear_extensions_iterator())
sage: SG_ext = list(H.supergreedy_linear_extensions_iterator())
sage: [0, 2, 3, 1, 4] in G_ext
True
sage: [0, 2, 3, 1, 4] in SG_ext
False

sage: len(SG_ext)
4

top()

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

Return 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. If False (the default), return an element that is not the top neither the bottom element of the lattice, but is comparable to all elements of the lattice, if the lattice is vertically decomposable and None otherwise. If True, return list of decomposition elements.

EXAMPLES:

sage: H = posets.BooleanLattice(4)._hasse_diagram
sage: H.vertical_decomposition() is None
True
sage: P = Poset( ([1,2,3,6,12,18,36], attrcall("divides")) )
sage: P._hasse_diagram.vertical_decomposition()
3
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”.