TOPICS
Search

Partial Order Ideal


A partial order ideal I of a partial order P is a subset of P such that if y in I and x<y, then x in I. This is the combinatorial convention, which includes the empty set (Stanley 2011, p. 281). In other order-theoretic conventions, an ideal is additionally required to be nonempty and a directed set (Abramsky and Jung 1994, Definition 2.1.8).

For k disjoint chains in which the ith chain contains n_i elements, there are (1+n_1)(1+n_2)...(1+n_k) ideals in the combinatorial sense. The number of such ideals of an n-element fence poset is the Fibonacci number F_(n+2).


Explore with Wolfram|Alpha

References

Abramsky, S. and Jung, A. "Domain Theory." In Handbook of Logic in Computer Science, Vol. 3 (Ed. S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum). Oxford, England: Clarendon Press, pp. 1-168, 1994. Corrected and expanded online version. https://www.cs.ox.ac.uk/people/samson.abramsky/handbook.pdf.Ruskey, F. "Information on Ideals of Partially Ordered Sets." https://web.archive.org/web/20120626002621/http://www.theory.csc.uvic.ca/~cos/inf/pose/Ideals.html.Stanley, R. P. Enumerative Combinatorics, Vol. 1, 2nd ed. Draft version of Jul. 15, 2011, p. 281. https://math.mit.edu/~rstan/ec/ec1.pdf.Steiner, G. "An Algorithm to Generate the Ideals of a Partial Order." Operat. Res. Let. 5, 317-320, 1986.

Referenced on Wolfram|Alpha

Partial Order Ideal

Cite this as:

Weisstein, Eric W. "Partial Order Ideal." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PartialOrderIdeal.html

Subject classifications