Finite posets

This module implements finite partially ordered sets. It defines:

FinitePoset	A class for finite posets
FinitePosets_n	A class for finite posets up to isomorphism (i.e. unlabeled posets)
Poset()	Construct a finite poset from various forms of input data.
is_poset()	Return True if a directed graph is acyclic and transitively reduced.

List of Poset methods

Comparing, intervals and relations

is_less_than()	Return True if \(x\) is strictly less than \(y\) in the poset.
is_greater_than()	Return True if \(x\) is strictly greater than \(y\) in the poset.
is_lequal()	Return True if \(x\) is less than or equal to \(y\) in the poset.
is_gequal()	Return True if \(x\) is greater than or equal to \(y\) in the poset.
compare_elements()	Compare two element of the poset.
closed_interval()	Return the list of elements in a closed interval of the poset.
open_interval()	Return the list of elements in an open interval of the poset.
relations()	Return the list of relations in the poset.
relations_iterator()	Return an iterator over relations in the poset.
order_filter()	Return the upper set generated by elements.
order_ideal()	Return the lower set generated by elements.

Covering

covers()	Return True if y covers x.
lower_covers()	Return elements covered by given element.
upper_covers()	Return elements covering given element.
cover_relations()	Return the list of cover relations.
lower_covers_iterator()	Return an iterator over elements covered by given element.
upper_covers_iterator()	Return an iterator over elements covering given element.
cover_relations_iterator()	Return an iterator over cover relations of the poset.
common_upper_covers()	Return the list of all common upper covers of the given elements.
common_lower_covers()	Return the list of all common lower covers of the given elements.
meet()	Return the meet of given elements if it exists; None otherwise.
join()	Return the join of given elements if it exists; None otherwise.

Properties of the poset

cardinality()	Return the number of elements in the poset.
height()	Return the number of elements in a longest chain of the poset.
width()	Return the number of elements in a longest antichain of the poset.
relations_number()	Return the number of relations in the poset.
dimension()	Return the dimension of the poset.
jump_number()	Return the jump number of the poset.
magnitude()	Return the magnitude of the poset.
has_bottom()	Return True if the poset has a unique minimal element.
has_top()	Return True if the poset has a unique maximal element.
is_bounded()	Return True if the poset has both unique minimal and unique maximal element.
is_chain()	Return True if the poset is totally ordered.
is_connected()	Return True if the poset is connected.
is_graded()	Return True if all maximal chains of the poset has same length.
is_ranked()	Return True if the poset has a rank function.
is_rank_symmetric()	Return True if the poset is rank symmetric.
is_series_parallel()	Return True if the poset can be built by ordinal sums and disjoint unions.
is_greedy()	Return True if all greedy linear extensions have equal number of jumps.
is_jump_critical()	Return True if removal of any element reduces the jump number.
is_eulerian()	Return True if the poset is Eulerian.
is_incomparable_chain_free()	Return True if the poset is (m+n)-free.
is_slender()	Return True if the poset is slender.
is_sperner()	Return True if the poset is Sperner.
is_join_semilattice()	Return True if the poset has a join operation.
is_meet_semilattice()	Return True if the poset has a meet operation.

Minimal and maximal elements

bottom()	Return the bottom element of the poset, if it exists.
top()	Return the top element of the poset, if it exists.
maximal_elements()	Return the list of the maximal elements of the poset.
minimal_elements()	Return the list of the minimal elements of the poset.

New posets from old ones

disjoint_union()	Return the disjoint union of the poset with other poset.
ordinal_sum()	Return the ordinal sum of the poset with other poset.
product()	Return the Cartesian product of the poset with other poset.
ordinal_product()	Return the ordinal product of the poset with other poset.
rees_product()	Return the Rees product of the poset with other poset.
lexicographic_sum()	Return the lexicographic sum of posets.
star_product()	Return the star product of the poset with other poset.
with_bounds()	Return the poset with bottom and top element adjoined.
without_bounds()	Return the poset with bottom and top element removed.
dual()	Return the dual of the poset.
completion_by_cuts()	Return the Dedekind-MacNeille completion of the poset.
intervals_poset()	Return the poset of intervals of the poset.
connected_components()	Return the connected components of the poset as subposets.
factor()	Return the decomposition of the poset as a Cartesian product.
ordinal_summands()	Return the ordinal summands of the poset.
subposet()	Return the subposet containing elements with partial order induced by this poset.
random_subposet()	Return a random subposet that contains each element with given probability.
relabel()	Return a copy of this poset with its elements relabelled.
canonical_label()	Return copy of the poset canonically (re)labelled to integers.
slant_sum()	Return the slant sum poset of two posets.

Chains, antichains & linear intervals

is_chain_of_poset()	Return True if elements in the given list are comparable.
is_antichain_of_poset()	Return True if elements in the given list are incomparable.
is_linear_interval()	Return whether the given interval is a total order.
chains()	Return the chains of the poset.
antichains()	Return the antichains of the poset.
maximal_chains()	Return the maximal chains of the poset.
maximal_antichains()	Return the maximal antichains of the poset.
maximal_chains_iterator()	Return an iterator over the maximal chains of the poset.
maximal_chain_length()	Return the maximum length of maximal chains of the poset.
antichains_iterator()	Return an iterator over the antichains of the poset.
random_maximal_chain()	Return a random maximal chain.
random_maximal_antichain()	Return a random maximal antichain.
linear_intervals_count()	Return the enumeration of linear intervals in the poset.

Drawing

show()	Display the Hasse diagram of the poset.
plot()	Return a Graphic object corresponding the Hasse diagram of the poset.
graphviz_string()	Return a representation in the DOT language, ready to render in graphviz.

Comparing posets

is_isomorphic()	Return True if both posets are isomorphic.
is_induced_subposet()	Return True if given poset is an induced subposet of this poset.

Polynomials

chain_polynomial()	Return the chain polynomial of the poset.
characteristic_polynomial()	Return the characteristic polynomial of the poset.
f_polynomial()	Return the f-polynomial of the poset.
flag_f_polynomial()	Return the flag f-polynomial of the poset.
h_polynomial()	Return the h-polynomial of the poset.
flag_h_polynomial()	Return the flag h-polynomial of the poset.
order_polynomial()	Return the order polynomial of the poset.
zeta_polynomial()	Return the zeta polynomial of the poset.
M_triangle()	Return the M-triangle of the poset.
kazhdan_lusztig_polynomial()	Return the Kazhdan-Lusztig polynomial of the poset.
coxeter_polynomial()	Return the characteristic polynomial of the Coxeter transformation.
degree_polynomial()	Return the generating polynomial of degrees of vertices in the Hasse diagram.
p_partition_enumerator()	Return a \(P\)-partition enumerator of the poset.

Polytopes

chain_polytope()	Return the chain polytope of the poset.
order_polytope()	Return the order polytope of the poset.

Graphs

hasse_diagram()	Return the Hasse diagram of the poset as a directed graph.
cover_relations_graph()	Return the (undirected) graph of cover relations.
comparability_graph()	Return the comparability graph of the poset.
incomparability_graph()	Return the incomparability graph of the poset.
frank_network()	Return Frank’s network of the poset.
linear_extensions_graph()	Return the linear extensions graph of the poset.

Linear extensions

is_linear_extension()	Return True if the given list is a linear extension of the poset.
linear_extension()	Return a linear extension of the poset.
linear_extensions()	Return the enumerated set of all the linear extensions of the poset.
promotion()	Return the (extended) promotion on the linear extension of the poset.
evacuation()	Return evacuation on the linear extension associated to the poset.
with_linear_extension()	Return a copy of self with a different default linear extension.
random_linear_extension()	Return a random linear extension.

Matrices

lequal_matrix()	Compute the matrix whose (i,j) entry is 1 if self.linear_extension()[i] < self.linear_extension()[j] and 0 otherwise.
moebius_function()	Return the value of Möbius function of given elements in the poset.
moebius_function_matrix()	Return a matrix whose (i,j) entry is the value of the Möbius function evaluated at self.linear_extension()[i] and self.linear_extension()[j].
coxeter_transformation()	Return the matrix of the Auslander-Reiten translation acting on the Grothendieck group of the derived category of modules.
coxeter_smith_form()	Return the Smith form of the Coxeter transformation.

Miscellaneous

sorted()	Return given list sorted by the poset.
isomorphic_subposets()	Return all subposets isomorphic to another poset.
isomorphic_subposets_iterator()	Return an iterator over the subposets isomorphic to another poset.
has_isomorphic_subposet()	Return True if the poset contains a subposet isomorphic to another poset.
list()	List the elements of the poset.
cuts()	Return the cuts of the given poset.
dilworth_decomposition()	Return a partition of the points into the minimal number of chains.
greene_shape()	Compute the Greene-Kleitman partition aka Greene shape of the poset self.
incidence_algebra()	Return the incidence algebra of self.
is_EL_labelling()	Return whether f is an EL labelling of the poset.
isomorphic_subposets_iterator()	Return an iterator over the subposets isomorphic to another poset.
isomorphic_subposets()	Return all subposets isomorphic to another poset.
level_sets()	Return elements grouped by maximal number of cover relations from a minimal element.
order_complex()	Return the order complex associated to this poset.
random_order_ideal()	Return a random order ideal of self with uniform probability.
rank()	Return the rank of an element, or the rank of the poset.
rank_function()	Return a rank function of the poset, if it exists.
unwrap()	Unwrap an element of this poset.
atkinson()	Return the \(a\)-spectrum of a poset whose undirected Hasse diagram is a forest.
spectrum()	Return the \(a\)-spectrum of this poset.

Classes and functions

class sage.combinat.posets.posets.FinitePoset(hasse_diagram, elements, category, facade, key)

Bases: UniqueRepresentation, Parent

A (finite) \(n\)-element poset constructed from a directed acyclic graph.

INPUT:

• hasse_diagram – an instance of FinitePoset, or a DiGraph that is transitively-reduced, acyclic, loop-free, and multiedge-free.

• elements – an optional list of elements, with element[i] corresponding to vertex i. If elements is None, then it is set to be the vertex set of the digraph. Note that if this option is set, then elements is considered as a specified linear extension of the poset and the \(linear_extension\) attribute is set.

• category – FinitePosets, or a subcategory thereof

• facade – boolean or None (default); whether the FinitePoset’s elements should be wrapped to make them aware of the Poset they belong to.

  • If facade = True, the FinitePoset’s elements are exactly those given as input.

  • If facade = False, the FinitePoset’s elements will become PosetElement objects.

  • If facade = None (default) the expected behaviour is the behaviour of facade = True, unless the opposite can be deduced from the context (i.e. for instance if a FinitePoset is built from another FinitePoset, itself built with facade = False)

• key – any hashable value (default: None)

EXAMPLES:

Sage

sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: from sage.combinat.posets.posets import FinitePoset
sage: P = FinitePoset(DiGraph(dict([[i,uc[i]] for i in range(len(uc))])), facade=False); P
Finite poset containing 6 elements
sage: P.cover_relations()
[[5, 4], [5, 3], [4, 1], [0, 2], [0, 3], [2, 1], [3, 1]]
sage: TestSuite(P).run()
sage: P.category()
Category of finite enumerated posets
sage: P.__class__
<class 'sage.combinat.posets.posets.FinitePoset_with_category'>

sage: Q = sage.combinat.posets.posets.FinitePoset(P, facade = False); Q
Finite poset containing 6 elements

sage: Q is P
True

Python

>>> from sage.all import *
>>> uc = [[Integer(2),Integer(3)], [], [Integer(1)], [Integer(1)], [Integer(1)], [Integer(3),Integer(4)]]
>>> from sage.combinat.posets.posets import FinitePoset
>>> P = FinitePoset(DiGraph(dict([[i,uc[i]] for i in range(len(uc))])), facade=False); P
Finite poset containing 6 elements
>>> P.cover_relations()
[[5, 4], [5, 3], [4, 1], [0, 2], [0, 3], [2, 1], [3, 1]]
>>> TestSuite(P).run()
>>> P.category()
Category of finite enumerated posets
>>> P.__class__
<class 'sage.combinat.posets.posets.FinitePoset_with_category'>

>>> Q = sage.combinat.posets.posets.FinitePoset(P, facade = False); Q
Finite poset containing 6 elements

>>> Q is P
True

We keep the same underlying Hasse diagram, but change the elements:

Sage

sage: Q = sage.combinat.posets.posets.FinitePoset(P, elements=[1,2,3,4,5,6], facade=False); Q
Finite poset containing 6 elements with distinguished linear extension
sage: Q.cover_relations()
[[1, 2], [1, 5], [2, 6], [3, 4], [3, 5], [4, 6], [5, 6]]

Python

>>> from sage.all import *
>>> Q = sage.combinat.posets.posets.FinitePoset(P, elements=[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)], facade=False); Q
Finite poset containing 6 elements with distinguished linear extension
>>> Q.cover_relations()
[[1, 2], [1, 5], [2, 6], [3, 4], [3, 5], [4, 6], [5, 6]]

We test the facade argument:

Sage

sage: P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=False)
sage: P.category()
Category of finite enumerated posets
sage: parent(P[0]) is P
True

sage: Q = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=True)
sage: Q.category()
Category of facade finite enumerated posets
sage: parent(Q[0]) is str
True
sage: TestSuite(Q).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented

Python

>>> from sage.all import *
>>> P = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=False)
>>> P.category()
Category of finite enumerated posets
>>> parent(P[Integer(0)]) is P
True

>>> Q = Poset(DiGraph({'a':['b'],'b':['c'],'c':['d']}), facade=True)
>>> Q.category()
Category of facade finite enumerated posets
>>> parent(Q[Integer(0)]) is str
True
>>> TestSuite(Q).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented

Changing a non facade poset to a facade poset:

Sage

sage: PQ = Poset(P, facade=True)
sage: PQ.category()
Category of facade finite enumerated posets
sage: parent(PQ[0]) is str
True
sage: PQ is Q
True

Python

>>> from sage.all import *
>>> PQ = Poset(P, facade=True)
>>> PQ.category()
Category of facade finite enumerated posets
>>> parent(PQ[Integer(0)]) is str
True
>>> PQ is Q
True

Changing a facade poset to a non facade poset:

Sage

sage: QP = Poset(Q, facade = False)
sage: QP.category()
Category of finite enumerated posets
sage: parent(QP[0]) is QP
True

Python

>>> from sage.all import *
>>> QP = Poset(Q, facade = False)
>>> QP.category()
Category of finite enumerated posets
>>> parent(QP[Integer(0)]) is QP
True

Conversion to some other software is possible:

Sage

sage: P = posets.TamariLattice(3)
sage: libgap(P)                                         # optional - gap_package_qpa
<A poset on 5 points>

sage: P = Poset({1:[2],2:[]})
sage: macaulay2('needsPackage "Posets"')   # optional - macaulay2
Posets
sage: macaulay2(P)   # optional - macaulay2
Relation Matrix: | 1 1 |
                 | 0 1 |

Python

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(3))
>>> libgap(P)                                         # optional - gap_package_qpa
<A poset on 5 points>

>>> P = Poset({Integer(1):[Integer(2)],Integer(2):[]})
>>> macaulay2('needsPackage "Posets"')   # optional - macaulay2
Posets
>>> macaulay2(P)   # optional - macaulay2
Relation Matrix: | 1 1 |
                 | 0 1 |

Note

A class that inherits from this class needs to define Element. This is the class of the elements that the inheriting class contains. For example, for this class, FinitePoset, Element is PosetElement. It can also define _dual_class which is the class of dual posets of this class. E.g. FiniteMeetSemilattice._dual_class is FiniteJoinSemilattice.

Element

alias of PosetElement

M_triangle()

Return the M-triangle of the poset.

The poset is expected to be graded.

OUTPUT: an M_triangle

The M-triangle is the generating polynomial of the Möbius numbers

\[M(x, y)=\sum_{a \leq b} \mu(a,b) x^{|a|}y^{|b|} .\]

EXAMPLES:

Sage

sage: P = posets.DiamondPoset(5)
sage: P.M_triangle()                                                        # needs sage.combinat
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1

Python

>>> from sage.all import *
>>> P = posets.DiamondPoset(Integer(5))
>>> P.M_triangle()                                                        # needs sage.combinat
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1

antichains(element_constructor=None)

Return the antichains of the poset.

An antichain of a poset is a set of elements of the poset that are pairwise incomparable.

INPUT:

• element_constructor – a function taking an iterable as argument (default: list)

OUTPUT:

The enumerated set (of type PairwiseCompatibleSubsets) of all antichains of the poset, each of which is given as an element_constructor.

EXAMPLES:

Sage

sage: A = posets.PentagonPoset().antichains(); A
Set of antichains of Finite lattice containing 5 elements
sage: list(A)
[[], [0], [1], [1, 2], [1, 3], [2], [3], [4]]
sage: A.cardinality()
8
sage: A[3]
[1, 2]

Python

>>> from sage.all import *
>>> A = posets.PentagonPoset().antichains(); A
Set of antichains of Finite lattice containing 5 elements
>>> list(A)
[[], [0], [1], [1, 2], [1, 3], [2], [3], [4]]
>>> A.cardinality()
8
>>> A[Integer(3)]
[1, 2]

To get the antichains as, say, sets, one may use the element_constructor option:

Sage

sage: list(posets.ChainPoset(3).antichains(element_constructor=set))
[set(), {0}, {1}, {2}]

Python

>>> from sage.all import *
>>> list(posets.ChainPoset(Integer(3)).antichains(element_constructor=set))
[set(), {0}, {1}, {2}]

To get the antichains of a given size one can currently use:

Sage

sage: list(A.elements_of_depth_iterator(2))
[[1, 2], [1, 3]]

Python

>>> from sage.all import *
>>> list(A.elements_of_depth_iterator(Integer(2)))
[[1, 2], [1, 3]]

Eventually the following syntax will be accepted:

Sage

sage: A.subset(size=2)              # not implemented

Python

>>> from sage.all import *
>>> A.subset(size=Integer(2))              # not implemented

Note

Internally, this uses sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets and RecursivelyEnumeratedSet_forest. At this point, iterating through this set is about twice slower than using antichains_iterator() (tested on posets.AntichainPoset(15)). The algorithm is the same (depth first search through the tree), but antichains_iterator() manually inlines things which apparently avoids some infrastructure overhead.

On the other hand, this returns a full featured enumerated set, with containment testing, etc.

See also

maximal_antichains(), chains()

antichains_iterator()

Return an iterator over the antichains of the poset.

EXAMPLES:

Sage

sage: it = posets.PentagonPoset().antichains_iterator(); it
<generator object ...antichains_iterator at ...>
sage: next(it), next(it)
([], [4])

Python

>>> from sage.all import *
>>> it = posets.PentagonPoset().antichains_iterator(); it
<generator object ...antichains_iterator at ...>
>>> next(it), next(it)
([], [4])

See also

antichains()

atkinson(a)

Return the \(a\)-spectrum of a poset whose Hasse diagram is cycle-free as an undirected graph.

Given an element \(a\) in a poset \(P\), the \(a\)-spectrum is the list of integers whose \(i\)-th term contains the number of linear extensions of \(P\) with element \(a\) located in the \(i\)-th position.

INPUT:

• self – a poset whose Hasse diagram is a forest

• a – an element of the poset

OUTPUT: the \(a\)-spectrum of this poset, returned as a list

EXAMPLES:

Sage

sage: P = Poset({0: [2], 1: [2], 2: [3, 4], 3: [], 4: []})
sage: P.atkinson(0)
[2, 2, 0, 0, 0]

sage: P = Poset({0: [1], 1: [2, 3], 2: [], 3: [], 4: [5, 6], 5: [], 6: []})
sage: P.atkinson(5)
[0, 10, 18, 24, 28, 30, 30]

sage: P = posets.AntichainPoset(10)
sage: P.atkinson(0)
[362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(2)], Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)], Integer(3): [], Integer(4): []})
>>> P.atkinson(Integer(0))
[2, 2, 0, 0, 0]

>>> P = Poset({Integer(0): [Integer(1)], Integer(1): [Integer(2), Integer(3)], Integer(2): [], Integer(3): [], Integer(4): [Integer(5), Integer(6)], Integer(5): [], Integer(6): []})
>>> P.atkinson(Integer(5))
[0, 10, 18, 24, 28, 30, 30]

>>> P = posets.AntichainPoset(Integer(10))
>>> P.atkinson(Integer(0))
[362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880, 362880]

Note

This function is the implementation of the algorithm from [At1990].

bottom()

Return the unique minimal element of the poset, if it exists.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)],Integer(1):[Integer(3)],Integer(2):[Integer(3)],Integer(3):[Integer(4)],Integer(4):[]})
>>> P.bottom() is None
True
>>> Q = Poset({Integer(0):[Integer(1)],Integer(1):[]})
>>> Q.bottom()
0

See also

has_bottom(), top()

canonical_label(algorithm=None)

Return the unique poset on the labels \(\{0, \ldots, n-1\}\) (where \(n\) is the number of elements in the poset) that is isomorphic to this poset and invariant in the isomorphism class.

INPUT:

• algorithm – string (optional); a parameter forwarded to underlying graph function to select the algorithm to use

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True)
sage: P.list()
[1, 2, 3, 4, 6, 12]
sage: Q = P.canonical_label()
sage: sorted(Q.list())
[0, 1, 2, 3, 4, 5]
sage: Q.is_isomorphic(P)
True

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")), linear_extension=True)
>>> P.list()
[1, 2, 3, 4, 6, 12]
>>> Q = P.canonical_label()
>>> sorted(Q.list())
[0, 1, 2, 3, 4, 5]
>>> Q.is_isomorphic(P)
True

Canonical labeling of (semi)lattice returns (semi)lattice:

Sage

sage: D = DiGraph({'a':['b','c']})
sage: P = Poset(D)
sage: ML = MeetSemilattice(D)
sage: P.canonical_label()
Finite poset containing 3 elements
sage: ML.canonical_label()
Finite meet-semilattice containing 3 elements

Python

>>> from sage.all import *
>>> D = DiGraph({'a':['b','c']})
>>> P = Poset(D)
>>> ML = MeetSemilattice(D)
>>> P.canonical_label()
Finite poset containing 3 elements
>>> ML.canonical_label()
Finite meet-semilattice containing 3 elements

See also

• Canonical labeling of directed graphs: canonical_label()

cardinality()

Return the number of elements in the poset.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> Poset([[Integer(1),Integer(2),Integer(3)],[Integer(4)],[Integer(4)],[Integer(4)],[]]).cardinality()
5

See also

degree_polynomial() for a more refined invariant

chain_polynomial()

Return the chain polynomial of the poset.

The coefficient of \(q^k\) is the number of chains of \(k\) elements in the poset. List of coefficients of this polynomial is also called a f-vector of the poset.

Note

This is not what has been called the chain polynomial in [St1986]. The latter is identical with the order polynomial in SageMath (order_polynomial()).

See also

f_polynomial(), order_polynomial()

EXAMPLES:

Sage

sage: P = posets.ChainPoset(3)
sage: t = P.chain_polynomial(); t
q^3 + 3*q^2 + 3*q + 1
sage: t(1) == len(list(P.chains()))
True

sage: P = posets.BooleanLattice(3)
sage: P.chain_polynomial()
6*q^4 + 18*q^3 + 19*q^2 + 8*q + 1

sage: P = posets.AntichainPoset(5)
sage: P.chain_polynomial()
5*q + 1

Python

>>> from sage.all import *
>>> P = posets.ChainPoset(Integer(3))
>>> t = P.chain_polynomial(); t
q^3 + 3*q^2 + 3*q + 1
>>> t(Integer(1)) == len(list(P.chains()))
True

>>> P = posets.BooleanLattice(Integer(3))
>>> P.chain_polynomial()
6*q^4 + 18*q^3 + 19*q^2 + 8*q + 1

>>> P = posets.AntichainPoset(Integer(5))
>>> P.chain_polynomial()
5*q + 1

chain_polytope()

Return the chain polytope of the poset self.

The chain polytope of a finite poset \(P\) is defined as the subset of \(\RR^P\) consisting of all maps \(x : P \to \RR\) satisfying

\[x(p) \geq 0 \mbox{ for all } p \in P,\]

and

\[x(p_1) + x(p_2) + \ldots + x(p_k) \leq 1 \mbox{ for all chains } p_1 < p_2 < \ldots < p_k \mbox{ in } P.\]

This polytope was defined and studied in [St1986].

EXAMPLES:

Sage

sage: P = posets.AntichainPoset(3)
sage: Q = P.chain_polytope(); Q                                             # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: P = posets.PentagonPoset()
sage: Q = P.chain_polytope(); Q                                             # needs sage.geometry.polyhedron
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices

Python

>>> from sage.all import *
>>> P = posets.AntichainPoset(Integer(3))
>>> Q = P.chain_polytope(); Q                                             # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
>>> P = posets.PentagonPoset()
>>> Q = P.chain_polytope(); Q                                             # needs sage.geometry.polyhedron
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices

chains(element_constructor=None, exclude=None)

Return the chains of the poset.

A chain of a poset is an increasing sequence of distinct elements of the poset.

INPUT:

• element_constructor – a function taking an iterable as argument (default: list)

• exclude – elements of the poset to be excluded (default: None)

OUTPUT:

The enumerated set (of type PairwiseCompatibleSubsets) of all chains of the poset, each of which is given as an element_constructor.

EXAMPLES:

Sage

sage: C = posets.PentagonPoset().chains(); C
Set of chains of Finite lattice containing 5 elements
sage: list(C)
[[], [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]]

Python

>>> from sage.all import *
>>> C = posets.PentagonPoset().chains(); C
Set of chains of Finite lattice containing 5 elements
>>> list(C)
[[], [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]]

Exclusion of elements, tuple (instead of list) as constructor:

Sage

sage: P = Poset({1: [2, 3], 2: [4], 3: [4, 5]})
sage: list(P.chains(element_constructor=tuple, exclude=[3]))
[(), (1,), (1, 2), (1, 2, 4), (1, 4), (1, 5), (2,), (2, 4), (4,), (5,)]

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(4), Integer(5)]})
>>> list(P.chains(element_constructor=tuple, exclude=[Integer(3)]))
[(), (1,), (1, 2), (1, 2, 4), (1, 4), (1, 5), (2,), (2, 4), (4,), (5,)]

To get the chains of a given size one can currently use:

Sage

sage: list(C.elements_of_depth_iterator(2))
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 4]]

Python

>>> from sage.all import *
>>> list(C.elements_of_depth_iterator(Integer(2)))
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 3], [2, 4], [3, 4]]

Eventually the following syntax will be accepted:

Sage

sage: C.subset(size=2)              # not implemented

Python

>>> from sage.all import *
>>> C.subset(size=Integer(2))              # not implemented

See also

maximal_chains(), antichains()

characteristic_polynomial()

Return the characteristic polynomial of the poset.

The poset is expected to be graded and have a bottom element.

If \(P\) is a graded poset with rank \(n\) and a unique minimal element \(\hat{0}\), then the characteristic polynomial of \(P\) is defined to be

\[\sum_{x \in P} \mu(\hat{0}, x) q^{n-\rho(x)} \in \ZZ[q],\]

where \(\rho\) is the rank function, and \(\mu\) is the Möbius function of \(P\).

See section 3.10 of [EnumComb1].

EXAMPLES:

Sage

sage: P = posets.DiamondPoset(5)
sage: P.characteristic_polynomial()
q^2 - 3*q + 2

sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6], 6: [7]})
sage: P.characteristic_polynomial()
q^4 - 2*q^3 + q

Python

>>> from sage.all import *
>>> P = posets.DiamondPoset(Integer(5))
>>> P.characteristic_polynomial()
q^2 - 3*q + 2

>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(6)], Integer(5): [Integer(6)], Integer(6): [Integer(7)]})
>>> P.characteristic_polynomial()
q^4 - 2*q^3 + q

closed_interval(x, y)

Return the list of elements \(z\) such that \(x \le z \le y\) in the poset.

EXAMPLES:

Sage

sage: P = Poset((divisors(1000), attrcall("divides")))
sage: P.closed_interval(2, 100)
[2, 4, 10, 20, 50, 100]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(1000)), attrcall("divides")))
>>> P.closed_interval(Integer(2), Integer(100))
[2, 4, 10, 20, 50, 100]

See also

open_interval()

common_lower_covers(elmts)

Return all of the common lower covers of the elements elmts.

EXAMPLES:

Sage

sage: P = Poset({0: [1,2], 1: [3], 2: [3], 3: []})
sage: P.common_lower_covers([1, 2])
[0]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1),Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): []})
>>> P.common_lower_covers([Integer(1), Integer(2)])
[0]

common_upper_covers(elmts)

Return all of the common upper covers of the elements elmts.

EXAMPLES:

Sage

sage: P = Poset({0: [1,2], 1: [3], 2: [3], 3: []})
sage: P.common_upper_covers([1, 2])
[3]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1),Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): []})
>>> P.common_upper_covers([Integer(1), Integer(2)])
[3]

comparability_graph()

Return the comparability graph of the poset.

The comparability graph is an undirected graph where vertices are the elements of the poset and there is an edge between two vertices if they are comparable in the poset.

See Wikipedia article Comparability_graph

EXAMPLES:

Sage

sage: Y = Poset({1: [2], 2: [3, 4]})
sage: g = Y.comparability_graph(); g
Comparability graph on 4 vertices
sage: Y.compare_elements(1, 3) is not None
True
sage: g.has_edge(1, 3)
True

Python

>>> from sage.all import *
>>> Y = Poset({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)]})
>>> g = Y.comparability_graph(); g
Comparability graph on 4 vertices
>>> Y.compare_elements(Integer(1), Integer(3)) is not None
True
>>> g.has_edge(Integer(1), Integer(3))
True

See also

incomparability_graph(), sage.graphs.comparability

compare_elements(x, y)

Compare \(x\) and \(y\) in the poset.

• If \(x < y\), return -1.

• If \(x = y\), return 0.

• If \(x > y\), return 1.

• If \(x\) and \(y\) are not comparable, return None.

EXAMPLES:

Sage

sage: P = Poset([[1, 2], [4], [3], [4], []])
sage: P.compare_elements(0, 0)
0
sage: P.compare_elements(0, 4)
-1
sage: P.compare_elements(4, 0)
1
sage: P.compare_elements(1, 2) is None
True

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1), Integer(2)], [Integer(4)], [Integer(3)], [Integer(4)], []])
>>> P.compare_elements(Integer(0), Integer(0))
0
>>> P.compare_elements(Integer(0), Integer(4))
-1
>>> P.compare_elements(Integer(4), Integer(0))
1
>>> P.compare_elements(Integer(1), Integer(2)) is None
True

completion_by_cuts()

Return the completion by cuts of self.

This is the smallest lattice containing the poset. This is also called the Dedekind-MacNeille completion.

See the Wikipedia article Dedekind-MacNeille completion.

OUTPUT: a finite lattice

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.completion_by_cuts().is_isomorphic(P)
True

sage: Y = Poset({1: [2], 2: [3, 4]})
sage: trafficsign = LatticePoset({1: [2], 2: [3, 4], 3: [5], 4: [5]})
sage: L = Y.completion_by_cuts()
sage: L.is_isomorphic(trafficsign)
True

sage: P = posets.SymmetricGroupBruhatOrderPoset(3)
sage: Q = P.completion_by_cuts(); Q
Finite lattice containing 7 elements

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.completion_by_cuts().is_isomorphic(P)
True

>>> Y = Poset({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)]})
>>> trafficsign = LatticePoset({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(5)]})
>>> L = Y.completion_by_cuts()
>>> L.is_isomorphic(trafficsign)
True

>>> P = posets.SymmetricGroupBruhatOrderPoset(Integer(3))
>>> Q = P.completion_by_cuts(); Q
Finite lattice containing 7 elements

See also

cuts(), irreducibles_poset()

connected_components()

Return the connected components of the poset as subposets.

EXAMPLES:

Sage

sage: P = Poset({1: [2, 3], 3: [4, 5], 6: [7, 8]})
sage: parts = sorted(P.connected_components(), key=len); parts
[Finite poset containing 3 elements,
 Finite poset containing 5 elements]
sage: parts[0].cover_relations()
[[6, 7], [6, 8]]

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(3): [Integer(4), Integer(5)], Integer(6): [Integer(7), Integer(8)]})
>>> parts = sorted(P.connected_components(), key=len); parts
[Finite poset containing 3 elements,
 Finite poset containing 5 elements]
>>> parts[Integer(0)].cover_relations()
[[6, 7], [6, 8]]

See also

disjoint_union(), is_connected()

cover_relations()

Return the list of pairs [x, y] of elements of the poset such that y covers x.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.cover_relations()
[[1, 2], [0, 2], [2, 3], [3, 4]]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.cover_relations()
[[1, 2], [0, 2], [2, 3], [3, 4]]

cover_relations_graph()

Return the (undirected) graph of cover relations.

EXAMPLES:

Sage

sage: P = Poset({0: [1, 2], 1: [3], 2: [3]})
sage: G = P.cover_relations_graph(); G
Graph on 4 vertices
sage: G.has_edge(3, 1), G.has_edge(3, 0)
(True, False)

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)]})
>>> G = P.cover_relations_graph(); G
Graph on 4 vertices
>>> G.has_edge(Integer(3), Integer(1)), G.has_edge(Integer(3), Integer(0))
(True, False)

See also

hasse_diagram()

cover_relations_iterator()

Return an iterator over the cover relations of the poset.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: type(P.cover_relations_iterator())
<class 'generator'>
sage: [z for z in P.cover_relations_iterator()]
[[1, 2], [0, 2], [2, 3], [3, 4]]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> type(P.cover_relations_iterator())
<class 'generator'>
>>> [z for z in P.cover_relations_iterator()]
[[1, 2], [0, 2], [2, 3], [3, 4]]

covers(x, y)

Return True if y covers x and False otherwise.

Element \(y\) covers \(x\) if \(x < y\) and there is no \(z\) such that \(x < z < y\).

EXAMPLES:

Sage

sage: P = Poset([[1,5], [2,6], [3], [4], [], [6,3], [4]])
sage: P.covers(1, 6)
True
sage: P.covers(1, 4)
False
sage: P.covers(1, 5)
False

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(5)], [Integer(2),Integer(6)], [Integer(3)], [Integer(4)], [], [Integer(6),Integer(3)], [Integer(4)]])
>>> P.covers(Integer(1), Integer(6))
True
>>> P.covers(Integer(1), Integer(4))
False
>>> P.covers(Integer(1), Integer(5))
False

coxeter_polynomial()

Return the Coxeter polynomial of the poset.

OUTPUT: a polynomial in one variable

The output is the characteristic polynomial of the Coxeter transformation. This polynomial only depends on the derived category of modules on the poset.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.coxeter_polynomial()                                                # needs sage.libs.flint
x^5 + x^4 + x + 1

sage: p = posets.SymmetricGroupWeakOrderPoset(3)                            # needs sage.groups
sage: p.coxeter_polynomial()                                                # needs sage.groups sage.libs.flint
x^6 + x^5 - x^3 + x + 1

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.coxeter_polynomial()                                                # needs sage.libs.flint
x^5 + x^4 + x + 1

>>> p = posets.SymmetricGroupWeakOrderPoset(Integer(3))                            # needs sage.groups
>>> p.coxeter_polynomial()                                                # needs sage.groups sage.libs.flint
x^6 + x^5 - x^3 + x + 1

See also

coxeter_transformation(), coxeter_smith_form()

coxeter_smith_form(algorithm='singular')

Return the Smith normal form of \(x\) minus the Coxeter transformation matrix.

INPUT:

• algorithm – (default: 'singular') possible values are 'singular', 'sage', 'gap', 'pari', 'maple', 'magma', 'fricas'

Beware that speed depends very much on the choice of algorithm. Sage is rather slow, Singular is faster and Pari is fast at least for small sizes.

OUTPUT: list of polynomials in one variable, each one dividing the next one

The output list is a refinement of the characteristic polynomial of the Coxeter transformation, which is its product. This list of polynomials only depends on the derived category of modules on the poset.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.coxeter_smith_form()                                                 # needs sage.libs.singular
[1, 1, 1, 1, x^5 + x^4 + x + 1]

sage: P = posets.DiamondPoset(7)
sage: prod(P.coxeter_smith_form()) == P.coxeter_polynomial()                 # needs sage.libs.singular
True

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.coxeter_smith_form()                                                 # needs sage.libs.singular
[1, 1, 1, 1, x^5 + x^4 + x + 1]

>>> P = posets.DiamondPoset(Integer(7))
>>> prod(P.coxeter_smith_form()) == P.coxeter_polynomial()                 # needs sage.libs.singular
True

See also

coxeter_transformation(), coxeter_matrix()

coxeter_transformation()

Return the Coxeter transformation of the poset.

OUTPUT: a square matrix with integer coefficients

The output is 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. This matrix is usually called the Coxeter transformation.

EXAMPLES:

Sage

sage: posets.PentagonPoset().coxeter_transformation()                       # needs sage.libs.flint
[ 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]

Python

>>> from sage.all import *
>>> posets.PentagonPoset().coxeter_transformation()                       # needs sage.libs.flint
[ 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]

See also

coxeter_polynomial(), coxeter_smith_form()

cuts()

Return the list of cuts of the poset self.

A cut is a subset \(A\) of self such that the set of lower bounds of the set of upper bounds of \(A\) is exactly \(A\).

The cuts are computed here using the maximal independent sets in the auxiliary graph defined as \(P \times [0,1]\) with an edge from \((x, 0)\) to \((y, 1)\) if and only if \(x \not\geq_P y\). See the end of section 4 in [JRJ94].

EXAMPLES:

Sage

sage: P = posets.AntichainPoset(3)
sage: Pc = P.cuts()
sage: Pc # random
[frozenset({0}),
 frozenset(),
 frozenset({0, 1, 2}),
 frozenset({2}),
 frozenset({1})]
sage: sorted(list(c) for c in Pc)
[[], [0], [0, 1, 2], [1], [2]]

Python

>>> from sage.all import *
>>> P = posets.AntichainPoset(Integer(3))
>>> Pc = P.cuts()
>>> Pc # random
[frozenset({0}),
 frozenset(),
 frozenset({0, 1, 2}),
 frozenset({2}),
 frozenset({1})]
>>> sorted(list(c) for c in Pc)
[[], [0], [0, 1, 2], [1], [2]]

See also

completion_by_cuts()

degree_polynomial()

Return the generating polynomial of degrees of vertices in self.

This is the sum

\[\sum_{v \in P} x^{\operatorname{in}(v)} y^{\operatorname{out}(v)},\]

where in(v) and out(v) are the number of incoming and outgoing edges at vertex \(v\) in the Hasse diagram of \(P\).

Because this polynomial is multiplicative for Cartesian product of posets, it is useful to help see if the poset can be isomorphic to a Cartesian product.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.degree_polynomial()
x^2 + 3*x*y + y^2

sage: P = posets.BooleanLattice(4)
sage: P.degree_polynomial().factor()
(x + y)^4

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.degree_polynomial()
x^2 + 3*x*y + y^2

>>> P = posets.BooleanLattice(Integer(4))
>>> P.degree_polynomial().factor()
(x + y)^4

See also

cardinality() for the value at \((x, y) = (1, 1)\)

diamonds()

Return the list of diamonds of self.

A diamond is the following subgraph of the Hasse diagram:

  z
 / \
x   y
 \ /
  w

Thus each edge represents a cover relation in the Hasse diagram. We represent this as the tuple \((w, x, y, z)\).

OUTPUT: a tuple with

• a list of all diamonds in the Hasse Diagram,

• a boolean checking that every \(w,x,y\) that form a V, there is a unique element \(z\), which completes the diamond.

EXAMPLES:

Sage

sage: P = Poset({0: [1,2], 1: [3], 2: [3], 3: []})
sage: P.diamonds()
([(0, 1, 2, 3)], True)

sage: P = posets.YoungDiagramPoset(Partition([3, 2, 2]))                    # needs sage.combinat
sage: P.diamonds()                                                          # needs sage.combinat
([((0, 0), (0, 1), (1, 0), (1, 1)), ((1, 0), (1, 1), (2, 0), (2, 1))], False)

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1),Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): []})
>>> P.diamonds()
([(0, 1, 2, 3)], True)

>>> P = posets.YoungDiagramPoset(Partition([Integer(3), Integer(2), Integer(2)]))                    # needs sage.combinat
>>> P.diamonds()                                                          # needs sage.combinat
([((0, 0), (0, 1), (1, 0), (1, 1)), ((1, 0), (1, 1), (2, 0), (2, 1))], False)

dilworth_decomposition()

Return a partition of the points into the minimal number of chains.

According to Dilworth’s theorem, the points of a poset can be partitioned into \(\alpha\) chains, where \(\alpha\) is the cardinality of its largest antichain. This method returns such a partition.

See Wikipedia article Dilworth%27s_theorem.

ALGORITHM:

We build a bipartite graph in which a vertex \(v\) of the poset is represented by two vertices \(v^-,v^+\). For any two \(u,v\) such that \(u<v\) in the poset we add an edge \(v^+u^-\).

A matching in this graph is equivalent to a partition of the poset into chains: indeed, a chain \(v_1...v_k\) gives rise to the matching \(v_1^+v_2^-,v_2^+v_3^-,...\), and from a matching one can build the union of chains.

According to Dilworth’s theorem, the number of chains is equal to \(\alpha\) (the posets’ width).

EXAMPLES:

Sage

sage: p = posets.BooleanLattice(4)
sage: p.width()                                                             # needs networkx
6
sage: p.dilworth_decomposition()  # random                                  # needs networkx
[[7, 6, 4], [11, 3], [12, 8, 0], [13, 9, 1], [14, 10, 2], [15, 5]]

Python

>>> from sage.all import *
>>> p = posets.BooleanLattice(Integer(4))
>>> p.width()                                                             # needs networkx
6
>>> p.dilworth_decomposition()  # random                                  # needs networkx
[[7, 6, 4], [11, 3], [12, 8, 0], [13, 9, 1], [14, 10, 2], [15, 5]]

See also

level_sets() to return elements grouped to antichains.

dimension(certificate, solver, integrality_tolerance=False)

Return the dimension of the Poset.

The (Dushnik-Miller) dimension of a poset is the minimal number of total orders so that the poset is their “intersection”. More precisely, the dimension of a poset defined on a set \(X\) of points is the smallest integer \(n\) such that there exist linear extensions \(P_1,...,P_n\) of \(P\) satisfying:

\[u\leq_P v\ \text{if and only if }\ \forall i, u\leq_{P_i} v\]

For more information, see the Wikipedia article Order_dimension.

INPUT:

• certificate – boolean (default: False); whether to return an integer (the dimension) or a certificate, i.e. a smallest set of linear extensions

• solver – (default: None) specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• integrality_tolerance – parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values()

Note

The speed of this function greatly improves when more efficient MILP solvers (e.g. Gurobi, CPLEX) are installed. See MixedIntegerLinearProgram for more information.

Note

Prior to version 8.3 this returned only realizer with certificate=True. Now it returns a pair having a realizer as the second element. See Issue #25588 for details.

ALGORITHM:

As explained [FT00], the dimension of a poset is equal to the (weak) chromatic number of a hypergraph. More precisely:

Let \(inc(P)\) be the set of (ordered) pairs of incomparable elements of \(P\), i.e. all \(uv\) and \(vu\) such that \(u\not \leq_P v\) and \(v\not \leq_P u\). Any linear extension of \(P\) is a total order on \(X\) that can be seen as the union of relations from \(P\) along with some relations from \(inc(P)\). Thus, the dimension of \(P\) is the smallest number of linear extensions of \(P\) which cover all points of \(inc(P)\).

Consequently, \(dim(P)\) is equal to the chromatic number of the hypergraph \(\mathcal H_{inc}\), where \(\mathcal H_{inc}\) is the hypergraph defined on \(inc(P)\) whose sets are all \(S\subseteq inc(P)\) such that \(P\cup S\) is not acyclic.

We solve this problem through a Mixed Integer Linear Program.

The problem is known to be NP-complete.

EXAMPLES:

We create a poset, compute a set of linear extensions and check that we get back the poset from them:

Sage

sage: P = Poset([[1,4], [3], [4,5,3], [6], [], [6], []])
sage: P.dimension()                                                         # needs networkx
3
sage: dim, L = P.dimension(certificate=True)                                # needs sage.numerical.mip
sage: L  # random -- architecture-dependent                                 # needs sage.numerical.mip
[[0, 2, 4, 5, 1, 3, 6], [2, 5, 0, 1, 3, 4, 6], [0, 1, 2, 3, 5, 6, 4]]
sage: Poset( (L[0], lambda x, y: all(l.index(x) < l.index(y) for l in L)) ) == P        # needs sage.numerical.mip
True

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(4)], [Integer(3)], [Integer(4),Integer(5),Integer(3)], [Integer(6)], [], [Integer(6)], []])
>>> P.dimension()                                                         # needs networkx
3
>>> dim, L = P.dimension(certificate=True)                                # needs sage.numerical.mip
>>> L  # random -- architecture-dependent                                 # needs sage.numerical.mip
[[0, 2, 4, 5, 1, 3, 6], [2, 5, 0, 1, 3, 4, 6], [0, 1, 2, 3, 5, 6, 4]]
>>> Poset( (L[Integer(0)], lambda x, y: all(l.index(x) < l.index(y) for l in L)) ) == P        # needs sage.numerical.mip
True

According to Schnyder’s theorem, the incidence poset (of height 2) of a graph has dimension \(\leq 3\) if and only if the graph is planar:

Sage

sage: G = graphs.CompleteGraph(4)
sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges(sort=True)}))
sage: P.dimension()                                                         # needs networkx
3

sage: G = graphs.CompleteBipartiteGraph(3,3)
sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges(sort=True)}))
sage: P.dimension()  # not tested (around 4s with CPLEX)
4

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges(sort=True)}))
>>> P.dimension()                                                         # needs networkx
3

>>> G = graphs.CompleteBipartiteGraph(Integer(3),Integer(3))
>>> P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges(sort=True)}))
>>> P.dimension()  # not tested (around 4s with CPLEX)
4

disjoint_union(other, labels='pairs')

Return a poset isomorphic to disjoint union (also called direct sum) of the poset with other.

The disjoint union of \(P\) and \(Q\) is a poset that contains every element and relation from both \(P\) and \(Q\), and where every element of \(P\) is incomparable to every element of \(Q\).

Mathematically, it is only defined when \(P\) and \(Q\) have no common element; here we force that by giving them different names in the resulting poset.

INPUT:

• other – poset

• labels – (defaults to ‘pairs’) If set to ‘pairs’, each element v in this poset will be named (0,v) and each element u in other will be named (1,u) in the result. If set to ‘integers’, the elements of the result will be relabeled with consecutive integers.

EXAMPLES:

Sage

sage: P1 = Poset({'a': 'b'})
sage: P2 = Poset({'c': 'd'})
sage: P = P1.disjoint_union(P2); P
Finite poset containing 4 elements
sage: sorted(P.cover_relations())
[[(0, 'a'), (0, 'b')], [(1, 'c'), (1, 'd')]]
sage: P = P1.disjoint_union(P2, labels='integers')
sage: P.cover_relations()
[[2, 3], [0, 1]]

sage: N5 = posets.PentagonPoset(); N5
Finite lattice containing 5 elements
sage: N5.disjoint_union(N5)  # Union of lattices is not a lattice
Finite poset containing 10 elements

Python

>>> from sage.all import *
>>> P1 = Poset({'a': 'b'})
>>> P2 = Poset({'c': 'd'})
>>> P = P1.disjoint_union(P2); P
Finite poset containing 4 elements
>>> sorted(P.cover_relations())
[[(0, 'a'), (0, 'b')], [(1, 'c'), (1, 'd')]]
>>> P = P1.disjoint_union(P2, labels='integers')
>>> P.cover_relations()
[[2, 3], [0, 1]]

>>> N5 = posets.PentagonPoset(); N5
Finite lattice containing 5 elements
>>> N5.disjoint_union(N5)  # Union of lattices is not a lattice
Finite poset containing 10 elements

We show how to get literally direct sum with elements untouched:

Sage

sage: P = P1.disjoint_union(P2).relabel(lambda x: x[1])
sage: sorted(P.cover_relations())
[['a', 'b'], ['c', 'd']]

Python

>>> from sage.all import *
>>> P = P1.disjoint_union(P2).relabel(lambda x: x[Integer(1)])
>>> sorted(P.cover_relations())
[['a', 'b'], ['c', 'd']]

See also

connected_components()

dual()

Return the dual poset of the given poset.

In the dual of a poset \(P\) we have \(x \le y\) iff \(y \le x\) in \(P\).

EXAMPLES:

Sage

sage: P = Poset({1: [2, 3], 3: [4]})
sage: P.cover_relations()
[[1, 2], [1, 3], [3, 4]]
sage: Q = P.dual()
sage: Q.cover_relations()
[[4, 3], [3, 1], [2, 1]]

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(3): [Integer(4)]})
>>> P.cover_relations()
[[1, 2], [1, 3], [3, 4]]
>>> Q = P.dual()
>>> Q.cover_relations()
[[4, 3], [3, 1], [2, 1]]

Dual of a lattice is a lattice; dual of a meet-semilattice is join-semilattice and vice versa. Also the dual of a (non-)facade poset is again (non-)facade:

Sage

sage: V = MeetSemilattice({1: [2, 3]}, facade=False)
sage: A = V.dual(); A
Finite join-semilattice containing 3 elements
sage: A(2) < A(1)
True

Python

>>> from sage.all import *
>>> V = MeetSemilattice({Integer(1): [Integer(2), Integer(3)]}, facade=False)
>>> A = V.dual(); A
Finite join-semilattice containing 3 elements
>>> A(Integer(2)) < A(Integer(1))
True

See also

is_self_dual()

evacuation()

Compute evacuation on the linear extension associated to the poset self.

OUTPUT: an isomorphic poset, with the same default linear extension

Evacuation is defined on a poset self of size \(n\) by applying the evacuation operator \((\tau_1 \cdots \tau_{n-1}) (\tau_1 \cdots \tau_{n-2}) \cdots (\tau_1)\), to the default linear extension \(\pi\) of self (see evacuation()), and relabeling self accordingly. For more details see [Stan2009].

EXAMPLES:

Sage

sage: P = Poset(([1,2], [[1,2]]), linear_extension=True, facade=False)
sage: P.evacuation()
Finite poset containing 2 elements with distinguished linear extension
sage: P.evacuation() == P
True

sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]]), linear_extension=True, facade=False)
sage: P.list()
[1, 2, 3, 4, 5, 6, 7]
sage: Q = P.evacuation(); Q
Finite poset containing 7 elements with distinguished linear extension
sage: Q.cover_relations()
[[1, 2], [1, 3], [2, 5], [3, 4], [3, 6], [4, 7], [6, 7]]

Python

>>> from sage.all import *
>>> P = Poset(([Integer(1),Integer(2)], [[Integer(1),Integer(2)]]), linear_extension=True, facade=False)
>>> P.evacuation()
Finite poset containing 2 elements with distinguished linear extension
>>> P.evacuation() == P
True

>>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)], [[Integer(1),Integer(2)],[Integer(1),Integer(4)],[Integer(2),Integer(3)],[Integer(2),Integer(5)],[Integer(3),Integer(6)],[Integer(4),Integer(7)],[Integer(5),Integer(6)]]), linear_extension=True, facade=False)
>>> P.list()
[1, 2, 3, 4, 5, 6, 7]
>>> Q = P.evacuation(); Q
Finite poset containing 7 elements with distinguished linear extension
>>> Q.cover_relations()
[[1, 2], [1, 3], [2, 5], [3, 4], [3, 6], [4, 7], [6, 7]]

Note that the results depend on the linear extension associated to the poset:

Sage

sage: P = Poset(([1,2,3,4,5,6,7], [[1,2],[1,4],[2,3],[2,5],[3,6],[4,7],[5,6]]))
sage: P.list()
[1, 2, 3, 5, 6, 4, 7]
sage: Q = P.evacuation(); Q
Finite poset containing 7 elements with distinguished linear extension
sage: Q.cover_relations()
[[1, 2], [1, 5], [2, 3], [5, 6], [5, 4], [6, 7], [4, 7]]

Python

>>> from sage.all import *
>>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7)], [[Integer(1),Integer(2)],[Integer(1),Integer(4)],[Integer(2),Integer(3)],[Integer(2),Integer(5)],[Integer(3),Integer(6)],[Integer(4),Integer(7)],[Integer(5),Integer(6)]]))
>>> P.list()
[1, 2, 3, 5, 6, 4, 7]
>>> Q = P.evacuation(); Q
Finite poset containing 7 elements with distinguished linear extension
>>> Q.cover_relations()
[[1, 2], [1, 5], [2, 3], [5, 6], [5, 4], [6, 7], [4, 7]]

Here is an example of a poset where the elements are not labelled by \(\{1,2,\ldots,n\}\):

Sage

sage: P = Poset((divisors(15), attrcall("divides")), linear_extension = True)
sage: P.list()
[1, 3, 5, 15]
sage: Q = P.evacuation(); Q
Finite poset containing 4 elements with distinguished linear extension
sage: Q.cover_relations()
[[1, 3], [1, 5], [3, 15], [5, 15]]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(15)), attrcall("divides")), linear_extension = True)
>>> P.list()
[1, 3, 5, 15]
>>> Q = P.evacuation(); Q
Finite poset containing 4 elements with distinguished linear extension
>>> Q.cover_relations()
[[1, 3], [1, 5], [3, 15], [5, 15]]

See also

• linear_extension()

• with_linear_extension() and the linear_extension option of Poset()

• evacuation()

• promotion()

AUTHOR:

• Anne Schilling (2012-02-18)

f_polynomial()

Return the \(f\)-polynomial of the poset.

The poset is expected to be bounded.

This is the \(f\)-polynomial of the order complex of the poset minus its bounds.

The coefficient of \(q^i\) is the number of chains of \(i+1\) elements containing both bounds of the poset.

Note

This is slightly different from the fPolynomial method in Macaulay2.

EXAMPLES:

Sage

sage: P = posets.DiamondPoset(5)
sage: P.f_polynomial()
3*q^2 + q

sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [7], 6: [7]})
sage: P.f_polynomial()
q^4 + 4*q^3 + 5*q^2 + q

Python

>>> from sage.all import *
>>> P = posets.DiamondPoset(Integer(5))
>>> P.f_polynomial()
3*q^2 + q

>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(6)], Integer(5): [Integer(7)], Integer(6): [Integer(7)]})
>>> P.f_polynomial()
q^4 + 4*q^3 + 5*q^2 + q

See also

is_bounded(), h_polynomial(), order_complex(), sage.topology.cell_complex.GenericCellComplex.f_vector()

factor()

Factor the poset as a Cartesian product of smaller posets.

This only works for connected posets for the moment.

The decomposition of a connected poset as a Cartesian product of posets (prime in the sense that they cannot be written as Cartesian products) is unique up to reordering and isomorphism.

OUTPUT: list of posets

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: Q = P*P
sage: Q.factor()
[Finite poset containing 5 elements,
 Finite poset containing 5 elements]

sage: P1 = posets.ChainPoset(3)
sage: P2 = posets.ChainPoset(7)
sage: P1.factor()
[Finite lattice containing 3 elements]
sage: (P1 * P2).factor()
[Finite poset containing 7 elements,
 Finite poset containing 3 elements]

sage: P = posets.TamariLattice(4)
sage: (P*P).factor()
[Finite poset containing 14 elements,
Finite poset containing 14 elements]

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> Q = P*P
>>> Q.factor()
[Finite poset containing 5 elements,
 Finite poset containing 5 elements]

>>> P1 = posets.ChainPoset(Integer(3))
>>> P2 = posets.ChainPoset(Integer(7))
>>> P1.factor()
[Finite lattice containing 3 elements]
>>> (P1 * P2).factor()
[Finite poset containing 7 elements,
 Finite poset containing 3 elements]

>>> P = posets.TamariLattice(Integer(4))
>>> (P*P).factor()
[Finite poset containing 14 elements,
Finite poset containing 14 elements]

See also

product()

REFERENCES:

[Feig1986]

Joan Feigenbaum, Directed Cartesian-Product Graphs have Unique Factorizations that can be computed in Polynomial Time, Discrete Applied Mathematics 15 (1986) 105-110 doi:10.1016/0166-218X(86)90023-5

flag_f_polynomial()

Return the flag \(f\)-polynomial of the poset.

The poset is expected to be bounded and ranked.

This is the sum, over all chains containing both bounds, of a monomial encoding the ranks of the elements of the chain.

More precisely, if \(P\) is a bounded ranked poset, then the flag \(f\)-polynomial of \(P\) is defined as the polynomial

\[\begin{split}\sum_{\substack{p_0 < p_1 < \ldots < p_k, \\ p_0 = \min P, \ p_k = \max P}} x_{\rho(p_1)} x_{\rho(p_2)} \cdots x_{\rho(p_k)} \in \ZZ[x_1, x_2, \cdots, x_n],\end{split}\]

where \(\min P\) and \(\max P\) are (respectively) the minimum and the maximum of \(P\), where \(\rho\) is the rank function of \(P\) (normalized to satisfy \(\rho(\min P) = 0\)), and where \(n\) is the rank of \(\max P\). (Note that the indeterminate \(x_0\) does not actually appear in the polynomial.)

For technical reasons, the polynomial is returned in the slightly larger ring \(\ZZ[x_0, x_1, x_2, \cdots, x_{n+1}]\) by this method.

See Wikipedia article h-vector.

EXAMPLES:

Sage

sage: P = posets.DiamondPoset(5)
sage: P.flag_f_polynomial()
3*x1*x2 + x2

sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]})
sage: fl = P.flag_f_polynomial(); fl
2*x1*x2*x3 + 2*x1*x3 + 2*x2*x3 + x3
sage: q = polygen(ZZ,'q')
sage: fl(q,q,q,q) == P.f_polynomial()
True

sage: P = Poset({1: [2, 3, 4], 2: [5], 3: [5], 4: [5], 5: [6]})
sage: P.flag_f_polynomial()
3*x1*x2*x3 + 3*x1*x3 + x2*x3 + x3

Python

>>> from sage.all import *
>>> P = posets.DiamondPoset(Integer(5))
>>> P.flag_f_polynomial()
3*x1*x2 + x2

>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(6)], Integer(5): [Integer(6)]})
>>> fl = P.flag_f_polynomial(); fl
2*x1*x2*x3 + 2*x1*x3 + 2*x2*x3 + x3
>>> q = polygen(ZZ,'q')
>>> fl(q,q,q,q) == P.f_polynomial()
True

>>> P = Poset({Integer(1): [Integer(2), Integer(3), Integer(4)], Integer(2): [Integer(5)], Integer(3): [Integer(5)], Integer(4): [Integer(5)], Integer(5): [Integer(6)]})
>>> P.flag_f_polynomial()
3*x1*x2*x3 + 3*x1*x3 + x2*x3 + x3

See also

is_bounded(), flag_h_polynomial()

flag_h_polynomial()

Return the flag \(h\)-polynomial of the poset.

The poset is expected to be bounded and ranked.

If \(P\) is a bounded ranked poset whose maximal element has rank \(n\) (where the minimal element is set to have rank \(0\)), then the flag \(h\)-polynomial of \(P\) is defined as the polynomial

\[\prod_{k=1}^n (1-x_k) \cdot f \left(\frac{x_1}{1-x_1}, \frac{x_2}{1-x_2}, \cdots, \frac{x_n}{1-x_n}\right) \in \ZZ[x_1, x_2, \cdots, x_n],\]

where \(f\) is the flag \(f\)-polynomial of \(P\) (see flag_f_polynomial()).

For technical reasons, the polynomial is returned in the slightly larger ring \(\QQ[x_0, x_1, x_2, \cdots, x_{n+1}]\) by this method.

See Wikipedia article h-vector.

EXAMPLES:

Sage

sage: P = posets.DiamondPoset(5)
sage: P.flag_h_polynomial()
2*x1*x2 + x2

sage: P = Poset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]})
sage: fl = P.flag_h_polynomial(); fl
-x1*x2*x3 + x1*x3 + x2*x3 + x3
sage: q = polygen(ZZ,'q')
sage: fl(q,q,q,q) == P.h_polynomial()
True

sage: P = Poset({1: [2, 3, 4], 2: [5], 3: [5], 4: [5], 5: [6]})
sage: P.flag_h_polynomial()
2*x1*x3 + x3

sage: P = posets.ChainPoset(4)
sage: P.flag_h_polynomial()
x3

Python

>>> from sage.all import *
>>> P = posets.DiamondPoset(Integer(5))
>>> P.flag_h_polynomial()
2*x1*x2 + x2

>>> P = Poset({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(6)], Integer(5): [Integer(6)]})
>>> fl = P.flag_h_polynomial(); fl
-x1*x2*x3 + x1*x3 + x2*x3 + x3
>>> q = polygen(ZZ,'q')
>>> fl(q,q,q,q) == P.h_polynomial()
True

>>> P = Poset({Integer(1): [Integer(2), Integer(3), Integer(4)], Integer(2): [Integer(5)], Integer(3): [Integer(5)], Integer(4): [Integer(5)], Integer(5): [Integer(6)]})
>>> P.flag_h_polynomial()
2*x1*x3 + x3

>>> P = posets.ChainPoset(Integer(4))
>>> P.flag_h_polynomial()
x3

See also

is_bounded(), flag_f_polynomial()

frank_network()

Return Frank’s network of the poset.

This is defined in Section 8 of [BF1999].

OUTPUT:

A pair \((G, e)\), where \(G\) is Frank’s network of \(P\) encoded as a DiGraph, and \(e\) is the cost function on its edges encoded as a dictionary (indexed by these edges, which in turn are encoded as tuples of 2 vertices).

Note

Frank’s network of \(P\) is a certain directed graph with \(2|P| + 2\) vertices, defined in Section 8 of [BF1999]. Its set of vertices consists of two vertices \((0, p)\) and \((1, p)\) for each element \(p\) of \(P\), as well as two vertices \((-1, 0)\) and \((2, 0)\). (These notations are not the ones used in [BF1999]; see the table below for their relation.) The edges are:

• for each \(p\) in \(P\), an edge from \((-1, 0)\) to \((0, p)\);

• for each \(p\) in \(P\), an edge from \((1, p)\) to \((2, 0)\);

• for each \(p\) and \(q\) in \(P\) such that \(p \geq q\), an edge from \((0, p)\) to \((1, q)\).

We make this digraph into a network in the sense of flow theory as follows: The vertex \((-1, 0)\) is considered as the source of this network, and the vertex \((2, 0)\) as the sink. The cost function is defined to be \(1\) on the edge from \((0, p)\) to \((1, p)\) for each \(p \in P\), and to be \(0\) on every other edge. The capacity is \(1\) on each edge. Here is how to translate this notations into that used in [BF1999]:

our notations                    [BF1999]
   (-1, 0)                          s
   (0, p)                          x_p
   (1, p)                          y_p
   (2, 0)                           t
    a[e]                           a(e)

EXAMPLES:

Sage

sage: ps = [[16,12,14,-13],[[12,14],[14,-13],[12,16],[16,-13]]]
sage: G, e = Poset(ps).frank_network()
sage: G.edges(sort=True)
[((-1, 0), (0, -13), None), ((-1, 0), (0, 12), None),
 ((-1, 0), (0, 14), None), ((-1, 0), (0, 16), None),
 ((0, -13), (1, -13), None), ((0, -13), (1, 12), None),
 ((0, -13), (1, 14), None), ((0, -13), (1, 16), None),
 ((0, 12), (1, 12), None), ((0, 14), (1, 12), None),
 ((0, 14), (1, 14), None), ((0, 16), (1, 12), None),
 ((0, 16), (1, 16), None), ((1, -13), (2, 0), None),
 ((1, 12), (2, 0), None), ((1, 14), (2, 0), None),
 ((1, 16), (2, 0), None)]
sage: e
{((-1, 0), (0, -13)): 0,
 ((-1, 0), (0, 12)): 0,
 ((-1, 0), (0, 14)): 0,
 ((-1, 0), (0, 16)): 0,
 ((0, -13), (1, -13)): 1,
 ((0, -13), (1, 12)): 0,
 ((0, -13), (1, 14)): 0,
 ((0, -13), (1, 16)): 0,
 ((0, 12), (1, 12)): 1,
 ((0, 14), (1, 12)): 0,
 ((0, 14), (1, 14)): 1,
 ((0, 16), (1, 12)): 0,
 ((0, 16), (1, 16)): 1,
 ((1, -13), (2, 0)): 0,
 ((1, 12), (2, 0)): 0,
 ((1, 14), (2, 0)): 0,
 ((1, 16), (2, 0)): 0}
sage: qs = [[1,2,3,4,5,6,7,8,9],[[1,3],[3,4],[5,7],[1,9],[2,3]]]
sage: Poset(qs).frank_network()
(Digraph on 20 vertices,
 {((-1, 0), (0, 1)): 0,
  ((-1, 0), (0, 2)): 0,
  ((-1, 0), (0, 3)): 0,
  ((-1, 0), (0, 4)): 0,
  ((-1, 0), (0, 5)): 0,
  ((-1, 0), (0, 6)): 0,
  ((-1, 0), (0, 7)): 0,
  ((-1, 0), (0, 8)): 0,
  ((-1, 0), (0, 9)): 0,
  ((0, 1), (1, 1)): 1,
  ((0, 2), (1, 2)): 1,
  ((0, 3), (1, 1)): 0,
  ((0, 3), (1, 2)): 0,
  ((0, 3), (1, 3)): 1,
  ((0, 4), (1, 1)): 0,
  ((0, 4), (1, 2)): 0,
  ((0, 4), (1, 3)): 0,
  ((0, 4), (1, 4)): 1,
  ((0, 5), (1, 5)): 1,
  ((0, 6), (1, 6)): 1,
  ((0, 7), (1, 5)): 0,
  ((0, 7), (1, 7)): 1,
  ((0, 8), (1, 8)): 1,
  ((0, 9), (1, 1)): 0,
  ((0, 9), (1, 9)): 1,
  ((1, 1), (2, 0)): 0,
  ((1, 2), (2, 0)): 0,
  ((1, 3), (2, 0)): 0,
  ((1, 4), (2, 0)): 0,
  ((1, 5), (2, 0)): 0,
  ((1, 6), (2, 0)): 0,
  ((1, 7), (2, 0)): 0,
  ((1, 8), (2, 0)): 0,
  ((1, 9), (2, 0)): 0})

Python

>>> from sage.all import *
>>> ps = [[Integer(16),Integer(12),Integer(14),-Integer(13)],[[Integer(12),Integer(14)],[Integer(14),-Integer(13)],[Integer(12),Integer(16)],[Integer(16),-Integer(13)]]]
>>> G, e = Poset(ps).frank_network()
>>> G.edges(sort=True)
[((-1, 0), (0, -13), None), ((-1, 0), (0, 12), None),
 ((-1, 0), (0, 14), None), ((-1, 0), (0, 16), None),
 ((0, -13), (1, -13), None), ((0, -13), (1, 12), None),
 ((0, -13), (1, 14), None), ((0, -13), (1, 16), None),
 ((0, 12), (1, 12), None), ((0, 14), (1, 12), None),
 ((0, 14), (1, 14), None), ((0, 16), (1, 12), None),
 ((0, 16), (1, 16), None), ((1, -13), (2, 0), None),
 ((1, 12), (2, 0), None), ((1, 14), (2, 0), None),
 ((1, 16), (2, 0), None)]
>>> e
{((-1, 0), (0, -13)): 0,
 ((-1, 0), (0, 12)): 0,
 ((-1, 0), (0, 14)): 0,
 ((-1, 0), (0, 16)): 0,
 ((0, -13), (1, -13)): 1,
 ((0, -13), (1, 12)): 0,
 ((0, -13), (1, 14)): 0,
 ((0, -13), (1, 16)): 0,
 ((0, 12), (1, 12)): 1,
 ((0, 14), (1, 12)): 0,
 ((0, 14), (1, 14)): 1,
 ((0, 16), (1, 12)): 0,
 ((0, 16), (1, 16)): 1,
 ((1, -13), (2, 0)): 0,
 ((1, 12), (2, 0)): 0,
 ((1, 14), (2, 0)): 0,
 ((1, 16), (2, 0)): 0}
>>> qs = [[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7),Integer(8),Integer(9)],[[Integer(1),Integer(3)],[Integer(3),Integer(4)],[Integer(5),Integer(7)],[Integer(1),Integer(9)],[Integer(2),Integer(3)]]]
>>> Poset(qs).frank_network()
(Digraph on 20 vertices,
 {((-1, 0), (0, 1)): 0,
  ((-1, 0), (0, 2)): 0,
  ((-1, 0), (0, 3)): 0,
  ((-1, 0), (0, 4)): 0,
  ((-1, 0), (0, 5)): 0,
  ((-1, 0), (0, 6)): 0,
  ((-1, 0), (0, 7)): 0,
  ((-1, 0), (0, 8)): 0,
  ((-1, 0), (0, 9)): 0,
  ((0, 1), (1, 1)): 1,
  ((0, 2), (1, 2)): 1,
  ((0, 3), (1, 1)): 0,
  ((0, 3), (1, 2)): 0,
  ((0, 3), (1, 3)): 1,
  ((0, 4), (1, 1)): 0,
  ((0, 4), (1, 2)): 0,
  ((0, 4), (1, 3)): 0,
  ((0, 4), (1, 4)): 1,
  ((0, 5), (1, 5)): 1,
  ((0, 6), (1, 6)): 1,
  ((0, 7), (1, 5)): 0,
  ((0, 7), (1, 7)): 1,
  ((0, 8), (1, 8)): 1,
  ((0, 9), (1, 1)): 0,
  ((0, 9), (1, 9)): 1,
  ((1, 1), (2, 0)): 0,
  ((1, 2), (2, 0)): 0,
  ((1, 3), (2, 0)): 0,
  ((1, 4), (2, 0)): 0,
  ((1, 5), (2, 0)): 0,
  ((1, 6), (2, 0)): 0,
  ((1, 7), (2, 0)): 0,
  ((1, 8), (2, 0)): 0,
  ((1, 9), (2, 0)): 0})

AUTHOR:

• Darij Grinberg (2013-05-09)

ge(x, y)

Return True if \(x\) is greater than or equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_gequal(3, 1)
True
sage: P.is_gequal(2, 2)
True
sage: P.is_gequal(0, 1)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_gequal(Integer(3), Integer(1))
True
>>> P.is_gequal(Integer(2), Integer(2))
True
>>> P.is_gequal(Integer(0), Integer(1))
False

See also

is_greater_than(), is_lequal().

graphviz_string(graph_string='graph', edge_string='--')

Return a representation in the DOT language, ready to render in graphviz.

See http://www.graphviz.org/doc/info/lang.html for more information about graphviz.

EXAMPLES:

Sage

sage: P = Poset({'a':['b'],'b':['d'],'c':['d'],'d':['f'],'e':['f'],'f':[]})
sage: print(P.graphviz_string())
graph {
"f";"d";"b";"a";"c";"e";
"f"--"e";"d"--"c";"b"--"a";"d"--"b";"f"--"d";
}

Python

>>> from sage.all import *
>>> P = Poset({'a':['b'],'b':['d'],'c':['d'],'d':['f'],'e':['f'],'f':[]})
>>> print(P.graphviz_string())
graph {
"f";"d";"b";"a";"c";"e";
"f"--"e";"d"--"c";"b"--"a";"d"--"b";"f"--"d";
}

greene_shape()

Return the Greene-Kleitman partition of self.

The Greene-Kleitman partition of a finite poset \(P\) is the partition \((c_1 - c_0, c_2 - c_1, c_3 - c_2, \ldots)\), where \(c_k\) is the maximum cardinality of a union of \(k\) chains of \(P\). Equivalently, this is the conjugate of the partition \((a_1 - a_0, a_2 - a_1, a_3 - a_2, \ldots)\), where \(a_k\) is the maximum cardinality of a union of \(k\) antichains of \(P\).

See many sources, e. g., [BF1999], for proofs of this equivalence.

EXAMPLES:

Sage

sage: # needs sage.combinat
sage: P = Poset([[3,2,1], [[3,1],[2,1]]])
sage: P.greene_shape()
[2, 1]
sage: P = Poset([[1,2,3,4], [[1,4],[2,4],[4,3]]])
sage: P.greene_shape()
[3, 1]
sage: P = Poset([[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],
....:            [[1,4],[2,4],[4,3]]])
sage: P.greene_shape()
[3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: P = Poset([[],[]])
sage: P.greene_shape()
[]

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> P = Poset([[Integer(3),Integer(2),Integer(1)], [[Integer(3),Integer(1)],[Integer(2),Integer(1)]]])
>>> P.greene_shape()
[2, 1]
>>> P = Poset([[Integer(1),Integer(2),Integer(3),Integer(4)], [[Integer(1),Integer(4)],[Integer(2),Integer(4)],[Integer(4),Integer(3)]]])
>>> P.greene_shape()
[3, 1]
>>> P = Poset([[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6),Integer(7),Integer(8),Integer(9),Integer(10),Integer(11),Integer(12),Integer(13),Integer(14),Integer(15),Integer(16),Integer(17),Integer(18),Integer(19),Integer(20),Integer(21),Integer(22)],
...            [[Integer(1),Integer(4)],[Integer(2),Integer(4)],[Integer(4),Integer(3)]]])
>>> P.greene_shape()
[3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
>>> P = Poset([[],[]])
>>> P.greene_shape()
[]

AUTHOR:

• Darij Grinberg (2013-05-09)

gt(x, y)

Return True if \(x\) is greater than but not equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_greater_than(3, 1)
True
sage: P.is_greater_than(1, 2)
False
sage: P.is_greater_than(3, 3)
False
sage: P.is_greater_than(0, 1)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_greater_than(Integer(3), Integer(1))
True
>>> P.is_greater_than(Integer(1), Integer(2))
False
>>> P.is_greater_than(Integer(3), Integer(3))
False
>>> P.is_greater_than(Integer(0), Integer(1))
False

For non-facade posets also > works:

Sage

sage: P = Poset({3: [1, 2]}, facade=False)
sage: P(2) > P(3)
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(3): [Integer(1), Integer(2)]}, facade=False)
>>> P(Integer(2)) > P(Integer(3))
True

See also

is_gequal(), is_less_than().

h_polynomial()

Return the \(h\)-polynomial of a bounded poset self.

This is the \(h\)-polynomial of the order complex of the poset minus its bounds.

This is related to the \(f\)-polynomial by a simple change of variables:

\[h(q) = (1-q)^{\deg f} f \left( \frac{q}{1-q} \right),\]

where \(f\) and \(h\) denote the \(f\)-polynomial and the \(h\)-polynomial, respectively.

See Wikipedia article h-vector.

Warning

This is slightly different from the hPolynomial method in Macaulay2.

EXAMPLES:

Sage

sage: P = posets.AntichainPoset(3).order_ideals_lattice()
sage: P.h_polynomial()
q^3 + 4*q^2 + q
sage: P = posets.DiamondPoset(5)
sage: P.h_polynomial()
2*q^2 + q
sage: P = Poset({1: []})
sage: P.h_polynomial()
1

Python

>>> from sage.all import *
>>> P = posets.AntichainPoset(Integer(3)).order_ideals_lattice()
>>> P.h_polynomial()
q^3 + 4*q^2 + q
>>> P = posets.DiamondPoset(Integer(5))
>>> P.h_polynomial()
2*q^2 + q
>>> P = Poset({Integer(1): []})
>>> P.h_polynomial()
1

See also

is_bounded(), f_polynomial(), order_complex(), sage.topology.simplicial_complex.SimplicialComplex.h_vector()

has_bottom()

Return True if the poset has a unique minimal element, and False otherwise.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.has_bottom()
False
>>> Q = Poset({Integer(0):[Integer(1)], Integer(1):[]})
>>> Q.has_bottom()
True

See also

• Dual Property: has_top()

• Stronger properties: is_bounded()

• Other: bottom()

has_isomorphic_subposet(other)

Return True if the poset contains a subposet isomorphic to other.

By subposet we mean that there exist a set X of elements such that self.subposet(X) is isomorphic to other.

INPUT:

• other – a finite poset

EXAMPLES:

Sage

sage: D = Poset({1:[2,3], 2:[4], 3:[4]})
sage: T = Poset({1:[2,3], 2:[4,5], 3:[6,7]})
sage: N5 = posets.PentagonPoset()

sage: N5.has_isomorphic_subposet(T)
False
sage: N5.has_isomorphic_subposet(D)
True

sage: len([P for P in Posets(5) if P.has_isomorphic_subposet(D)])
11

Python

>>> from sage.all import *
>>> D = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> T = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4),Integer(5)], Integer(3):[Integer(6),Integer(7)]})
>>> N5 = posets.PentagonPoset()

>>> N5.has_isomorphic_subposet(T)
False
>>> N5.has_isomorphic_subposet(D)
True

>>> len([P for P in Posets(Integer(5)) if P.has_isomorphic_subposet(D)])
11

has_top()

Return True if the poset has a unique maximal element, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[3], 1:[3], 2:[3], 3:[4, 5], 4:[], 5:[]})
sage: P.has_top()
False
sage: Q = Poset({0:[3], 1:[3], 2:[3], 3:[4], 4:[]})
sage: Q.has_top()
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(3)], Integer(3):[Integer(4), Integer(5)], Integer(4):[], Integer(5):[]})
>>> P.has_top()
False
>>> Q = Poset({Integer(0):[Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> Q.has_top()
True

See also

• Dual Property: has_bottom()

• Stronger properties: is_bounded()

• Other: top()

hasse_diagram()

Return the Hasse diagram of the poset as a Sage DiGraph.

The Hasse diagram is a directed graph where vertices are the elements of the poset and there is an edge from \(u\) to \(v\) whenever \(v\) covers \(u\) in the poset.

If dot2tex is installed, then this sets the Hasse diagram’s latex options to use the dot2tex formatting.

EXAMPLES:

Sage

sage: P = posets.DivisorLattice(12)
sage: H = P.hasse_diagram(); H
Digraph on 6 vertices
sage: P.cover_relations()
[[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]]
sage: H.edges(sort=True, labels=False)
[(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]

Python

>>> from sage.all import *
>>> P = posets.DivisorLattice(Integer(12))
>>> H = P.hasse_diagram(); H
Digraph on 6 vertices
>>> P.cover_relations()
[[1, 2], [1, 3], [2, 4], [2, 6], [3, 6], [4, 12], [6, 12]]
>>> H.edges(sort=True, labels=False)
[(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]

height(certificate=False)

Return the height (number of elements in a longest chain) of the poset.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return (h, c), where h is the height and c is a chain of maximum cardinality. If certificate=False return only the height.

EXAMPLES:

Sage

sage: P = Poset({0: [1], 2: [3, 4], 4: [5, 6]})
sage: P.height()
3
sage: posets.PentagonPoset().height(certificate=True)
(4, [0, 2, 3, 4])

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1)], Integer(2): [Integer(3), Integer(4)], Integer(4): [Integer(5), Integer(6)]})
>>> P.height()
3
>>> posets.PentagonPoset().height(certificate=True)
(4, [0, 2, 3, 4])

incidence_algebra(R, prefix='I')

Return the incidence algebra of self over R.

OUTPUT: an instance of sage.combinat.posets.incidence_algebras.IncidenceAlgebra

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(4)
sage: P.incidence_algebra(QQ)
Incidence algebra of Finite lattice containing 16 elements
 over Rational Field

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(4))
>>> P.incidence_algebra(QQ)
Incidence algebra of Finite lattice containing 16 elements
 over Rational Field

incomparability_graph()

Return the incomparability graph of the poset.

This is the complement of the comparability graph, i.e. an undirected graph where vertices are the elements of the poset and there is an edge between vertices if they are not comparable in the poset.

EXAMPLES:

Sage

sage: Y = Poset({1: [2], 2: [3, 4]})
sage: g = Y.incomparability_graph(); g
Incomparability graph on 4 vertices
sage: Y.compare_elements(1, 3) is not None
True
sage: g.has_edge(1, 3)
False

Python

>>> from sage.all import *
>>> Y = Poset({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)]})
>>> g = Y.incomparability_graph(); g
Incomparability graph on 4 vertices
>>> Y.compare_elements(Integer(1), Integer(3)) is not None
True
>>> g.has_edge(Integer(1), Integer(3))
False

See also

comparability_graph()

interval(x, y)

Return a list of the elements \(z\) such that \(x \le z \le y\).

INPUT:

• x – any element of the poset

• y – any element of the poset

EXAMPLES:

Sage

sage: uc = [[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]]
sage: dag = DiGraph(dict(zip(range(len(uc)),uc)))
sage: P = Poset(dag)
sage: I = set(map(P,[2,5,6,4,7]))
sage: I == set(P.interval(2,7))
True

Python

>>> from sage.all import *
>>> uc = [[Integer(1),Integer(3),Integer(2)],[Integer(4)],[Integer(4),Integer(5),Integer(6)],[Integer(6)],[Integer(7)],[Integer(7)],[Integer(7)],[]]
>>> dag = DiGraph(dict(zip(range(len(uc)),uc)))
>>> P = Poset(dag)
>>> I = set(map(P,[Integer(2),Integer(5),Integer(6),Integer(4),Integer(7)]))
>>> I == set(P.interval(Integer(2),Integer(7)))
True

Sage

sage: dg = DiGraph({"a":["b","c"], "b":["d"], "c":["d"]})
sage: P = Poset(dg, facade = False)
sage: P.interval("a","d")
[a, b, c, d]

Python

>>> from sage.all import *
>>> dg = DiGraph({"a":["b","c"], "b":["d"], "c":["d"]})
>>> P = Poset(dg, facade = False)
>>> P.interval("a","d")
[a, b, c, d]

intervals_number()

Return the number of relations in the poset.

A relation is a pair of elements \(x\) and \(y\) such that \(x\leq y\) in the poset.

Relations are also often called intervals. The number of intervals is the dimension of the incidence algebra.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.relations_number()
13

sage: posets.TamariLattice(4).relations_number()
68

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.relations_number()
13

>>> posets.TamariLattice(Integer(4)).relations_number()
68

See also

relations_iterator(), relations()

intervals_poset()

Return the natural partial order on the set of intervals of the poset.

OUTPUT: a finite poset

The poset of intervals of a poset \(P\) has the set of intervals \([x,y]\) in \(P\) as elements, endowed with the order relation defined by \([x_1,y_1] \leq [x_2,y_2]\) if and only if \(x_1 \leq x_2\) and \(y_1 \leq y_2\).

This is also called \(P\) to the power 2, meaning the poset of poset-morphisms from the 2-chain to \(P\).

If \(P\) is a lattice, the result is also a lattice.

EXAMPLES:

Sage

sage: P = Poset({0:[1]})
sage: P.intervals_poset()
Finite poset containing 3 elements

sage: P = posets.PentagonPoset()
sage: P.intervals_poset()
Finite lattice containing 13 elements

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(1)]})
>>> P.intervals_poset()
Finite poset containing 3 elements

>>> P = posets.PentagonPoset()
>>> P.intervals_poset()
Finite lattice containing 13 elements

is_EL_labelling(f, return_raising_chains=False)

Return True if f is an EL labelling of self.

A labelling \(f\) of the edges of the Hasse diagram of a poset is called an EL labelling (edge lexicographic labelling) if for any two elements \(u\) and \(v\) with \(u \leq v\),

• there is a unique \(f\)-raising chain from \(u\) to \(v\) in the Hasse diagram, and this chain is lexicographically first among all chains from \(u\) to \(v\).

For more details, see [Bj1980].

INPUT:

• f – a function taking two elements a and b in self such that b covers a and returning elements in a totally ordered set.

• return_raising_chains (optional; default:False) if True, returns the set of all raising chains in self, if possible.

EXAMPLES:

Let us consider a Boolean poset:

Sage

sage: P = Poset([[(0,0),(0,1),(1,0),(1,1)],[[(0,0),(0,1)],[(0,0),(1,0)],[(0,1),(1,1)],[(1,0),(1,1)]]],facade=True)
sage: label = lambda a,b: min( i for i in [0,1] if a[i] != b[i] )
sage: P.is_EL_labelling(label)
True
sage: P.is_EL_labelling(label,return_raising_chains=True)
{((0, 0), (0, 1)): [1],
 ((0, 0), (1, 0)): [0],
 ((0, 0), (1, 1)): [0, 1],
 ((0, 1), (1, 1)): [0],
 ((1, 0), (1, 1)): [1]}

Python

>>> from sage.all import *
>>> P = Poset([[(Integer(0),Integer(0)),(Integer(0),Integer(1)),(Integer(1),Integer(0)),(Integer(1),Integer(1))],[[(Integer(0),Integer(0)),(Integer(0),Integer(1))],[(Integer(0),Integer(0)),(Integer(1),Integer(0))],[(Integer(0),Integer(1)),(Integer(1),Integer(1))],[(Integer(1),Integer(0)),(Integer(1),Integer(1))]]],facade=True)
>>> label = lambda a,b: min( i for i in [Integer(0),Integer(1)] if a[i] != b[i] )
>>> P.is_EL_labelling(label)
True
>>> P.is_EL_labelling(label,return_raising_chains=True)
{((0, 0), (0, 1)): [1],
 ((0, 0), (1, 0)): [0],
 ((0, 0), (1, 1)): [0, 1],
 ((0, 1), (1, 1)): [0],
 ((1, 0), (1, 1)): [1]}

is_antichain_of_poset(elms)

Return True if elms is an antichain of the poset and False otherwise.

Set of elements are an antichain of a poset if they are pairwise incomparable.

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(5)
sage: P.is_antichain_of_poset([3, 5, 7])
False
sage: P.is_antichain_of_poset([3, 5, 14])
True

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(5))
>>> P.is_antichain_of_poset([Integer(3), Integer(5), Integer(7)])
False
>>> P.is_antichain_of_poset([Integer(3), Integer(5), Integer(14)])
True

is_bounded()

Return True if the poset is bounded, and False otherwise.

A poset is bounded if it contains both a unique maximal element and a unique minimal element.

EXAMPLES:

Sage

sage: P = Poset({0:[3], 1:[3], 2:[3], 3:[4, 5], 4:[], 5:[]})
sage: P.is_bounded()
False
sage: Q = posets.DiamondPoset(5)
sage: Q.is_bounded()
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(3)], Integer(3):[Integer(4), Integer(5)], Integer(4):[], Integer(5):[]})
>>> P.is_bounded()
False
>>> Q = posets.DiamondPoset(Integer(5))
>>> Q.is_bounded()
True

See also

• Weaker properties: has_bottom(), has_top()

• Other: with_bounds(), without_bounds()

is_chain()

Return True if the poset is totally ordered (“chain”), and False otherwise.

EXAMPLES:

Sage

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

sage: II = Poset({0:[1], 2:[3]})
sage: II.is_chain()
False

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

Python

>>> from sage.all import *
>>> I = Poset({Integer(0):[Integer(1)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)]})
>>> I.is_chain()
True

>>> II = Poset({Integer(0):[Integer(1)], Integer(2):[Integer(3)]})
>>> II.is_chain()
False

>>> V = Poset({Integer(0):[Integer(1), Integer(2)]})
>>> V.is_chain()
False

is_chain_of_poset(elms, ordered=False)

Return True if elms is a chain of the poset, and False otherwise.

Set of elements are a chain of a poset if they are comparable to each other.

INPUT:

• elms – list or other iterable containing some elements of the poset

• ordered – boolean; if True, then return True only if elements in elms are strictly increasing in the poset. This makes no sense if elms is a set. If False (the default), then elements can be repeated and be in any order.

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")))
sage: sorted(P.list())
[1, 2, 3, 4, 6, 12]
sage: P.is_chain_of_poset([12, 3])
True
sage: P.is_chain_of_poset({3, 4, 12})
False
sage: P.is_chain_of_poset([12, 3], ordered=True)
False
sage: P.is_chain_of_poset((1, 1, 3))
True
sage: P.is_chain_of_poset((1, 1, 3), ordered=True)
False
sage: P.is_chain_of_poset((1, 3), ordered=True)
True

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")))
>>> sorted(P.list())
[1, 2, 3, 4, 6, 12]
>>> P.is_chain_of_poset([Integer(12), Integer(3)])
True
>>> P.is_chain_of_poset({Integer(3), Integer(4), Integer(12)})
False
>>> P.is_chain_of_poset([Integer(12), Integer(3)], ordered=True)
False
>>> P.is_chain_of_poset((Integer(1), Integer(1), Integer(3)))
True
>>> P.is_chain_of_poset((Integer(1), Integer(1), Integer(3)), ordered=True)
False
>>> P.is_chain_of_poset((Integer(1), Integer(3)), ordered=True)
True

is_connected()

Return True if the poset is connected, and False otherwise.

A poset is connected if its Hasse diagram is connected.

If a poset is not connected, then it can be divided to parts \(S_1\) and \(S_2\) so that every element of \(S_1\) is incomparable to every element of \(S_2\).

EXAMPLES:

Sage

sage: P = Poset({1:[2, 3], 3:[4, 5]})
sage: P.is_connected()
True

sage: P = Poset({1:[2, 3], 3:[4, 5], 6:[7, 8]})
sage: P.is_connected()
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(1):[Integer(2), Integer(3)], Integer(3):[Integer(4), Integer(5)]})
>>> P.is_connected()
True

>>> P = Poset({Integer(1):[Integer(2), Integer(3)], Integer(3):[Integer(4), Integer(5)], Integer(6):[Integer(7), Integer(8)]})
>>> P.is_connected()
False

See also

connected_components()

is_d_complete()

Return True if a poset is d-complete and False otherwise.

See also

• d_complete

EXAMPLES:

Sage

sage: from sage.combinat.posets.posets import FinitePoset
sage: A = Poset({0: [1,2]})
sage: A.is_d_complete()
False

sage: from sage.combinat.posets.poset_examples import Posets
sage: B = Posets.DoubleTailedDiamond(3)
sage: B.is_d_complete()
True

sage: C = Poset({0: [2], 1: [2], 2: [3, 4], 3: [5], 4: [5], 5: [6]})
sage: C.is_d_complete()
False

sage: D = Poset({0: [1, 2], 1: [4], 2: [4], 3: [4]})
sage: D.is_d_complete()
False

sage: P = Posets.YoungDiagramPoset(Partition([3, 2, 2]), dual=True)         # needs sage.combinat
sage: P.is_d_complete()                                                     # needs sage.combinat
True

Python

>>> from sage.all import *
>>> from sage.combinat.posets.posets import FinitePoset
>>> A = Poset({Integer(0): [Integer(1),Integer(2)]})
>>> A.is_d_complete()
False

>>> from sage.combinat.posets.poset_examples import Posets
>>> B = Posets.DoubleTailedDiamond(Integer(3))
>>> B.is_d_complete()
True

>>> C = Poset({Integer(0): [Integer(2)], Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)], Integer(3): [Integer(5)], Integer(4): [Integer(5)], Integer(5): [Integer(6)]})
>>> C.is_d_complete()
False

>>> D = Poset({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(4)], Integer(2): [Integer(4)], Integer(3): [Integer(4)]})
>>> D.is_d_complete()
False

>>> P = Posets.YoungDiagramPoset(Partition([Integer(3), Integer(2), Integer(2)]), dual=True)         # needs sage.combinat
>>> P.is_d_complete()                                                     # needs sage.combinat
True

is_eulerian(k=None, certificate=False)

Return True if the poset is Eulerian, and False otherwise.

The poset is expected to be graded and bounded.

A poset is Eulerian if every non-trivial interval has the same number of elements of even rank as of odd rank. A poset is \(k\)-eulerian if every non-trivial interval up to rank \(k\) is Eulerian.

See Wikipedia article Eulerian_poset.

INPUT:

• k – integer; only check if the poset is \(k\)-eulerian. If None (the default), check if the poset is Eulerian.

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either True, None or False, (a, b), where the interval (a, b) is not Eulerian. If certificate=False return True or False.

EXAMPLES:

Sage

sage: P = Poset({0: [1, 2, 3], 1: [4, 5], 2: [4, 6], 3: [5, 6],
....:            4: [7, 8], 5: [7, 8], 6: [7, 8], 7: [9], 8: [9]})
sage: P.is_eulerian()                                                       # needs sage.libs.flint
True
sage: P = Poset({0: [1, 2, 3], 1: [4, 5, 6], 2: [4, 6], 3: [5,6],
....:            4: [7], 5:[7], 6:[7]})
sage: P.is_eulerian()                                                       # needs sage.libs.flint
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5)], Integer(2): [Integer(4), Integer(6)], Integer(3): [Integer(5), Integer(6)],
...            Integer(4): [Integer(7), Integer(8)], Integer(5): [Integer(7), Integer(8)], Integer(6): [Integer(7), Integer(8)], Integer(7): [Integer(9)], Integer(8): [Integer(9)]})
>>> P.is_eulerian()                                                       # needs sage.libs.flint
True
>>> P = Poset({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5), Integer(6)], Integer(2): [Integer(4), Integer(6)], Integer(3): [Integer(5),Integer(6)],
...            Integer(4): [Integer(7)], Integer(5):[Integer(7)], Integer(6):[Integer(7)]})
>>> P.is_eulerian()                                                       # needs sage.libs.flint
False

Canonical examples of Eulerian posets are the face lattices of convex polytopes:

Sage

sage: P = polytopes.cube().face_lattice()                                   # needs sage.geometry.polyhedron
sage: P.is_eulerian()                                                       # needs sage.geometry.polyhedron sage.libs.flint
True

Python

>>> from sage.all import *
>>> P = polytopes.cube().face_lattice()                                   # needs sage.geometry.polyhedron
>>> P.is_eulerian()                                                       # needs sage.geometry.polyhedron sage.libs.flint
True

A poset that is 3- but not 4-eulerian:

Sage

sage: P = Poset(DiGraph('MWW@_?W?@_?W??@??O@_?W?@_?W?@??O??')); P
Finite poset containing 14 elements
sage: P.is_eulerian(k=3)                                                    # needs sage.libs.flint
True
sage: P.is_eulerian(k=4)                                                    # needs sage.libs.flint
False

Python

>>> from sage.all import *
>>> P = Poset(DiGraph('MWW@_?W?@_?W??@??O@_?W?@_?W?@??O??')); P
Finite poset containing 14 elements
>>> P.is_eulerian(k=Integer(3))                                                    # needs sage.libs.flint
True
>>> P.is_eulerian(k=Integer(4))                                                    # needs sage.libs.flint
False

Getting an interval that is not Eulerian:

Sage

sage: P = posets.DivisorLattice(12)
sage: P.is_eulerian(certificate=True)                                       # needs sage.libs.flint
(False, (1, 4))

Python

>>> from sage.all import *
>>> P = posets.DivisorLattice(Integer(12))
>>> P.is_eulerian(certificate=True)                                       # needs sage.libs.flint
(False, (1, 4))

is_gequal(x, y)

Return True if \(x\) is greater than or equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_gequal(3, 1)
True
sage: P.is_gequal(2, 2)
True
sage: P.is_gequal(0, 1)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_gequal(Integer(3), Integer(1))
True
>>> P.is_gequal(Integer(2), Integer(2))
True
>>> P.is_gequal(Integer(0), Integer(1))
False

See also

is_greater_than(), is_lequal().

is_graded()

Return True if the poset is graded, and False otherwise.

A poset is graded if all its maximal chains have the same length.

There are various competing definitions for graded posets (see Wikipedia article Graded_poset). This definition is from section 3.1 of Richard Stanley’s Enumerative Combinatorics, Vol. 1 [EnumComb1]. Some sources call these posets tiered.

Every graded poset is ranked. The converse is true for bounded posets, including lattices.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()  # Not even ranked
sage: P.is_graded()
False

sage: P = Poset({1:[2, 3], 3:[4]})  # Ranked, but not graded
sage: P.is_graded()
False

sage: P = Poset({1:[3, 4], 2:[3, 4], 5:[6]})
sage: P.is_graded()
True

sage: P = Poset([[1], [2], [], [4], []])
sage: P.is_graded()
False

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()  # Not even ranked
>>> P.is_graded()
False

>>> P = Poset({Integer(1):[Integer(2), Integer(3)], Integer(3):[Integer(4)]})  # Ranked, but not graded
>>> P.is_graded()
False

>>> P = Poset({Integer(1):[Integer(3), Integer(4)], Integer(2):[Integer(3), Integer(4)], Integer(5):[Integer(6)]})
>>> P.is_graded()
True

>>> P = Poset([[Integer(1)], [Integer(2)], [], [Integer(4)], []])
>>> P.is_graded()
False

See also

is_ranked(), level_sets()

is_greater_than(x, y)

Return True if \(x\) is greater than but not equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_greater_than(3, 1)
True
sage: P.is_greater_than(1, 2)
False
sage: P.is_greater_than(3, 3)
False
sage: P.is_greater_than(0, 1)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_greater_than(Integer(3), Integer(1))
True
>>> P.is_greater_than(Integer(1), Integer(2))
False
>>> P.is_greater_than(Integer(3), Integer(3))
False
>>> P.is_greater_than(Integer(0), Integer(1))
False

For non-facade posets also > works:

Sage

sage: P = Poset({3: [1, 2]}, facade=False)
sage: P(2) > P(3)
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(3): [Integer(1), Integer(2)]}, facade=False)
>>> P(Integer(2)) > P(Integer(3))
True

See also

is_gequal(), is_less_than().

is_greedy(certificate=False)

Return True if the poset is greedy, and False otherwise.

A poset is greedy if every greedy linear extension has the same number of jumps.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either (True, None) or (False, (A, B)) where \(A\) and \(B\) are greedy linear extension so that \(B\) has more jumps. If certificate=False return True or False.

EXAMPLES:

This is not a self-dual property:

Sage

sage: W = Poset({1: [3, 4], 2: [4, 5]})
sage: M = W.dual()
sage: W.is_greedy()
True
sage: M.is_greedy()
False

Python

>>> from sage.all import *
>>> W = Poset({Integer(1): [Integer(3), Integer(4)], Integer(2): [Integer(4), Integer(5)]})
>>> M = W.dual()
>>> W.is_greedy()
True
>>> M.is_greedy()
False

Getting a certificate:

Sage

sage: N = Poset({1: [3], 2: [3, 4]})
sage: N.is_greedy(certificate=True)
(False, ([1, 2, 4, 3], [2, 4, 1, 3]))

Python

>>> from sage.all import *
>>> N = Poset({Integer(1): [Integer(3)], Integer(2): [Integer(3), Integer(4)]})
>>> N.is_greedy(certificate=True)
(False, ([1, 2, 4, 3], [2, 4, 1, 3]))

is_incomparable_chain_free(m, n=None)

Return True if the poset is \((m+n)\)-free, and False otherwise.

A poset is \((m+n)\)-free if there is no incomparable chains of lengths \(m\) and \(n\). Three cases have special name (see [EnumComb1], exercise 3.15):

• ‘’interval order’’ is \((2+2)\)-free

• ‘’semiorder’’ (or ‘’unit interval order’’) is \((1+3)\)-free and \((2+2)\)-free

• ‘’weak order’’ is \((1+2)\)-free.

INPUT:

• m, n – positive integers

It is also possible to give a list of integer pairs as argument. See below for an example.

EXAMPLES:

Sage

sage: B3 = posets.BooleanLattice(3)
sage: B3.is_incomparable_chain_free(1, 3)
True
sage: B3.is_incomparable_chain_free(2, 2)
False

sage: IP6 = posets.IntegerPartitions(6)                                     # needs sage.combinat
sage: IP6.is_incomparable_chain_free(1, 3)                                  # needs sage.combinat
False
sage: IP6.is_incomparable_chain_free(2, 2)                                  # needs sage.combinat
True

Python

>>> from sage.all import *
>>> B3 = posets.BooleanLattice(Integer(3))
>>> B3.is_incomparable_chain_free(Integer(1), Integer(3))
True
>>> B3.is_incomparable_chain_free(Integer(2), Integer(2))
False

>>> IP6 = posets.IntegerPartitions(Integer(6))                                     # needs sage.combinat
>>> IP6.is_incomparable_chain_free(Integer(1), Integer(3))                                  # needs sage.combinat
False
>>> IP6.is_incomparable_chain_free(Integer(2), Integer(2))                                  # needs sage.combinat
True

A list of pairs as an argument:

Sage

sage: B3.is_incomparable_chain_free([[1, 3], [2, 2]])
False

Python

>>> from sage.all import *
>>> B3.is_incomparable_chain_free([[Integer(1), Integer(3)], [Integer(2), Integer(2)]])
False

We show how to get an incomparable chain pair:

Sage

sage: P = posets.PentagonPoset()
sage: chains_1_2 = Poset({0:[], 1:[2]})
sage: incomps = P.isomorphic_subposets(chains_1_2)[0]
sage: sorted(incomps.list()), incomps.cover_relations()
([1, 2, 3], [[2, 3]])

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> chains_1_2 = Poset({Integer(0):[], Integer(1):[Integer(2)]})
>>> incomps = P.isomorphic_subposets(chains_1_2)[Integer(0)]
>>> sorted(incomps.list()), incomps.cover_relations()
([1, 2, 3], [[2, 3]])

AUTHOR:

• Eric Rowland (2013-05-28)

is_induced_subposet(other)

Return True if the poset is an induced subposet of other, and False otherwise.

A poset \(P\) is an induced subposet of \(Q\) if every element of \(P\) is an element of \(Q\), and \(x \le_P y\) iff \(x \le_Q y\). Note that “induced” here has somewhat different meaning compared to that of graphs.

INPUT:

• other – poset

Note

This method does not check whether the poset is a isomorphic (i.e., up to relabeling) subposet of other, but only if other directly contains the poset as an induced subposet. For isomorphic subposets see has_isomorphic_subposet().

EXAMPLES:

Sage

sage: P = Poset({1:[2, 3]})
sage: Q = Poset({1:[2, 4], 2:[3]})
sage: P.is_induced_subposet(Q)
False
sage: R = Poset({0:[1], 1:[3, 4], 3:[5], 4:[2]})
sage: P.is_induced_subposet(R)
True

Python

>>> from sage.all import *
>>> P = Poset({Integer(1):[Integer(2), Integer(3)]})
>>> Q = Poset({Integer(1):[Integer(2), Integer(4)], Integer(2):[Integer(3)]})
>>> P.is_induced_subposet(Q)
False
>>> R = Poset({Integer(0):[Integer(1)], Integer(1):[Integer(3), Integer(4)], Integer(3):[Integer(5)], Integer(4):[Integer(2)]})
>>> P.is_induced_subposet(R)
True

is_isomorphic(other, **kwds)

Return True if both posets are isomorphic.

EXAMPLES:

Sage

sage: P = Poset(([1,2,3],[[1,3],[2,3]]))
sage: Q = Poset(([4,5,6],[[4,6],[5,6]]))
sage: P.is_isomorphic(Q)
True

Python

>>> from sage.all import *
>>> P = Poset(([Integer(1),Integer(2),Integer(3)],[[Integer(1),Integer(3)],[Integer(2),Integer(3)]]))
>>> Q = Poset(([Integer(4),Integer(5),Integer(6)],[[Integer(4),Integer(6)],[Integer(5),Integer(6)]]))
>>> P.is_isomorphic(Q)
True

is_join_semilattice(certificate=False)

Return True if the poset has a join operation, and False otherwise.

A join is the least upper bound for given elements, if it exists.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either (True, None) or (False, (a, b)) where elements \(a\) and \(b\) have no least upper bound. If certificate=False return True or False.

EXAMPLES:

Sage

sage: P = Poset([[1,3,2], [4], [4,5,6], [6], [7], [7], [7], []])
sage: P.is_join_semilattice()
True

sage: P = Poset({1:[3, 4], 2:[3, 4], 3:[5], 4:[5]})
sage: P.is_join_semilattice()
False
sage: P.is_join_semilattice(certificate=True)
(False, (2, 1))

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(3),Integer(2)], [Integer(4)], [Integer(4),Integer(5),Integer(6)], [Integer(6)], [Integer(7)], [Integer(7)], [Integer(7)], []])
>>> P.is_join_semilattice()
True

>>> P = Poset({Integer(1):[Integer(3), Integer(4)], Integer(2):[Integer(3), Integer(4)], Integer(3):[Integer(5)], Integer(4):[Integer(5)]})
>>> P.is_join_semilattice()
False
>>> P.is_join_semilattice(certificate=True)
(False, (2, 1))

See also

• Dual property: is_meet_semilattice()

• Stronger properties: is_lattice()

is_jump_critical(certificate=False)

Return True if the poset is jump-critical, and False otherwise.

A poset \(P\) is jump-critical if every proper subposet has smaller jump number.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either (True, None) or (False, e) so that removing element \(e\) from the poset does not decrease the jump number. If certificate=False return True or False.

EXAMPLES:

Sage

sage: P = Poset({1: [3, 6], 2: [3, 4, 5], 4: [6, 7], 5: [7]})
sage: P.is_jump_critical()
True

sage: P = posets.PentagonPoset()
sage: P.is_jump_critical()
False
sage: P.is_jump_critical(certificate=True)
(False, 3)

Python

>>> from sage.all import *
>>> P = Poset({Integer(1): [Integer(3), Integer(6)], Integer(2): [Integer(3), Integer(4), Integer(5)], Integer(4): [Integer(6), Integer(7)], Integer(5): [Integer(7)]})
>>> P.is_jump_critical()
True

>>> P = posets.PentagonPoset()
>>> P.is_jump_critical()
False
>>> P.is_jump_critical(certificate=True)
(False, 3)

See also

jump_number()

is_lequal(x, y)

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

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_lequal(2, 4)
True
sage: P.is_lequal(2, 2)
True
sage: P.is_lequal(0, 1)
False
sage: P.is_lequal(3, 2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_lequal(Integer(2), Integer(4))
True
>>> P.is_lequal(Integer(2), Integer(2))
True
>>> P.is_lequal(Integer(0), Integer(1))
False
>>> P.is_lequal(Integer(3), Integer(2))
False

See also

is_less_than(), is_gequal().

is_less_than(x, y)

Return True if \(x\) is less than but not equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_less_than(1, 3)
True
sage: P.is_less_than(0, 1)
False
sage: P.is_less_than(2, 2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_less_than(Integer(1), Integer(3))
True
>>> P.is_less_than(Integer(0), Integer(1))
False
>>> P.is_less_than(Integer(2), Integer(2))
False

For non-facade posets also < works:

Sage

sage: P = Poset({3: [1, 2]}, facade=False)
sage: P(1) < P(2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(3): [Integer(1), Integer(2)]}, facade=False)
>>> P(Integer(1)) < P(Integer(2))
False

See also

is_lequal(), is_greater_than().

is_linear_extension(l)

Return whether l is a linear extension of self.

INPUT:

• l – list (or iterable) containing all of the elements of self exactly once

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True)
sage: P.list()
[1, 2, 3, 4, 6, 12]
sage: P.is_linear_extension([1, 2, 4, 3, 6, 12])
True
sage: P.is_linear_extension([1, 2, 4, 6, 3, 12])
False

sage: [p for p in Permutations(list(P)) if P.is_linear_extension(p)]
[[1, 2, 3, 4, 6, 12],
 [1, 2, 3, 6, 4, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12]]
sage: list(P.linear_extensions())
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")), facade=True, linear_extension=True)
>>> P.list()
[1, 2, 3, 4, 6, 12]
>>> P.is_linear_extension([Integer(1), Integer(2), Integer(4), Integer(3), Integer(6), Integer(12)])
True
>>> P.is_linear_extension([Integer(1), Integer(2), Integer(4), Integer(6), Integer(3), Integer(12)])
False

>>> [p for p in Permutations(list(P)) if P.is_linear_extension(p)]
[[1, 2, 3, 4, 6, 12],
 [1, 2, 3, 6, 4, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12]]
>>> list(P.linear_extensions())
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]

Note

This is used and systematically tested in LinearExtensionsOfPosets

See also

linear_extension(), linear_extensions()

is_linear_interval(x, y)

Return whether the interval [x, y] is linear.

This means that this interval is a total order.

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.is_linear_interval(0, 4)
False
sage: P.is_linear_interval(0, 3)
True
sage: P.is_linear_interval(1, 3)
False

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.is_linear_interval(Integer(0), Integer(4))
False
>>> P.is_linear_interval(Integer(0), Integer(3))
True
>>> P.is_linear_interval(Integer(1), Integer(3))
False

is_meet_semilattice(certificate=False)

Return True if the poset has a meet operation, and False otherwise.

A meet is the greatest lower bound for given elements, if it exists.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either (True, None) or (False, (a, b)) where elements \(a\) and \(b\) have no greatest lower bound. If certificate=False return True or False.

EXAMPLES:

Sage

sage: P = Poset({1:[2, 3, 4], 2:[5, 6], 3:[6], 4:[6, 7]})
sage: P.is_meet_semilattice()
True

sage: Q = P.dual()
sage: Q.is_meet_semilattice()
False

sage: V = posets.IntegerPartitions(5)                                       # needs sage.combinat
sage: V.is_meet_semilattice(certificate=True)                               # needs sage.combinat
(False, ((2, 2, 1), (3, 1, 1)))

Python

>>> from sage.all import *
>>> P = Poset({Integer(1):[Integer(2), Integer(3), Integer(4)], Integer(2):[Integer(5), Integer(6)], Integer(3):[Integer(6)], Integer(4):[Integer(6), Integer(7)]})
>>> P.is_meet_semilattice()
True

>>> Q = P.dual()
>>> Q.is_meet_semilattice()
False

>>> V = posets.IntegerPartitions(Integer(5))                                       # needs sage.combinat
>>> V.is_meet_semilattice(certificate=True)                               # needs sage.combinat
(False, ((2, 2, 1), (3, 1, 1)))

See also

• Dual property: is_join_semilattice()

• Stronger properties: is_lattice()

is_parent_of(x)

Return True if x is an element of the poset.

is_rank_symmetric()

Return True if the poset is rank symmetric, and False otherwise.

The poset is expected to be graded and connected.

A poset of rank \(h\) (maximal chains have \(h+1\) elements) is rank symmetric if the number of elements are equal in ranks \(i\) and \(h-i\) for every \(i\) in \(0, 1, \ldots, h\).

EXAMPLES:

Sage

sage: P = Poset({1:[3, 4, 5], 2:[3, 4, 5], 3:[6], 4:[7], 5:[7]})
sage: P.is_rank_symmetric()
True
sage: P = Poset({1:[2], 2:[3, 4], 3:[5], 4:[5]})
sage: P.is_rank_symmetric()
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(1):[Integer(3), Integer(4), Integer(5)], Integer(2):[Integer(3), Integer(4), Integer(5)], Integer(3):[Integer(6)], Integer(4):[Integer(7)], Integer(5):[Integer(7)]})
>>> P.is_rank_symmetric()
True
>>> P = Poset({Integer(1):[Integer(2)], Integer(2):[Integer(3), Integer(4)], Integer(3):[Integer(5)], Integer(4):[Integer(5)]})
>>> P.is_rank_symmetric()
False

is_ranked()

Return True if the poset is ranked, and False otherwise.

A poset is ranked if there is a function \(r\) from poset elements to integers so that \(r(x)=r(y)+1\) when \(x\) covers \(y\).

Informally said a ranked poset can be “levelized”: every element is on a “level”, and every cover relation goes only one level up.

EXAMPLES:

Sage

sage: P = Poset( ([1, 2, 3, 4], [[1, 2], [2, 4], [3, 4]] ))
sage: P.is_ranked()
True

sage: P = Poset([[1, 5], [2, 6], [3], [4],[], [6, 3], [4]])
sage: P.is_ranked()
False

Python

>>> from sage.all import *
>>> P = Poset( ([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(2), Integer(4)], [Integer(3), Integer(4)]] ))
>>> P.is_ranked()
True

>>> P = Poset([[Integer(1), Integer(5)], [Integer(2), Integer(6)], [Integer(3)], [Integer(4)],[], [Integer(6), Integer(3)], [Integer(4)]])
>>> P.is_ranked()
False

See also

rank_function(), rank(), is_graded()

is_series_parallel()

Return True if the poset is series-parallel, and False otherwise.

A poset is series-parallel if it can be built up from one-element posets using the operations of disjoint union and ordinal sum. This is also called N-free property: every poset that is not series-parallel contains a subposet isomorphic to the 4-element N-shaped poset where \(a > c, d\) and \(b > d\).

Note

Some papers use the term N-free for posets having no N-shaped poset as a cover-preserving subposet. This definition is not used here.

See Wikipedia article Series-parallel partial order.

EXAMPLES:

Sage

sage: VA = Poset({1: [2, 3], 4: [5], 6: [5]})
sage: VA.is_series_parallel()
True
sage: big_N = Poset({1: [2, 4], 2: [3], 4:[7], 5:[6], 6:[7]})
sage: big_N.is_series_parallel()
False

Python

>>> from sage.all import *
>>> VA = Poset({Integer(1): [Integer(2), Integer(3)], Integer(4): [Integer(5)], Integer(6): [Integer(5)]})
>>> VA.is_series_parallel()
True
>>> big_N = Poset({Integer(1): [Integer(2), Integer(4)], Integer(2): [Integer(3)], Integer(4):[Integer(7)], Integer(5):[Integer(6)], Integer(6):[Integer(7)]})
>>> big_N.is_series_parallel()
False

is_slender(certificate=False)

Return True if the poset is slender, and False otherwise.

A finite graded poset is slender if every rank 2 interval contains three or four elements, as defined in [Stan2009]. (This notion of “slender” is unrelated to the eponymous notion defined by Graetzer and Kelly in “The Free \(\mathfrak{m}\)-Lattice on the Poset \(H\)”, Order 1 (1984), 47–65.)

This function does not check if the poset is graded or not. Instead it just returns True if the poset does not contain 5 distinct elements \(x\), \(y\), \(a\), \(b\) and \(c\) such that \(x \lessdot a,b,c \lessdot y\) where \(\lessdot\) is the covering relation.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return either (True, None) or (False, (a, b)) so that the interval \([a, b]\) has at least five elements. If certificate=False return True or False.

EXAMPLES:

Sage

sage: P = Poset(([1, 2, 3, 4], [[1, 2], [1, 3], [2, 4], [3, 4]]))
sage: P.is_slender()
True
sage: P = Poset(([1,2,3,4,5],[[1,2],[1,3],[1,4],[2,5],[3,5],[4,5]]))
sage: P.is_slender()
False

sage: # needs sage.groups
sage: W = WeylGroup(['A', 2])
sage: G = W.bruhat_poset()
sage: G.is_slender()
True
sage: W = WeylGroup(['A', 3])
sage: G = W.bruhat_poset()
sage: G.is_slender()
True

sage: P = posets.IntegerPartitions(6)                                       # needs sage.combinat
sage: P.is_slender(certificate=True)                                        # needs sage.combinat
(False, ((6,), (3, 2, 1)))

Python

>>> from sage.all import *
>>> P = Poset(([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(1), Integer(3)], [Integer(2), Integer(4)], [Integer(3), Integer(4)]]))
>>> P.is_slender()
True
>>> P = Poset(([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)],[[Integer(1),Integer(2)],[Integer(1),Integer(3)],[Integer(1),Integer(4)],[Integer(2),Integer(5)],[Integer(3),Integer(5)],[Integer(4),Integer(5)]]))
>>> P.is_slender()
False

>>> # needs sage.groups
>>> W = WeylGroup(['A', Integer(2)])
>>> G = W.bruhat_poset()
>>> G.is_slender()
True
>>> W = WeylGroup(['A', Integer(3)])
>>> G = W.bruhat_poset()
>>> G.is_slender()
True

>>> P = posets.IntegerPartitions(Integer(6))                                       # needs sage.combinat
>>> P.is_slender(certificate=True)                                        # needs sage.combinat
(False, ((6,), (3, 2, 1)))

is_sperner()

Return True if the poset is Sperner, and False otherwise.

The poset is expected to be ranked.

A poset is Sperner, if no antichain is larger than the largest rank level (one of the sets of elements of the same rank) in the poset.

See Wikipedia article Sperner_property_of_a_partially_ordered_set

See also

width(), dilworth_decomposition()

EXAMPLES:

Sage

sage: posets.SetPartitions(3).is_sperner()                                  # needs sage.combinat
True

sage: P = Poset({0: [3,4,5], 1: [5], 2: [5]})
sage: P.is_sperner()                                                        # needs networkx
False

Python

>>> from sage.all import *
>>> posets.SetPartitions(Integer(3)).is_sperner()                                  # needs sage.combinat
True

>>> P = Poset({Integer(0): [Integer(3),Integer(4),Integer(5)], Integer(1): [Integer(5)], Integer(2): [Integer(5)]})
>>> P.is_sperner()                                                        # needs networkx
False

isomorphic_subposets(other)

Return a list of subposets of self isomorphic to other.

By subposet we mean self.subposet(X) which is isomorphic to other and where X is a subset of elements of self.

INPUT:

• other – a finite poset

EXAMPLES:

Sage

sage: C2 = Poset({0:[1]})
sage: C3 = Poset({'a':['b'], 'b':['c']})
sage: L = sorted(x.cover_relations() for x in C3.isomorphic_subposets(C2))
sage: for x in L: print(x)
[['a', 'b']]
[['a', 'c']]
[['b', 'c']]

sage: D = Poset({1:[2,3], 2:[4], 3:[4]})
sage: N5 = posets.PentagonPoset()
sage: len(N5.isomorphic_subposets(D))
2

Python

>>> from sage.all import *
>>> C2 = Poset({Integer(0):[Integer(1)]})
>>> C3 = Poset({'a':['b'], 'b':['c']})
>>> L = sorted(x.cover_relations() for x in C3.isomorphic_subposets(C2))
>>> for x in L: print(x)
[['a', 'b']]
[['a', 'c']]
[['b', 'c']]

>>> D = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> N5 = posets.PentagonPoset()
>>> len(N5.isomorphic_subposets(D))
2

Note

If this function takes too much time, try using isomorphic_subposets_iterator().

isomorphic_subposets_iterator(other)

Return an iterator over the subposets of self isomorphic to other.

By subposet we mean self.subposet(X) which is isomorphic to other and where X is a subset of elements of self.

INPUT:

• other – a finite poset

EXAMPLES:

Sage

sage: D = Poset({1:[2,3], 2:[4], 3:[4]})
sage: N5 = posets.PentagonPoset()
sage: for P in N5.isomorphic_subposets_iterator(D):
....:     print(P.cover_relations())
[[0, 1], [0, 2], [1, 4], [2, 4]]
[[0, 1], [0, 3], [1, 4], [3, 4]]
[[0, 1], [0, 2], [1, 4], [2, 4]]
[[0, 1], [0, 3], [1, 4], [3, 4]]

Python

>>> from sage.all import *
>>> D = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> N5 = posets.PentagonPoset()
>>> for P in N5.isomorphic_subposets_iterator(D):
...     print(P.cover_relations())
[[0, 1], [0, 2], [1, 4], [2, 4]]
[[0, 1], [0, 3], [1, 4], [3, 4]]
[[0, 1], [0, 2], [1, 4], [2, 4]]
[[0, 1], [0, 3], [1, 4], [3, 4]]

Warning

This function will return same subposet as many times as there are automorphism on it. This is due to subgraph_search_iterator() returning labelled subgraphs. On the other hand, this function does not eat memory like isomorphic_subposets() does.

See also

sage.combinat.posets.lattices.FiniteLatticePoset.isomorphic_sublattices_iterator().

join(x, y)

Return the join of two elements x, y in the poset if the join exists; and None otherwise.

EXAMPLES:

Sage

sage: D = Poset({1:[2,3], 2:[4], 3:[4]})
sage: D.join(2, 3)
4
sage: P = Poset({'e':['b'], 'f':['b', 'c', 'd'], 'g':['c', 'd'],
....:            'b':['a'], 'c':['a']})
sage: P.join('a', 'b')
'a'
sage: P.join('e', 'a')
'a'
sage: P.join('c', 'b')
'a'
sage: P.join('e', 'f')
'b'
sage: P.join('e', 'g')
'a'
sage: P.join('c', 'd') is None
True
sage: P.join('g', 'f') is None
True

Python

>>> from sage.all import *
>>> D = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> D.join(Integer(2), Integer(3))
4
>>> P = Poset({'e':['b'], 'f':['b', 'c', 'd'], 'g':['c', 'd'],
...            'b':['a'], 'c':['a']})
>>> P.join('a', 'b')
'a'
>>> P.join('e', 'a')
'a'
>>> P.join('c', 'b')
'a'
>>> P.join('e', 'f')
'b'
>>> P.join('e', 'g')
'a'
>>> P.join('c', 'd') is None
True
>>> P.join('g', 'f') is None
True

jump_number(certificate=False)

Return the jump number of the poset.

A jump in a linear extension \([e_1, \ldots, e_n]\) of a poset \(P\) is a pair \((e_i, e_{i+1})\) so that \(e_{i+1}\) does not cover \(e_i\) in \(P\). The jump number of a poset is the minimal number of jumps in linear extensions of a poset.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• If certificate=True return a pair \((n, l)\) where \(n\) is the jump number and \(l\) is a linear extension with \(n\) jumps. If certificate=False return only the jump number.

EXAMPLES:

Sage

sage: B3 = posets.BooleanLattice(3)
sage: B3.jump_number()
3

sage: N = Poset({1: [3, 4], 2: [3]})
sage: N.jump_number(certificate=True)
(1, [1, 4, 2, 3])

Python

>>> from sage.all import *
>>> B3 = posets.BooleanLattice(Integer(3))
>>> B3.jump_number()
3

>>> N = Poset({Integer(1): [Integer(3), Integer(4)], Integer(2): [Integer(3)]})
>>> N.jump_number(certificate=True)
(1, [1, 4, 2, 3])

ALGORITHM:

It is known that every poset has a greedy linear extension – an extension \([e_1, e_2, \ldots, e_n]\) where every \(e_{i+1}\) is an upper cover of \(e_i\) if that is possible – with the smallest possible number of jumps; see [Sys1987].

Hence it suffices to test only those. We do that by backtracking.

The problem is proven to be NP-complete.

See also

is_jump_critical()

kazhdan_lusztig_polynomial(x=None, y=None, q=None, canonical_labels=None)

Return the Kazhdan-Lusztig polynomial \(P_{x,y}(q)\) of the poset.

The poset is expected to be ranked.

We follow the definition given in [EPW14]. Let \(G\) denote a graded poset with unique minimal and maximal elements and \(\chi_G\) denote the characteristic polynomial of \(G\). Let \(I_x\) and \(F^x\) denote the principal order ideal and filter of \(x\) respectively. Define the Kazhdan-Lusztig polynomial of \(G\) as the unique polynomial \(P_G(q)\) satisfying the following:

1. If \(\operatorname{rank} G = 0\), then \(P_G(q) = 1\).

2. If \(\operatorname{rank} G > 0\), then \(\deg P_G(q) < \frac{1}{2} \operatorname{rank} G\).

3. We have

   \[q^{\operatorname{rank} G} P_G(q^{-1}) = \sum_{x \in G} \chi_{I_x}(q) P_{F^x}(q).\]

We then extend this to \(P_{x,y}(q)\) by considering the subposet corresponding to the (closed) interval \([x, y]\). We also define \(P_{\emptyset}(q) = 0\) (so if \(x \not\leq y\), then \(P_{x,y}(q) = 0\)).

INPUT:

• q – (default: \(q \in \ZZ[q]\)) the indeterminate \(q\)

• x – (default: the minimal element) the element \(x\)

• y – (default: the maximal element) the element \(y\)

• canonical_labels – (optional) for subposets, use the canonical labeling (this can limit recursive calls for posets with large amounts of symmetry, but producing the labeling takes time); if not specified, this is True if x and y are both not specified and False otherwise

EXAMPLES:

Sage

sage: L = posets.BooleanLattice(3)
sage: L.kazhdan_lusztig_polynomial()
1

Python

>>> from sage.all import *
>>> L = posets.BooleanLattice(Integer(3))
>>> L.kazhdan_lusztig_polynomial()
1

Sage

sage: L = posets.SymmetricGroupWeakOrderPoset(4)
sage: L.kazhdan_lusztig_polynomial()
1
sage: x = '2314'
sage: y = '3421'
sage: L.kazhdan_lusztig_polynomial(x, y)
-q + 1
sage: L.kazhdan_lusztig_polynomial(x, y, var('t'))                          # needs sage.symbolic
-t + 1

Python

>>> from sage.all import *
>>> L = posets.SymmetricGroupWeakOrderPoset(Integer(4))
>>> L.kazhdan_lusztig_polynomial()
1
>>> x = '2314'
>>> y = '3421'
>>> L.kazhdan_lusztig_polynomial(x, y)
-q + 1
>>> L.kazhdan_lusztig_polynomial(x, y, var('t'))                          # needs sage.symbolic
-t + 1

AUTHORS:

• Travis Scrimshaw (27-12-2014)

le(x, y)

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

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_lequal(2, 4)
True
sage: P.is_lequal(2, 2)
True
sage: P.is_lequal(0, 1)
False
sage: P.is_lequal(3, 2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_lequal(Integer(2), Integer(4))
True
>>> P.is_lequal(Integer(2), Integer(2))
True
>>> P.is_lequal(Integer(0), Integer(1))
False
>>> P.is_lequal(Integer(3), Integer(2))
False

See also

is_less_than(), is_gequal().

lequal_matrix(ring=Integer Ring, sparse=False)

Compute the matrix whose (i,j) entry is 1 if self.linear_extension()[i] < self.linear_extension()[j] and 0 otherwise.

INPUT:

• ring – the ring of coefficients (default: ZZ)

• sparse – whether the returned matrix is sparse or not (default: True)

EXAMPLES:

Sage

sage: P = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade=False)
sage: LEQM = P.lequal_matrix(); LEQM
[1 1 1 1 1 1 1 1]
[0 1 0 1 0 0 0 1]
[0 0 1 1 1 0 1 1]
[0 0 0 1 0 0 0 1]
[0 0 0 0 1 0 0 1]
[0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 0 1]
sage: LEQM[1,3]
1
sage: P.linear_extension()[1] < P.linear_extension()[3]
True
sage: LEQM[2,5]
0
sage: P.linear_extension()[2] < P.linear_extension()[5]
False

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(3),Integer(2)],[Integer(4)],[Integer(4),Integer(5),Integer(6)],[Integer(6)],[Integer(7)],[Integer(7)],[Integer(7)],[]], facade=False)
>>> LEQM = P.lequal_matrix(); LEQM
[1 1 1 1 1 1 1 1]
[0 1 0 1 0 0 0 1]
[0 0 1 1 1 0 1 1]
[0 0 0 1 0 0 0 1]
[0 0 0 0 1 0 0 1]
[0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 0 1]
>>> LEQM[Integer(1),Integer(3)]
1
>>> P.linear_extension()[Integer(1)] < P.linear_extension()[Integer(3)]
True
>>> LEQM[Integer(2),Integer(5)]
0
>>> P.linear_extension()[Integer(2)] < P.linear_extension()[Integer(5)]
False

We now demonstrate the usage of the optional parameters:

Sage

sage: P.lequal_matrix(ring=QQ, sparse=False).parent()                       # needs sage.libs.flint
Full MatrixSpace of 8 by 8 dense matrices over Rational Field

Python

>>> from sage.all import *
>>> P.lequal_matrix(ring=QQ, sparse=False).parent()                       # needs sage.libs.flint
Full MatrixSpace of 8 by 8 dense matrices over Rational Field

level_sets()

Return elements grouped by maximal number of cover relations from a minimal element.

This returns a list of lists l such that l[i] is the set of minimal elements of the poset obtained by removing the elements in l[0], l[1], ..., l[i-1]. (In particular, l[0] is the set of minimal elements of self.)

Every level is an antichain of the poset.

EXAMPLES:

Sage

sage: P = Poset({0:[1,2],1:[3],2:[3],3:[]})
sage: P.level_sets()
[[0], [1, 2], [3]]

sage: Q = Poset({0:[1,2], 1:[3], 2:[4], 3:[4]})
sage: Q.level_sets()
[[0], [1, 2], [3], [4]]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(1),Integer(2)],Integer(1):[Integer(3)],Integer(2):[Integer(3)],Integer(3):[]})
>>> P.level_sets()
[[0], [1, 2], [3]]

>>> Q = Poset({Integer(0):[Integer(1),Integer(2)], Integer(1):[Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> Q.level_sets()
[[0], [1, 2], [3], [4]]

See also

dilworth_decomposition() to return elements grouped to chains.

lexicographic_sum(P)

Return the lexicographic sum using this poset as index.

In the lexicographic sum of posets \(P_t\) by index poset \(T\) we have \(x \le y\) if either \(x \le y\) in \(P_t\) for some \(t \in T\), or \(x \in P_i\), \(y \in P_j\) and \(i \le j\) in \(T\).

Informally said we substitute every element of \(T\) by corresponding poset \(P_t\).

Mathematically, it is only defined when all \(P_t\) have no common element; here we force that by giving them different names in the resulting poset.

disjoint_union() and ordinal_sum() are special cases of lexicographic sum where the index poset is an (anti)chain. ordinal_product() is a special case where every \(P_t\) is same poset.

INPUT:

• P – dictionary whose keys are elements of this poset, values are posets

EXAMPLES:

Sage

sage: N = Poset({1: [3, 4], 2: [4]})
sage: P = {1: posets.PentagonPoset(), 2: N,
....:      3: posets.ChainPoset(3), 4: posets.AntichainPoset(4)}
sage: NP = N.lexicographic_sum(P); NP
Finite poset containing 16 elements
sage: sorted(NP.minimal_elements())
[(1, 0), (2, 1), (2, 2)]

Python

>>> from sage.all import *
>>> N = Poset({Integer(1): [Integer(3), Integer(4)], Integer(2): [Integer(4)]})
>>> P = {Integer(1): posets.PentagonPoset(), Integer(2): N,
...      Integer(3): posets.ChainPoset(Integer(3)), Integer(4): posets.AntichainPoset(Integer(4))}
>>> NP = N.lexicographic_sum(P); NP
Finite poset containing 16 elements
>>> sorted(NP.minimal_elements())
[(1, 0), (2, 1), (2, 2)]

linear_extension(linear_extension=None, check=True)

Return a linear extension of this poset.

A linear extension of a finite poset \(P\) of size \(n\) is a total ordering \(\pi := \pi_0 \pi_1 \ldots \pi_{n-1}\) of its elements such that \(i<j\) whenever \(\pi_i < \pi_j\) in the poset \(P\).

INPUT:

• linear_extension – (default: None) a list of the elements of self

• check – boolean (default: True); whether to check that linear_extension is indeed a linear extension of self

EXAMPLES:

Sage

sage: P = Poset((divisors(15), attrcall("divides")), facade=True)

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(15)), attrcall("divides")), facade=True)

Without optional argument, the default linear extension of the poset is returned, as a plain list:

Sage

sage: P.linear_extension()
[1, 3, 5, 15]

Python

>>> from sage.all import *
>>> P.linear_extension()
[1, 3, 5, 15]

Otherwise, a full-featured linear extension is constructed as an element of P.linear_extensions():

Sage

sage: l = P.linear_extension([1,5,3,15]); l
[1, 5, 3, 15]
sage: type(l)
<class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category.element_class'>
sage: l.parent()
The set of all linear extensions of Finite poset containing 4 elements

Python

>>> from sage.all import *
>>> l = P.linear_extension([Integer(1),Integer(5),Integer(3),Integer(15)]); l
[1, 5, 3, 15]
>>> type(l)
<class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category.element_class'>
>>> l.parent()
The set of all linear extensions of Finite poset containing 4 elements

By default, the linear extension is checked for correctness:

Sage

sage: l = P.linear_extension([1,3,15,5])
Traceback (most recent call last):
...
ValueError: [1, 3, 15, 5] is not a linear extension of Finite poset containing 4 elements

Python

>>> from sage.all import *
>>> l = P.linear_extension([Integer(1),Integer(3),Integer(15),Integer(5)])
Traceback (most recent call last):
...
ValueError: [1, 3, 15, 5] is not a linear extension of Finite poset containing 4 elements

This can be disabled (at your own risks!) with:

Sage

sage: P.linear_extension([1,3,15,5], check=False)
[1, 3, 15, 5]

Python

>>> from sage.all import *
>>> P.linear_extension([Integer(1),Integer(3),Integer(15),Integer(5)], check=False)
[1, 3, 15, 5]

See also

is_linear_extension(), linear_extensions()

Todo

• Is it acceptable to have those two features for a single method?

• In particular, we miss a short idiom to get the default linear extension

linear_extensions(facade=False)

Return the enumerated set of all the linear extensions of this poset.

INPUT:

• facade – boolean (default: False); whether to return the linear extensions as plain lists

  Warning

  The facade option is not yet fully functional:

  Sage

  sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True)
  sage: L = P.linear_extensions(facade=True); L
  The set of all linear extensions of
   Finite poset containing 6 elements with distinguished linear extension
  sage: L([1, 2, 3, 4, 6, 12])
  Traceback (most recent call last):
  ...
  TypeError: Cannot convert list to sage.structure.element.Element
  

  Python

  >>> from sage.all import *
  >>> P = Poset((divisors(Integer(12)), attrcall("divides")), linear_extension=True)
  >>> L = P.linear_extensions(facade=True); L
  The set of all linear extensions of
   Finite poset containing 6 elements with distinguished linear extension
  >>> L([Integer(1), Integer(2), Integer(3), Integer(4), Integer(6), Integer(12)])
  Traceback (most recent call last):
  ...
  TypeError: Cannot convert list to sage.structure.element.Element
  

EXAMPLES:

Sage

sage: P = Poset((divisors(12), attrcall("divides")), linear_extension=True)
sage: P.list()
[1, 2, 3, 4, 6, 12]
sage: L = P.linear_extensions(); L
The set of all linear extensions of
 Finite poset containing 6 elements with distinguished linear extension
sage: l = L.an_element(); l
[1, 2, 3, 4, 6, 12]
sage: L.cardinality()
5
sage: L.list()
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(12)), attrcall("divides")), linear_extension=True)
>>> P.list()
[1, 2, 3, 4, 6, 12]
>>> L = P.linear_extensions(); L
The set of all linear extensions of
 Finite poset containing 6 elements with distinguished linear extension
>>> l = L.an_element(); l
[1, 2, 3, 4, 6, 12]
>>> L.cardinality()
5
>>> L.list()
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]

Each element is aware that it is a linear extension of \(P\):

Sage

sage: type(l.parent())
<class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category'>

Python

>>> from sage.all import *
>>> type(l.parent())
<class 'sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category'>

With facade=True, the elements of L are plain lists instead:

Sage

sage: L = P.linear_extensions(facade=True)
sage: l = L.an_element()
sage: type(l)
<class 'list'>

Python

>>> from sage.all import *
>>> L = P.linear_extensions(facade=True)
>>> l = L.an_element()
>>> type(l)
<class 'list'>

Warning

In Sage <= 4.8, this function used to return a plain list of lists. To recover the previous functionality, please use:

Sage

sage: L = list(P.linear_extensions(facade=True)); L
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]
sage: type(L[0])
<class 'list'>

Python

>>> from sage.all import *
>>> L = list(P.linear_extensions(facade=True)); L
[[1, 2, 3, 4, 6, 12],
 [1, 2, 4, 3, 6, 12],
 [1, 3, 2, 4, 6, 12],
 [1, 3, 2, 6, 4, 12],
 [1, 2, 3, 6, 4, 12]]
>>> type(L[Integer(0)])
<class 'list'>

See also

linear_extension(), is_linear_extension()

linear_extensions_graph()

Return the linear extensions graph of the poset.

Vertices of the graph are linear extensions of the poset. Two vertices are connected by an edge if the linear extensions differ by only one adjacent transposition.

EXAMPLES:

Sage

sage: N = Poset({1: [3, 4], 2: [4]})
sage: G = N.linear_extensions_graph(); G
Graph on 5 vertices
sage: G.neighbors(N.linear_extension([1,2,3,4]))
[[2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3]]

sage: chevron = Poset({1: [2, 6], 2: [3], 4: [3, 5], 6: [5]})
sage: G = chevron.linear_extensions_graph(); G
Graph on 22 vertices
sage: G.size()
36

Python

>>> from sage.all import *
>>> N = Poset({Integer(1): [Integer(3), Integer(4)], Integer(2): [Integer(4)]})
>>> G = N.linear_extensions_graph(); G
Graph on 5 vertices
>>> G.neighbors(N.linear_extension([Integer(1),Integer(2),Integer(3),Integer(4)]))
[[2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3]]

>>> chevron = Poset({Integer(1): [Integer(2), Integer(6)], Integer(2): [Integer(3)], Integer(4): [Integer(3), Integer(5)], Integer(6): [Integer(5)]})
>>> G = chevron.linear_extensions_graph(); G
Graph on 22 vertices
>>> G.size()
36

linear_intervals_count()

Return the enumeration of linear intervals w.r.t. their cardinality.

An interval is linear if it is a total order.

OUTPUT: list of integers

See also

is_linear_interval()

EXAMPLES:

Sage

sage: P = posets.PentagonPoset()
sage: P.linear_intervals_count()
[5, 5, 2]
sage: P = posets.TamariLattice(4)
sage: P.linear_intervals_count()
[14, 21, 12, 2]

Python

>>> from sage.all import *
>>> P = posets.PentagonPoset()
>>> P.linear_intervals_count()
[5, 5, 2]
>>> P = posets.TamariLattice(Integer(4))
>>> P.linear_intervals_count()
[14, 21, 12, 2]

list()

List the elements of the poset. This just returns the result of linear_extension().

EXAMPLES:

Sage

sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] }, facade = False)
sage: D.list()
[0, 1, 2, 3, 4]
sage: type(D.list()[0])
<class 'sage.combinat.posets.posets.FinitePoset_with_category.element_class'>

Python

>>> from sage.all import *
>>> D = Poset({ Integer(0):[Integer(1),Integer(2)], Integer(1):[Integer(3)], Integer(2):[Integer(3),Integer(4)] }, facade = False)
>>> D.list()
[0, 1, 2, 3, 4]
>>> type(D.list()[Integer(0)])
<class 'sage.combinat.posets.posets.FinitePoset_with_category.element_class'>

lower_covers(x)

Return the list of lower covers of the element x.

A lower cover of \(x\) is an element \(y\) such that \(y < x\) and there is no element \(z\) so that \(y < z < x\).

EXAMPLES:

Sage

sage: P = Poset([[1,5], [2,6], [3], [4], [], [6,3], [4]])
sage: P.lower_covers(3)
[2, 5]
sage: P.lower_covers(0)
[]

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(5)], [Integer(2),Integer(6)], [Integer(3)], [Integer(4)], [], [Integer(6),Integer(3)], [Integer(4)]])
>>> P.lower_covers(Integer(3))
[2, 5]
>>> P.lower_covers(Integer(0))
[]

See also

upper_covers()

lower_covers_iterator(x)

Return an iterator over the lower covers of the element x.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[]})
sage: l0 = P.lower_covers_iterator(3)
sage: type(l0)
<class 'generator'>
sage: next(l0)
2

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[]})
>>> l0 = P.lower_covers_iterator(Integer(3))
>>> type(l0)
<class 'generator'>
>>> next(l0)
2

lt(x, y)

Return True if \(x\) is less than but not equal to \(y\) in the poset, and False otherwise.

EXAMPLES:

Sage

sage: P = Poset({0:[2], 1:[2], 2:[3], 3:[4], 4:[]})
sage: P.is_less_than(1, 3)
True
sage: P.is_less_than(0, 1)
False
sage: P.is_less_than(2, 2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(2)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[]})
>>> P.is_less_than(Integer(1), Integer(3))
True
>>> P.is_less_than(Integer(0), Integer(1))
False
>>> P.is_less_than(Integer(2), Integer(2))
False

For non-facade posets also < works:

Sage

sage: P = Poset({3: [1, 2]}, facade=False)
sage: P(1) < P(2)
False

Python

>>> from sage.all import *
>>> P = Poset({Integer(3): [Integer(1), Integer(2)]}, facade=False)
>>> P(Integer(1)) < P(Integer(2))
False

See also

is_lequal(), is_greater_than().

magnitude()

Return the magnitude of self.

The magnitude is an integer defined as the sum of all Möbius numbers, and can be seen as some kind of Euler characteristic of the poset. It is additive under disjoint union and multiplicative under Cartesian product.

REFERENCES:

• [Lein2008] Tom Leinster, The Euler Characteristic of a Category, Documenta Mathematica, Vol. 13 (2008), 21-49 https://www.math.uni-bielefeld.de/documenta/vol-13/02.html

• https://golem.ph.utexas.edu/category/2011/06/the_magnitude_of_an_enriched_c.html

EXAMPLES:

Sage

sage: # needs sage.groups sage.libs.flint
sage: P = posets.PentagonPoset()
sage: P.magnitude()
1
sage: W = SymmetricGroup(4)
sage: P = W.noncrossing_partition_lattice().without_bounds()
sage: P.magnitude()
-4
sage: P = posets.TamariLattice(4).without_bounds()
sage: P.magnitude()
0

Python

>>> from sage.all import *
>>> # needs sage.groups sage.libs.flint
>>> P = posets.PentagonPoset()
>>> P.magnitude()
1
>>> W = SymmetricGroup(Integer(4))
>>> P = W.noncrossing_partition_lattice().without_bounds()
>>> P.magnitude()
-4
>>> P = posets.TamariLattice(Integer(4)).without_bounds()
>>> P.magnitude()
0

See also

order_complex()

maximal_antichains()

Return the maximal antichains of the poset.

An antichain \(a\) of poset \(P\) is maximal if there is no element \(e \in P \setminus a\) such that \(a \cup \{e\}\) is an antichain.

EXAMPLES:

Sage

sage: P = Poset({'a':['b', 'c'], 'b':['d','e']})
sage: [sorted(anti) for anti in P.maximal_antichains()]
[['a'], ['b', 'c'], ['c', 'd', 'e']]

sage: posets.PentagonPoset().maximal_antichains()
[[0], [1, 2], [1, 3], [4]]

Python

>>> from sage.all import *
>>> P = Poset({'a':['b', 'c'], 'b':['d','e']})
>>> [sorted(anti) for anti in P.maximal_antichains()]
[['a'], ['b', 'c'], ['c', 'd', 'e']]

>>> posets.PentagonPoset().maximal_antichains()
[[0], [1, 2], [1, 3], [4]]

See also

antichains(), maximal_chains()

maximal_chain_length()

Return the maximum length of a maximal chain in the poset.

The length here is the number of vertices.

EXAMPLES:

Sage

sage: P = posets.TamariLattice(5)
sage: P.maximal_chain_length()
11

Python

>>> from sage.all import *
>>> P = posets.TamariLattice(Integer(5))
>>> P.maximal_chain_length()
11

See also

maximal_chains(), maximal_chains_iterator()

maximal_chains(partial=None)

Return all maximal chains of this poset.

Each chain is listed in increasing order.

INPUT:

• partial – list (optional); if given, the list partial is assumed to be the start of a maximal chain, and the function will find all maximal chains starting with the elements in partial

This is used in constructing the order complex for the poset.

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(3)
sage: P.maximal_chains()
[[0, 1, 3, 7], [0, 1, 5, 7], [0, 2, 3, 7],
 [0, 2, 6, 7], [0, 4, 5, 7], [0, 4, 6, 7]]
sage: P.maximal_chains(partial=[0,2])
[[0, 2, 3, 7], [0, 2, 6, 7]]
sage: Q = posets.ChainPoset(6)
sage: Q.maximal_chains()
[[0, 1, 2, 3, 4, 5]]

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(3))
>>> P.maximal_chains()
[[0, 1, 3, 7], [0, 1, 5, 7], [0, 2, 3, 7],
 [0, 2, 6, 7], [0, 4, 5, 7], [0, 4, 6, 7]]
>>> P.maximal_chains(partial=[Integer(0),Integer(2)])
[[0, 2, 3, 7], [0, 2, 6, 7]]
>>> Q = posets.ChainPoset(Integer(6))
>>> Q.maximal_chains()
[[0, 1, 2, 3, 4, 5]]

See also

maximal_antichains(), chains()

maximal_chains_iterator(partial=None)

Return an iterator over maximal chains.

Each chain is listed in increasing order.

INPUT:

• partial – list (optional); if given, the list partial is assumed to be the start of a maximal chain, and the function will yield all maximal chains starting with the elements in partial

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(3)
sage: it = P.maximal_chains_iterator()
sage: next(it)
[0, 1, 3, 7]

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(3))
>>> it = P.maximal_chains_iterator()
>>> next(it)
[0, 1, 3, 7]

See also

antichains_iterator()

maximal_elements()

Return the list of the maximal elements of the poset.

EXAMPLES:

Sage

sage: P = Poset({0:[3],1:[3],2:[3],3:[4],4:[]})
sage: P.maximal_elements()
[4]

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)],Integer(1):[Integer(3)],Integer(2):[Integer(3)],Integer(3):[Integer(4)],Integer(4):[]})
>>> P.maximal_elements()
[4]

See also

minimal_elements().

meet(x, y)

Return the meet of two elements x, y in the poset if the meet exists; and None otherwise.

EXAMPLES:

Sage

sage: D = Poset({1:[2,3], 2:[4], 3:[4]})
sage: D.meet(2, 3)
1
sage: P = Poset({'a':['b', 'c'], 'b':['e', 'f'], 'c':['f', 'g'],
....:            'd':['f', 'g']})
sage: P.meet('a', 'b')
'a'
sage: P.meet('e', 'a')
'a'
sage: P.meet('c', 'b')
'a'
sage: P.meet('e', 'f')
'b'
sage: P.meet('e', 'g')
'a'
sage: P.meet('c', 'd') is None
True
sage: P.meet('g', 'f') is None
True

Python

>>> from sage.all import *
>>> D = Poset({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(4)], Integer(3):[Integer(4)]})
>>> D.meet(Integer(2), Integer(3))
1
>>> P = Poset({'a':['b', 'c'], 'b':['e', 'f'], 'c':['f', 'g'],
...            'd':['f', 'g']})
>>> P.meet('a', 'b')
'a'
>>> P.meet('e', 'a')
'a'
>>> P.meet('c', 'b')
'a'
>>> P.meet('e', 'f')
'b'
>>> P.meet('e', 'g')
'a'
>>> P.meet('c', 'd') is None
True
>>> P.meet('g', 'f') is None
True

minimal_elements()

Return the list of the minimal elements of the poset.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = Poset({Integer(0):[Integer(3)],Integer(1):[Integer(3)],Integer(2):[Integer(3)],Integer(3):[Integer(4)],Integer(4):[]})
>>> P(Integer(0)) in P.minimal_elements()
True
>>> P(Integer(1)) in P.minimal_elements()
True
>>> P(Integer(2)) in P.minimal_elements()
True

See also

maximal_elements().

moebius_function(x, y)

Return the value of the Möbius function of the poset on the elements x and y.

EXAMPLES:

Sage

sage: P = Poset([[1,2,3],[4],[4],[4],[]])
sage: P.moebius_function(P(0),P(4))
2
sage: sum(P.moebius_function(P(0),v) for v in P)
0
sage: sum(abs(P.moebius_function(P(0),v))
....:     for v in P)
6
sage: for u,v in P.cover_relations_iterator():
....:     if P.moebius_function(u,v) != -1:
....:         print("Bug in moebius_function!")

Python

>>> from sage.all import *
>>> P = Poset([[Integer(1),Integer(2),Integer(3)],[Integer(4)],[Integer(4)],[Integer(4)],[]])
>>> P.moebius_function(P(Integer(0)),P(Integer(4)))
2
>>> sum(P.moebius_function(P(Integer(0)),v) for v in P)
0
>>> sum(abs(P.moebius_function(P(Integer(0)),v))
...     for v in P)
6
>>> for u,v in P.cover_relations_iterator():
...     if P.moebius_function(u,v) != -Integer(1):
...         print("Bug in moebius_function!")

Sage

sage: Q = Poset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]])
sage: Q.moebius_function(Q(0),Q(7))
0
sage: Q.moebius_function(Q(0),Q(5))
0
sage: Q.moebius_function(Q(2),Q(7))
2
sage: Q.moebius_function(Q(3),Q(3))
1
sage: sum([Q.moebius_function(Q(0),v) for v in Q])
0

Python

>>> from sage.all import *
>>> Q = Poset([[Integer(1),Integer(3),Integer(2)],[Integer(4)],[Integer(4),Integer(5),Integer(6)],[Integer(6)],[Integer(7)],[Integer(7)],[Integer(7)],[]])
>>> Q.moebius_function(Q(Integer(0)),Q(Integer(7)))
0
>>> Q.moebius_function(Q(Integer(0)),Q(Integer(5)))
0
>>> Q.moebius_function(Q(Integer(2)),Q(Integer(7)))
2
>>> Q.moebius_function(Q(Integer(3)),Q(Integer(3)))
1
>>> sum([Q.moebius_function(Q(Integer(0)),v) for v in Q])
0

moebius_function_matrix(ring=Integer Ring, sparse=False)

Return a matrix whose (i,j) entry is the value of the Möbius function evaluated at self.linear_extension()[i] and self.linear_extension()[j].

INPUT:

• ring – the ring of coefficients (default: ZZ)

• sparse – whether the returned matrix is sparse or not (default: True)

EXAMPLES:

Sage

sage: P = Poset([[4,2,3],[],[1],[1],[1]])
sage: x,y = (P.linear_extension()[0],P.linear_extension()[1])
sage: P.moebius_function(x,y)
-1
sage: M = P.moebius_function_matrix(); M                                    # needs sage.libs.flint
[ 1 -1 -1 -1  2]
[ 0  1  0  0 -1]
[ 0  0  1  0 -1]
[ 0  0  0  1 -1]
[ 0  0  0  0  1]
sage: M[0,4]                                                                # needs sage.libs.flint
2
sage: M[0,1]                                                                # needs sage.libs.flint
-1

Python

>>> from sage.all import *
>>> P = Poset([[Integer(4),Integer(2),Integer(3)],[],[Integer(1)],[Integer(1)],[Integer(1)]])
>>> x,y = (P.linear_extension()[Integer(0)],P.linear_extension()[Integer(1)])
>>> P.moebius_function(x,y)
-1
>>> M = P.moebius_function_matrix(); M                                    # needs sage.libs.flint
[ 1 -1 -1 -1  2]
[ 0  1  0  0 -1]
[ 0  0  1  0 -1]
[ 0  0  0  1 -1]
[ 0  0  0  0  1]
>>> M[Integer(0),Integer(4)]                                                                # needs sage.libs.flint
2
>>> M[Integer(0),Integer(1)]                                                                # needs sage.libs.flint
-1

We now demonstrate the usage of the optional parameters:

Sage

sage: P.moebius_function_matrix(ring=QQ, sparse=False).parent()             # needs sage.libs.flint
Full MatrixSpace of 5 by 5 dense matrices over Rational Field

Python

>>> from sage.all import *
>>> P.moebius_function_matrix(ring=QQ, sparse=False).parent()             # needs sage.libs.flint
Full MatrixSpace of 5 by 5 dense matrices over Rational Field

open_interval(x, y)

Return the list of elements \(z\) such that \(x < z < y\) in the poset.

EXAMPLES:

Sage

sage: P = Poset((divisors(1000), attrcall("divides")))
sage: P.open_interval(2, 100)
[4, 10, 20, 50]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(1000)), attrcall("divides")))
>>> P.open_interval(Integer(2), Integer(100))
[4, 10, 20, 50]

See also

closed_interval()

order_complex(on_ints=False)

Return the order complex associated to this poset.

The order complex is the simplicial complex with vertices equal to the elements of the poset, and faces given by the chains.

INPUT:

• on_ints – boolean (default: False)

OUTPUT: an order complex of type SimplicialComplex

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(3)
sage: S = P.order_complex(); S
Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6, 7) and 6 facets
sage: S.f_vector()
[1, 8, 19, 18, 6]
sage: S.homology()      # S is contractible
{0: 0, 1: 0, 2: 0, 3: 0}
sage: Q = P.subposet([1,2,3,4,5,6])
sage: Q.order_complex().homology()    # a circle
{0: 0, 1: Z}

sage: P = Poset((divisors(15), attrcall("divides")), facade=True)
sage: P.order_complex()
Simplicial complex with vertex set (1, 3, 5, 15) and
 facets {(1, 3, 15), (1, 5, 15)}

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(3))
>>> S = P.order_complex(); S
Simplicial complex with vertex set (0, 1, 2, 3, 4, 5, 6, 7) and 6 facets
>>> S.f_vector()
[1, 8, 19, 18, 6]
>>> S.homology()      # S is contractible
{0: 0, 1: 0, 2: 0, 3: 0}
>>> Q = P.subposet([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6)])
>>> Q.order_complex().homology()    # a circle
{0: 0, 1: Z}

>>> P = Poset((divisors(Integer(15)), attrcall("divides")), facade=True)
>>> P.order_complex()
Simplicial complex with vertex set (1, 3, 5, 15) and
 facets {(1, 3, 15), (1, 5, 15)}

If on_ints, then the elements of the poset are labelled \(0,1,\dots\) in the chain complex:

Sage

sage: P.order_complex(on_ints=True)
Simplicial complex with vertex set (0, 1, 2, 3) and
 facets {(0, 1, 3), (0, 2, 3)}

Python

>>> from sage.all import *
>>> P.order_complex(on_ints=True)
Simplicial complex with vertex set (0, 1, 2, 3) and
 facets {(0, 1, 3), (0, 2, 3)}

order_filter(elements)

Return the order filter generated by the elements of an iterable elements.

\(I\) is an order filter if, for any \(x\) in \(I\) and \(y\) such that \(y \ge x\), then \(y\) is in \(I\). This is also called upper set or upset.

EXAMPLES:

Sage

sage: P = Poset((divisors(1000), attrcall("divides")))
sage: P.order_filter([20, 25])
[20, 40, 25, 50, 100, 200, 125, 250, 500, 1000]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(1000)), attrcall("divides")))
>>> P.order_filter([Integer(20), Integer(25)])
[20, 40, 25, 50, 100, 200, 125, 250, 500, 1000]

See also

order_ideal(), principal_order_filter().

order_ideal(elements)

Return the order ideal generated by the elements of an iterable elements.

\(I\) is an order ideal if, for any \(x\) in \(I\) and \(y\) such that \(y \le x\), then \(y\) is in \(I\). This is also called lower set or downset.

EXAMPLES:

Sage

sage: P = Poset((divisors(1000), attrcall("divides")))
sage: P.order_ideal([20, 25])
[1, 2, 4, 5, 10, 20, 25]

Python

>>> from sage.all import *
>>> P = Poset((divisors(Integer(1000)), attrcall("divides")))
>>> P.order_ideal([Integer(20), Integer(25)])
[1, 2, 4, 5, 10, 20, 25]

See also

order_filter(), principal_order_ideal().

order_ideal_cardinality(elements)

Return the cardinality of the order ideal generated by elements.

The elements \(I\) is an order ideal if, for any \(x \in I\) and \(y\) such that \(y \le x\), then \(y \in I\).

EXAMPLES:

Sage

sage: P = posets.BooleanLattice(4)
sage: P.order_ideal_cardinality([7,10])
10

Python

>>> from sage.all import *
>>> P = posets.BooleanLattice(Integer(4))
>>> P.order_ideal_cardinality([Integer(7),Integer(10)])
10

order_ideal_plot(elements)

Return a plot of the order ideal generated by the elements of an iterable elements.

\(I\) is an order ideal if, for any \(x\) in \(I\) and \(y\) such that \(y \le x\), then \(y\) is in \(I\). This is also called lower set or downset.

EXAMPLES:

Sage

sage: # needs sage.plot
sage: P = Poset((divisors(1000), attrcall("divides")))
sage: P.order_ideal_plot([20, 25])
Graphics object consisting of 41 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.plot
>>> P = Poset((divisors(Integer(1000)), attrcall("divides")))
>>> P.order_ideal_plot([Integer(20), Integer(25)])
Graphics object consisting of 41 graphics primitives

order_polynomial()

Return the order polynomial of the poset.

The order polynomial \(\Omega_P(q)\) of a poset \(P\) is defined as the unique polynomial \(S\) such that for each integer \(m \geq 1\), \(S(m)\) is the number of order-preserving maps from \(P\) to \(\{1,\ldots,m\}\).

See sections 3.12 and 3.15 of [EnumComb1], and also [St1986].

EXAMPLES:

Sage

sage: P = posets.AntichainPoset(3)
sage: P.order_polynomial()
q^3

sage: P = posets.ChainPoset(3)
sage: f = P.order_polynomial(); f
1/6*q^3 + 1/2*q^2 + 1/3*q
sage: [f(i) for i in range(4)]
[0, 1, 4, 10]

Python

>>> from sage.all import *
>>> P = posets.AntichainPoset(Integer(3))
>>> P.order_polynomial()
q^3

>>> P = posets.ChainPoset(Integer(3))
>>> f = P.order_polynomial(); f
1/6*q^3 + 1/2*q^2 + 1/3*q
>>> [f(i) for i in range(Integer(4))]
[0, 1, 4, 10]

See also

order_polytope()

order_polytope()

Return the order polytope of the poset self.

The order polytope of a finite poset \(P\) is defined as the subset of \(\RR^P\) consisting of all maps \(x : P \to \RR\) satisfying

\[0 \leq x(p) \leq 1 \mbox{ for all } p \in P,\]

and

\[x(p) \leq x(q) \mbox{ for all } p, q \in P \mbox{ satisfying } p < q.\]

This polytope was defined and studied in [St1986].

EXAMPLES:

Sage

sage: P = posets.AntichainPoset(3)
sage: Q = P.order_polytope(); Q                                             # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: P = posets.PentagonPoset()
sage: Q = P.order_polytope(); Q                                             # needs sage.geometry.polyhedron
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices

sage: P = Poset([[1,2,3],[[1,2],[1,3]]])
sage: Q = P.order_polytope()                                                # needs sage.geometry.polyhedron
sage: Q.contains((1,0,0))                                                   # needs sage.geometry.polyhedron
False
sage: Q.contains((0,1,1))                                                   # needs sage.geometry.polyhedron
True

Python

>>> from sage.all import *
>>> P = posets.AntichainPoset(Integer(3))
>>> Q = P.order_polytope(); Q                                             # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
>>> P = posets.PentagonPoset()
>>> Q = P.order_polytope(); Q                                             # needs sage.geometry.polyhedron
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 8 vertices

>>> P = Poset([[Integer(1),Integer(2),Integer(3)],[[Integer(1),Integer(2)],[Integer(1),Integer(3)]]])
>>> Q = P.order_polytope()                                                # needs sage.geometry.polyhedron
>>> Q.contains((Integer(1),Integer(0),Integer(0)))                                                   # needs sage.geometry.polyhedron
False
>>> Q.contains((Integer(0),Integer(1),Integer(1)))                                                   # needs sage.geometry.polyhedron
True

ordinal_product(other, labels='pairs')

Return the ordinal product of self and other.

The ordinal product of two posets \(P\) and \(Q\) is a partial order on the Cartesian product of the underlying sets of \(P\) and \(Q\), defined as follows (see [EnumComb1], p. 284).

In the ordinal product, \((p,q) \leq (p',q')\) if either \(p \leq p'\) or \(p = p'\) and \(q \leq q'\).

This construction is not symmetric in \(P\) and \(Q\). Informally said we put a copy of \(Q\) in place of every element of \(P\).

INPUT:

• other – a poset

• labels – either 'integers' or 'pairs' (default); how the resulting poset will be labeled

EXAMPLES:

Sage

sage: P1 = Poset((['a', 'b'], [['a', 'b']]))
sage: P2 = Poset((['c', 'd'], [['c', 'd']]))
sage: P = P1.ordinal_product(P2); P
Finite poset containing 4 elements
sage: sorted(P.cover_relations())
[[('a', 'c'), ('a', 'd')], [('a', 'd'), ('b', 'c')],
[('b', 'c'), ('b', 'd')]]

Python

>>> from sage.all import *
>>> P1 = Poset((['a', 'b'], [['a', 'b']]))
>>> P2 = Poset((['c', 'd'], [['c', 'd']]))
>>> P = P1.ordinal_product(P2); P
Finite poset containing 4 elements
>>> sorted(P.cover_relations())
[[('a', 'c'), ('a', 'd')], [('a', 'd'), ('b', 'c')],
[('b', 'c'), ('b', 'd')]]

See also

product(), ordinal_sum()

ordinal_sum(other, labels='pairs')

Return a poset or (semi)lattice isomorphic to ordinal sum of the poset with other.

The ordinal sum of \(P\) and \(Q\) is a poset that contains every element and relation from both \(P\) and \(Q\), and where every element of \(P\) is smaller than any element of \(Q\).

Mathematically, it is only defined when \(P\) and \(Q\) have no common element; here we force that by giving them different names in the resulting poset.

The ordinal sum on lattices is a lattice; resp. for meet- and join-semilattices.

INPUT:

• other – poset

• labels – (defaults to ‘pairs’) If set to ‘pairs’, each element v in this poset will be named (0,v) and each element u in other will be named (1,u) in the result. If set to ‘integers’, the elements of the result will be relabeled with consecutive integers.

EXAMPLES:

Sage

sage: P1 = Poset( ([1, 2, 3, 4], [[1, 2], [1, 3], [1, 4]]) )
sage: P2 = Poset( ([1, 2, 3,], [[2,1], [3,1]]) )
sage: P3 = P1.ordinal_sum(P2); P3
Finite poset containing 7 elements
sage: len(P1.maximal_elements())*len(P2.minimal_elements())
6
sage: len(P1.cover_relations()+P2.cover_relations())
5
sage: len(P3.cover_relations()) # Every element of P2 is greater than elements of P1.