Originator: Gary Gordon (presented by Garth Isaak - REGS 2010)
Definitions: An antichain in a partially ordered set P is a family of incomparable elements. An order ideal or down-set is a family of elements closed under moving downward in the order relation in P. For any antichain A, the ideal generated by A, written D[A], is {y∈P: y≤x for some x∈A}. The down-deck of a poset P is the multiset of pairs (|A|,|D(A)|), where A ranges over all antichains in P.
The poset N is the 4-element poset whose strict order relation is {a<c, a<d, b<d}. When r and s are integers, the poset r+s is the disjoint union of chains of sizes r and s. A rooted tree poset is a poset such that there is exactly one minimal element (the root) and the ideal generated by any single element is a chain. That is, the poset "grows up" from the root, and its diagram is a tree. Neither N nor 3+1 is a rooted tree.
Given a poset Q, a poset P is Q-free if no subposet of P is isomorphic to Q (since "poset" means "partially ordered set", by "subposet" we mean a subset of the elements, inheriting all the relations among them). A series-parallel poset is a poset that can be constructed from isolated elements by using two operations: parallel composition (disjoint union) and series composition (combine two smaller such posets by putting each element of the first above each element of the second). The rooted trees are the series-parallel posets in which all series compositions use a single element as the `bottom' order. A poset is a series-parallel poset if and only if it is N-free (a series or parallel composition cannot introduce N if it was not present in either poset being combined.
A poset is an interval order if it can be represented by assigning each element an interval on the real line so that x<y if and only if the interval for x is completely to the left of the interval for y. A poset is a semiorder if this can be done using intervals of the same length. Fishburn [F] characterized the interval orders as the 2+2-free posets. The Scott-Suppes Theorem [SS] states that a poset is a semiorder if and only if it is both 2+2-free and 3+1-free.
Background: Every ideal is the ideal generated by the antichain consisting of its maximal elements, so in any poset the ideals are in one-to-one correspondence with the antichains. Thus the down-deck contains the multiset of antichain sizes in the first coordinate and the multiset of ideal sizes in the second coordinate, with the additional information of how they are paired.
The terminology "down-deck" is motivated by the Reconstruction Problem in graphs, where we try to reconstruct a graph from its deck of subgraphs obtained by deleted one vertex; here we try to reconstruct a poset from its down-deck. Interval orders are reconstructible from the pairs (|D[x]|,|U[x]|) for all elements x in P.
Problem 1: Which posets P are determined (up to isomorphism) by their down-decks?
Comments: Both N and 3+1 have down-deck {(0,0),(1,1),(1,1),(1,2),(1,3),(2,2),(2,3),(2,4)}, so these posets are not reconstructible from their down-decks. On the other hand, it follows from an algebraic result of Gordon [G], that every rooted tree is reconstructible from its down-deck.
Problem 2: Given a combinatorial proof that every rooted tree is reconstructible from its down-deck.
Conjecture 3: Series-parallel posets are reconstructible from their down-decks.
Gordon [G] studied what we have called the down-deck in the context of extending the Tutte polynomial to greedoids defined by ordered sets. Using algebraic methods in that context, he showed that the series-parallel posets in a class containing the rooted trees are reconstructible from their down-decks.
Question 4: Are semiorders (or perhaps 3+1-free posets) reconstructible from their down-decks?
Comment: The suggested families exclude the known pair {N, 3+1} having the same down-deck: N is not a series-parallel poset, and 3+1 is not a semiorder. However, both N and 3+1 are interval orders, so the class cannot be extended that far.
References:
[F] Fishburn, Peter C.; Interval representations for interval orders and
semiorders. J. Mathematical Psychology 10 (1973), 91--105.
[G] Gordon, Gary, Series-parallel posets and the Tutte polynomial, Disc. Math.,
158 (1996) 63-75.
[SS] Scott, Dana; Suppes, Patrick;
Foundational aspects of theories of measurement.
J. Symb. Logic 23 1958 113--128.