next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Posets :: Posets

Posets -- a package for working with partially ordered sets

Description

This package defines Poset as a new data type and provides routines which use or produce posets. A poset (partially ordered set) is a set together with a binary relation satisfying reflexivity, antisymmetry, and transitivity.

Contributors:

The following people have generously contributed code to the package: Kristine Fisher, Andrew Hoefel, Manoj Kummini, Stephen Sturgeon, and Josephine Yu.

Other acknowledgements:

A few methods in this package have been ported from John Stembridge's Maple package implementing posets, which is available at http://www.math.lsa.umich.edu/~jrs/maple.html#posets. Such methods are noted both in the source code and in the documentation.

See also

Authors

Certification a gold star

Version 1.1.2 of this package was accepted for publication in volume 7 of The Journal of Software for Algebra and Geometry on 5 June 2015, in the article Partially ordered sets in Macaulay2. That version can be obtained from the journal or from the Macaulay2 source code repository.

Version

This documentation describes version 1.1.2 of Posets.

Source code

The source code from which this documentation is derived is in the file Posets.m2.

Exports

  • Types
    • "NCPartition" -- see ncPartitions -- generates the non-crossing partitions of size $n$
    • Poset -- a class for partially ordered sets (posets)
  • Functions and commands
    • adjoinMax -- computes the poset with a new maximum element
    • adjoinMin -- computes the poset with a new minimum element
    • allRelations -- computes all relations of a poset
    • antichains -- computes all antichains of a poset
    • areIsomorphic -- determines if two posets are isomorphic
    • atoms -- computes the list of elements covering the minimal elements of a poset
    • augmentPoset -- computes the poset with an adjoined minimum and maximum
    • booleanLattice -- generates the boolean lattice on $n$ elements
    • boundedRegions -- computes the number of bounded regions a hyperplane arrangement divides the space into
    • chain -- generates the chain poset on $n$ elements
    • chains -- computes all chains of a poset
    • characteristicPolynomial -- computes the characteristic polynomial of a ranked poset with a unique minimal element
    • closedInterval -- computes the subposet contained between two points
    • comparabilityGraph -- produces the comparability graph of a poset
    • compare -- compares two elements in a poset
    • coveringRelations -- computes the minimal list of generating relations of a poset
    • coxeterPolynomial -- computes the Coxeter polynomial of a poset
    • diamondProduct -- computes the diamond product of two ranked posets
    • dilworthLattice -- computes the Dilworth lattice of a poset
    • dilworthNumber -- computes the Dilworth number of a poset
    • displayPoset -- generates a PDF representation of a poset and attempts to display it
    • distributiveLattice -- computes the lattice of order ideals of a poset
    • divisorPoset -- generates the poset of divisors
    • dominanceLattice -- generates the dominance lattice of partitions of $n$
    • dropElements -- computes the induced subposet of a poset given a list of elements to remove
    • facePoset -- generates the face poset of a simplicial complex
    • filter -- computes the elements above given elements in a poset
    • filtration -- generates the filtration of a poset
    • flagChains -- computes the maximal chains in a list of flags of a ranked poset
    • flagfPolynomial -- computes the flag-f polynomial of a ranked poset
    • flaghPolynomial -- computes the flag-h polynomial of a ranked poset
    • flagPoset -- computes the subposet of specified ranks of a ranked poset
    • fPolynomial -- computes the f-polynomial of a poset
    • gapConvertPoset -- converts between Macaulay2's Posets and GAP's Posets
    • greeneKleitmanPartition -- computes the Greene-Kleitman partition of a poset
    • hasseDiagram -- produces the Hasse diagram of a poset
    • hibiIdeal -- produces the Hibi ideal of a poset
    • hibiRing -- produces the Hibi ring of a poset
    • hPolynomial -- computes the h-polynomial of a poset
    • incomparabilityGraph -- produces the incomparability graph of a poset
    • indexLabeling -- relabels a poset with the labeling based on the indices of the vertices
    • intersectionLattice -- generates the intersection lattice of a hyperplane arrangement
    • isAntichain -- determines if a given list of vertices is an antichain of a poset
    • isAtomic -- determines if a lattice is atomic
    • isBounded -- determines if a poset is bounded
    • isComparabilityGraph -- determines if a graph is the comparability graph of a poset
    • isDistributive -- determines if a lattice is distributive
    • isGeometric -- determines if a lattice is geometric
    • isGraded -- determines if a poset is graded
    • isLattice -- determines if a poset is a lattice
    • isLowerSemilattice -- determines if a poset is a lower (or meet) semilattice
    • isLowerSemimodular -- determines if a ranked lattice is lower semimodular
    • isModular -- determines if a lattice is modular
    • isomorphism -- computes an isomorphism between isomorphic posets
    • isRanked -- determines if a poset is ranked
    • isSperner -- determines if a ranked poset has the Sperner property
    • isStrictSperner -- determines if a ranked poset has the strict Sperner property
    • isUpperSemilattice -- determines if a poset is an upper (or join) semilattice
    • isUpperSemimodular -- determines if a lattice is upper semimodular
    • joinExists -- determines if the join exists for two elements of a poset
    • joinIrreducibles -- determines the join irreducible elements of a poset
    • labelPoset -- relabels a poset with the specified labeling
    • lcmLattice -- generates the lattice of lcms in an ideal
    • linearExtensions -- computes all linear extensions of a poset
    • maximalAntichains -- computes all maximal antichains of a poset
    • maximalChains -- computes all maximal chains of a poset
    • maximalElements -- determines the maximal elements of a poset
    • meetExists -- determines if the meet exists for two elements of a poset
    • meetIrreducibles -- determines the meet irreducible elements of a poset
    • minimalElements -- determines the minimal elements of a poset
    • moebiusFunction -- computes the Moebius function at every pair of elements of a poset
    • naturalLabeling -- relabels a poset with a natural labeling
    • ncPartitions -- generates the non-crossing partitions of size $n$
    • ncpLattice -- computes the non-crossing partition lattice of set-partitions of size $n$
    • openInterval -- computes the subposet contained strictly between two points
    • orderComplex -- produces the order complex of a poset
    • orderIdeal -- computes the elements below given elements in a poset
    • outputTexPoset -- writes a LaTeX file with a TikZ-representation of a poset
    • partitionLattice -- computes the lattice of set-partitions of size $n$
    • plueckerPoset -- computes a poset associated to the Pluecker relations
    • poincarePolynomial -- computes the Poincare polynomial of a ranked poset with a unique minimal element
    • poset -- creates a new Poset object
    • posetJoin -- determines the join for two elements of a poset
    • posetMeet -- determines the meet for two elements of a poset
    • pPartitionRing -- produces the p-partition ring of a poset
    • principalFilter -- computes the elements above a given element in a poset
    • principalOrderIdeal -- computes the elements below a given element in a poset
    • projectivizeArrangement -- computes the intersection poset of a projectivized hyperplane arrangement
    • randomPoset -- generates a random poset with a given relation probability
    • rankFunction -- computes the rank function of a ranked poset
    • rankGeneratingFunction -- computes the rank generating function of a ranked poset
    • rankPoset -- generates a list of lists representing the ranks of a ranked poset
    • realRegions -- computes the number of regions a hyperplane arrangement divides the space into
    • removeIsomorphicPosets -- returns a sub-list of non-isomorphic posets
    • resolutionPoset -- generates a poset from a resolution
    • setPartition -- computes the list of set-partitions of size $n$
    • setPDFViewer -- sets the default PDFViewer option
    • setPrecompute -- sets the Precompute configuration
    • setSuppressLabels -- sets the SuppressLabels configuration
    • standardMonomialPoset -- generates the poset of divisibility in the monomial basis of an ideal
    • subposet -- computes the induced subposet of a poset given a list of elements
    • texPoset -- generates a string containing a TikZ-figure of a poset
    • transitiveClosure -- computes the transitive closure of a set of relations
    • transitiveOrientation -- generates a poset whose comparability graph is the given graph
    • tuttePolynomial -- computes the Tutte polynomial of a poset
    • union -- computes the union of two posets
    • youngSubposet -- generates a subposet of Young's lattice
    • zetaPolynomial -- computes the zeta polynomial of a poset
  • Methods
    • "adjoinMax(Poset)" -- see adjoinMax -- computes the poset with a new maximum element
    • "adjoinMax(Poset,Thing)" -- see adjoinMax -- computes the poset with a new maximum element
    • "adjoinMin(Poset)" -- see adjoinMin -- computes the poset with a new minimum element
    • "adjoinMin(Poset,Thing)" -- see adjoinMin -- computes the poset with a new minimum element
    • "allRelations(Poset)" -- see allRelations -- computes all relations of a poset
    • "allRelations(Poset,Boolean)" -- see allRelations -- computes all relations of a poset
    • "antichains(Poset)" -- see antichains -- computes all antichains of a poset
    • "antichains(Poset,ZZ)" -- see antichains -- computes all antichains of a poset
    • "areIsomorphic(Poset,Poset)" -- see areIsomorphic -- determines if two posets are isomorphic
    • "Poset == Poset" -- see areIsomorphic -- determines if two posets are isomorphic
    • "atoms(Poset)" -- see atoms -- computes the list of elements covering the minimal elements of a poset
    • "augmentPoset(Poset)" -- see augmentPoset -- computes the poset with an adjoined minimum and maximum
    • "augmentPoset(Poset,Thing,Thing)" -- see augmentPoset -- computes the poset with an adjoined minimum and maximum
    • "booleanLattice(ZZ)" -- see booleanLattice -- generates the boolean lattice on $n$ elements
    • "boundedRegions(List,Ring)" -- see boundedRegions -- computes the number of bounded regions a hyperplane arrangement divides the space into
    • "chain(ZZ)" -- see chain -- generates the chain poset on $n$ elements
    • "chains(Poset)" -- see chains -- computes all chains of a poset
    • "chains(Poset,ZZ)" -- see chains -- computes all chains of a poset
    • "characteristicPolynomial(Poset)" -- see characteristicPolynomial -- computes the characteristic polynomial of a ranked poset with a unique minimal element
    • "closedInterval(Poset,Thing,Thing)" -- see closedInterval -- computes the subposet contained between two points
    • "comparabilityGraph(Poset)" -- see comparabilityGraph -- produces the comparability graph of a poset
    • "compare(Poset,Thing,Thing)" -- see compare -- compares two elements in a poset
    • connectedComponents(Poset) -- generates a list of connected components of a poset
    • "coveringRelations(Poset)" -- see coveringRelations -- computes the minimal list of generating relations of a poset
    • "coxeterPolynomial(Poset)" -- see coxeterPolynomial -- computes the Coxeter polynomial of a poset
    • "diamondProduct(Poset,Poset)" -- see diamondProduct -- computes the diamond product of two ranked posets
    • "dilworthLattice(Poset)" -- see dilworthLattice -- computes the Dilworth lattice of a poset
    • "dilworthNumber(Poset)" -- see dilworthNumber -- computes the Dilworth number of a poset
    • "displayPoset(Poset)" -- see displayPoset -- generates a PDF representation of a poset and attempts to display it
    • "distributiveLattice(Poset)" -- see distributiveLattice -- computes the lattice of order ideals of a poset
    • "divisorPoset(ZZ)" -- see divisorPoset -- generates the poset of divisors
    • divisorPoset(List,List,PolynomialRing) -- generates the poset of divisors
    • divisorPoset(RingElement) -- generates the poset of divisors
    • divisorPoset(RingElement,RingElement) -- generates the poset of divisors with a lower and upper bound
    • "dominanceLattice(ZZ)" -- see dominanceLattice -- generates the dominance lattice of partitions of $n$
    • "dropElements(Poset,Function)" -- see dropElements -- computes the induced subposet of a poset given a list of elements to remove
    • "dropElements(Poset,List)" -- see dropElements -- computes the induced subposet of a poset given a list of elements to remove
    • "Poset - List" -- see dropElements -- computes the induced subposet of a poset given a list of elements to remove
    • dual(Poset) -- produces the derived poset with relations reversed
    • "facePoset(SimplicialComplex)" -- see facePoset -- generates the face poset of a simplicial complex
    • "filter(Poset,List)" -- see filter -- computes the elements above given elements in a poset
    • "filtration(Poset)" -- see filtration -- generates the filtration of a poset
    • "flagChains(Poset,List)" -- see flagChains -- computes the maximal chains in a list of flags of a ranked poset
    • "flagfPolynomial(Poset)" -- see flagfPolynomial -- computes the flag-f polynomial of a ranked poset
    • "flaghPolynomial(Poset)" -- see flaghPolynomial -- computes the flag-h polynomial of a ranked poset
    • "flagPoset(Poset,List)" -- see flagPoset -- computes the subposet of specified ranks of a ranked poset
    • "fPolynomial(Poset)" -- see fPolynomial -- computes the f-polynomial of a poset
    • "gapConvertPoset(Array)" -- see gapConvertPoset -- converts between Macaulay2's Posets and GAP's Posets
    • "gapConvertPoset(Poset)" -- see gapConvertPoset -- converts between Macaulay2's Posets and GAP's Posets
    • "gapConvertPoset(String)" -- see gapConvertPoset -- converts between Macaulay2's Posets and GAP's Posets
    • "greeneKleitmanPartition(Poset)" -- see greeneKleitmanPartition -- computes the Greene-Kleitman partition of a poset
    • "hasseDiagram(Poset)" -- see hasseDiagram -- produces the Hasse diagram of a poset
    • height(Poset) -- computes the height of a poset
    • "hibiIdeal(Poset)" -- see hibiIdeal -- produces the Hibi ideal of a poset
    • "hibiRing(Poset)" -- see hibiRing -- produces the Hibi ring of a poset
    • "hPolynomial(Poset)" -- see hPolynomial -- computes the h-polynomial of a poset
    • "incomparabilityGraph(Poset)" -- see incomparabilityGraph -- produces the incomparability graph of a poset
    • "indexLabeling(Poset)" -- see indexLabeling -- relabels a poset with the labeling based on the indices of the vertices
    • "intersectionLattice(List,Ring)" -- see intersectionLattice -- generates the intersection lattice of a hyperplane arrangement
    • "isAntichain(Poset,List)" -- see isAntichain -- determines if a given list of vertices is an antichain of a poset
    • "isAtomic(Poset)" -- see isAtomic -- determines if a lattice is atomic
    • "isBounded(Poset)" -- see isBounded -- determines if a poset is bounded
    • "isComparabilityGraph(Graph)" -- see isComparabilityGraph -- determines if a graph is the comparability graph of a poset
    • isConnected(Poset) -- determines if a poset is connected
    • "isDistributive(Poset)" -- see isDistributive -- determines if a lattice is distributive
    • isEulerian(Poset) -- determines if a ranked poset is Eulerian
    • "isGeometric(Poset)" -- see isGeometric -- determines if a lattice is geometric
    • "isGraded(Poset)" -- see isGraded -- determines if a poset is graded
    • "isLattice(Poset)" -- see isLattice -- determines if a poset is a lattice
    • "isLowerSemilattice(Poset)" -- see isLowerSemilattice -- determines if a poset is a lower (or meet) semilattice
    • "isLowerSemimodular(Poset)" -- see isLowerSemimodular -- determines if a ranked lattice is lower semimodular
    • "isModular(Poset)" -- see isModular -- determines if a lattice is modular
    • "isomorphism(Poset,Poset)" -- see isomorphism -- computes an isomorphism between isomorphic posets
    • "isRanked(Poset)" -- see isRanked -- determines if a poset is ranked
    • "isSperner(Poset)" -- see isSperner -- determines if a ranked poset has the Sperner property
    • "isStrictSperner(Poset)" -- see isStrictSperner -- determines if a ranked poset has the strict Sperner property
    • "isUpperSemilattice(Poset)" -- see isUpperSemilattice -- determines if a poset is an upper (or join) semilattice
    • "isUpperSemimodular(Poset)" -- see isUpperSemimodular -- determines if a lattice is upper semimodular
    • "joinExists(Poset,Thing,Thing)" -- see joinExists -- determines if the join exists for two elements of a poset
    • "joinIrreducibles(Poset)" -- see joinIrreducibles -- determines the join irreducible elements of a poset
    • "labelPoset(Poset,HashTable)" -- see labelPoset -- relabels a poset with the specified labeling
    • "lcmLattice(Ideal)" -- see lcmLattice -- generates the lattice of lcms in an ideal
    • "linearExtensions(Poset)" -- see linearExtensions -- computes all linear extensions of a poset
    • "maximalAntichains(Poset)" -- see maximalAntichains -- computes all maximal antichains of a poset
    • "maximalChains(Poset)" -- see maximalChains -- computes all maximal chains of a poset
    • "maximalElements(Poset)" -- see maximalElements -- determines the maximal elements of a poset
    • "meetExists(Poset,Thing,Thing)" -- see meetExists -- determines if the meet exists for two elements of a poset
    • "meetIrreducibles(Poset)" -- see meetIrreducibles -- determines the meet irreducible elements of a poset
    • "minimalElements(Poset)" -- see minimalElements -- determines the minimal elements of a poset
    • "moebiusFunction(Poset)" -- see moebiusFunction -- computes the Moebius function at every pair of elements of a poset
    • "naturalLabeling(Poset)" -- see naturalLabeling -- relabels a poset with a natural labeling
    • "naturalLabeling(Poset,ZZ)" -- see naturalLabeling -- relabels a poset with a natural labeling
    • "ncPartitions(ZZ)" -- see ncPartitions -- generates the non-crossing partitions of size $n$
    • "ncpLattice(ZZ)" -- see ncpLattice -- computes the non-crossing partition lattice of set-partitions of size $n$
    • "openInterval(Poset,Thing,Thing)" -- see openInterval -- computes the subposet contained strictly between two points
    • "orderComplex(Poset)" -- see orderComplex -- produces the order complex of a poset
    • "orderIdeal(Poset,List)" -- see orderIdeal -- computes the elements below given elements in a poset
    • "outputTexPoset(Poset,String)" -- see outputTexPoset -- writes a LaTeX file with a TikZ-representation of a poset
    • "partitionLattice(ZZ)" -- see partitionLattice -- computes the lattice of set-partitions of size $n$
    • "plueckerPoset(ZZ)" -- see plueckerPoset -- computes a poset associated to the Pluecker relations
    • "poincare(Poset)" -- see poincarePolynomial -- computes the Poincare polynomial of a ranked poset with a unique minimal element
    • "poincarePolynomial(Poset)" -- see poincarePolynomial -- computes the Poincare polynomial of a ranked poset with a unique minimal element
    • "poset(List)" -- see poset -- creates a new Poset object
    • "poset(List,Function)" -- see poset -- creates a new Poset object
    • "poset(List,List)" -- see poset -- creates a new Poset object
    • "poset(List,List,Matrix)" -- see poset -- creates a new Poset object
    • Poset _ List -- returns elements of the ground set
    • Poset _ ZZ -- returns an element of the ground set
    • Poset _* -- returns the ground set of a poset
    • "vertices(Poset)" -- see Poset _* -- returns the ground set of a poset
    • "posetJoin(Poset,Thing,Thing)" -- see posetJoin -- determines the join for two elements of a poset
    • "posetMeet(Poset,Thing,Thing)" -- see posetMeet -- determines the meet for two elements of a poset
    • "pPartitionRing(Poset)" -- see pPartitionRing -- produces the p-partition ring of a poset
    • "principalFilter(Poset,Thing)" -- see principalFilter -- computes the elements above a given element in a poset
    • "principalOrderIdeal(Poset,Thing)" -- see principalOrderIdeal -- computes the elements below a given element in a poset
    • "Poset * Poset" -- see product(Poset,Poset) -- computes the product of two posets
    • product(Poset,Poset) -- computes the product of two posets
    • "projectivizeArrangement(List,Ring)" -- see projectivizeArrangement -- computes the intersection poset of a projectivized hyperplane arrangement
    • "randomPoset(List)" -- see randomPoset -- generates a random poset with a given relation probability
    • "randomPoset(ZZ)" -- see randomPoset -- generates a random poset with a given relation probability
    • "rankFunction(Poset)" -- see rankFunction -- computes the rank function of a ranked poset
    • "rankGeneratingFunction(Poset)" -- see rankGeneratingFunction -- computes the rank generating function of a ranked poset
    • "rank(Poset)" -- see rankPoset -- generates a list of lists representing the ranks of a ranked poset
    • "rankPoset(Poset)" -- see rankPoset -- generates a list of lists representing the ranks of a ranked poset
    • "realRegions(List,Ring)" -- see realRegions -- computes the number of regions a hyperplane arrangement divides the space into
    • "removeIsomorphicPosets(List)" -- see removeIsomorphicPosets -- returns a sub-list of non-isomorphic posets
    • "resolutionPoset(ChainComplex)" -- see resolutionPoset -- generates a poset from a resolution
    • "resolutionPoset(Ideal)" -- see resolutionPoset -- generates a poset from a resolution
    • "resolutionPoset(MonomialIdeal)" -- see resolutionPoset -- generates a poset from a resolution
    • "setPartition(List)" -- see setPartition -- computes the list of set-partitions of size $n$
    • "setPartition(ZZ)" -- see setPartition -- computes the list of set-partitions of size $n$
    • "setPDFViewer(String)" -- see setPDFViewer -- sets the default PDFViewer option
    • "setPrecompute(Boolean)" -- see setPrecompute -- sets the Precompute configuration
    • "setSuppressLabels(Boolean)" -- see setSuppressLabels -- sets the SuppressLabels configuration
    • "standardMonomialPoset(MonomialIdeal)" -- see standardMonomialPoset -- generates the poset of divisibility in the monomial basis of an ideal
    • "standardMonomialPoset(MonomialIdeal,ZZ,ZZ)" -- see standardMonomialPoset -- generates the poset of divisibility in the monomial basis of an ideal
    • "subposet(Poset,List)" -- see subposet -- computes the induced subposet of a poset given a list of elements
    • "tex(Poset)" -- see texPoset -- generates a string containing a TikZ-figure of a poset
    • "texPoset(Poset)" -- see texPoset -- generates a string containing a TikZ-figure of a poset
    • "transitiveClosure(List,List)" -- see transitiveClosure -- computes the transitive closure of a set of relations
    • "transitiveOrientation(Graph)" -- see transitiveOrientation -- generates a poset whose comparability graph is the given graph
    • "tuttePolynomial(Poset)" -- see tuttePolynomial -- computes the Tutte polynomial of a poset
    • "Poset + Poset" -- see union -- computes the union of two posets
    • "union(Poset,Poset)" -- see union -- computes the union of two posets
    • "youngSubposet(List)" -- see youngSubposet -- generates a subposet of Young's lattice
    • "youngSubposet(List,List)" -- see youngSubposet -- generates a subposet of Young's lattice
    • "youngSubposet(ZZ)" -- see youngSubposet -- generates a subposet of Young's lattice
    • "zetaPolynomial(Poset)" -- see zetaPolynomial -- computes the zeta polynomial of a poset
  • Symbols
    • "PDFDirectory" -- see displayPoset -- generates a PDF representation of a poset and attempts to display it
    • "PDFViewer" -- see displayPoset -- generates a PDF representation of a poset and attempts to display it
    • "OriginalPoset" -- see distributiveLattice -- computes the lattice of order ideals of a poset
    • "GroundSet" -- see Poset -- a class for partially ordered sets (posets)
    • "RelationMatrix" -- see Poset -- a class for partially ordered sets (posets)
    • "Relations" -- see Poset -- a class for partially ordered sets (posets)
    • "AntisymmetryStrategy" -- see poset -- creates a new Poset object
    • Precompute -- a package-wide configuration that toggles precomputation
    • "Bias" -- see randomPoset -- generates a random poset with a given relation probability
    • "Jitter" -- see texPoset -- generates a string containing a TikZ-figure of a poset
    • "SuppressLabels" -- see texPoset -- generates a string containing a TikZ-figure of a poset

For the programmer

The object Posets is a package.