Data Structure for Posets

Suppose that P is a labeled poset with n elements.
The *child form* of P is the list of n lists in which the kth list is the set of the elements covered by element k of P, which must be listed in ascending order.
Further assume that P is naturally labeled.
Then given P's child form, it is especially easy to draw its Hasse (order) diagram.
Here is the child form of the diamond poset: {{}, {1}, {1}, {2, 3}}.

Suppose we ask Mathematica to "sort" a collection of child forms for one or more posets which each have n elements. Mma will order them lexicographically from the left, with a constituent child set of one child form being regarded as earlier than the corresponding child set of another child form if it is shorter than that corresponding child set. If the two corresponding child sets have the same length, the earlier one is found using lexicographic comparison from the left using the ordering of the positive integers on the labels of the childs.
We define the *standard form* for an unlabeled poset P to be the earliest of the child forms for its various possible natural labelings, according to this ordering convention.
For example, the standard form for the "N" poset is {{}, {}, {1}, {1, 2}} since this form is earlier than the child forms {{}, {}, {2}, {1, 2}};; {{}, {}, {1, 2}, {1}};; {{}, {}, {1, 2}, {12}};; and {{}, {1}, {}, {1, 3}} for the four other possible natural labelings.
All of the posets appearing in this atlas are presented in standard form.
In addition, all poset lists in this atlas have been sorted by the Mathematica rule described above.
The *name* of an unlabeled poset P with n elements is "n.#", where # is the position of its standard form within the sorted list of all standard forms of all posets with n elements.
Properties of this standard form for posets.
Given a poset P in child form, our Mathematica function StdFormIso[] will return the standard form for P along with the isomorphism between the two forms.

Suppose that P is a poset with n elements.
An *order extension* f of P is an order preserving bijection from P to the total ordering of {1, 2, .., n}.
Now suppose that P is labeled.
Then f can be described with the n-tuple (f(1), f(2), .., f(n)).
The corresponding *inverse extension* of P is the inverse of this permutation.
Alternatively, the inverse extensions of P are the ways of reading off the labels of P from bottom to top in a way which respects the partial order.
For example, when the "N" poset is labeled in the only way which is consistent with its standard form, its five inverse extensions are (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (2, 1, 3, 4), (2, 1, 4, 3).
All inverse extensions of all posets with up to 7 elements are stored in the associated data files invexts*.
Given a naturally labeled poset P, there exists at least one relabeling of P which gives rise to the standard form of P. It is an order extension of P.
Each such relabeling is a permutation of {1, 2, .., n}, and we describe it with its one-row form.
Given the child form C of a naturally labeled poset P, we define the Mathematica symbol s[C] to be the n-list which is the earliest permutation which relabels P in a way which gives rise to the standard form of P.
The values of s[C] for all naturally labeled posets with no more than 7 elements are stored in the associated data files stdisos*.
Given an unlabeled n-poset P with standard child form C, we define the Mathematica symbol m[C] to be the position of C in the list of all posets with n elements (i.e. the second portion of the name of P).
The values of m[C] for the standard forms for all posets with up to 7 elements are stored in the associated data files lookups*.

Example Application
Suppose we are given a naturally labeled poset P which has no more than 7 elements and which has child form C.
Then we can transform C according to s[C] to obtain the standard form T for P.
Next, m[T] gives us the name of P.
This gives us the position of the list of inverse extensions for P (within the list of all lists of inverse extensions) with respect to a labeling which is consistent with the standard form of P.
After retrieving this list of inverse extensions, the inverse of the transformation s[C] can be used to produce the list of all inverse extensions of P with its original labeling.

Return to Chapel Hill Poset Atlas Home Page Table of Contents