Order Ideal

Maximal Elements Minimal Elements Antichain Order Ideal Linear Extention References

Maximal Elements

\(\textbf{Definition: }\)Let \(P\) be a poset and \(S\subset P\). An element \(s\in S\) is called maximal element of \(S\) if there is no \(s'\in S\) such that \(s\lt s'\).


Minimal Elements

\(\textbf{Definition: }\)Let \(P\) be a poset and \(S\subset P\). An element \(s\in S\) is called minimal element of \(S\) if there is no \(s'\in S\) such that \(s'\lt s\).


Antichain

\(\textbf{Definition: }\)A set \(A\) is an antichain (or Sperner family or clutter) of a poset \(P\) if \(A\subset P\) and any pair of elements of \(A\) is incomparable in \(P\). The collection of all antichains of \(P\) is denoted \(\mathrm{Anti(P)}\), and the poset induced by inclusion on \(A(P)\) is denoted ambiguously by \(A(P)\).

Order Ideal

\(\textbf{Definition: }\) A set \(I\) is an order ideal (or semi-ideal or down-set or decreasing subset) of a poset \(P\) is a set \(I\subset P\) such that if \(p\in I\) and \(p'\lt p\), then \(p'\in I\). The collection of all order ideals of \(P\) is denoted \(J(P)\).

Linear Extention

\(\textbf{Definition: }\)Let poset \(P\) to have \(n\) elements and let \([n]=\{1, 2, \dots, n\}\). A linear extension of \(P\) is a bijection \(\mathfrak{L}: P\to [n]\) such that if \(p\lt p'\), then \(\mathfrak{L}(p)\lt \mathfrak{L}(p')\).

References