Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

Question

Consider two partially ordered sets $A = \{a< b,a< c\}$, $B=\{x< z,y< z\}$.

Their linear extensions (here we allow equality in linear extensions) for $A, B$ are $$A_L=\{A_1=\{a< b< c\}, A_2=\{a< b= c\}, A_3=\{a< c< b\}\}$$ and $$B_L = \{ B_1 = \{x< y< z\}, B_2=\{y< x< z\}, B_3 =\{x= y< z\}\}$$

We may define two order isomorphisms

$f_1: A_1\to B_1$ by $f_1(a)=x, f_1(b)=y, f_1(c)=z$ and

$f_2:A_3\to B_2$ by $f_2(a)=y, f_2(b)=x, f_2(c)=z$,

but there is no order isomorphism $f_3$ from $A_2$ to $B_3$ s.t. $t< s\Longleftrightarrow f_3(t)< f_3(s)$ and $t=s \Longleftrightarrow f_3(t)=f_3(s)$. (And it's easy to see that no other pairing of the $A_i$ with the $B_j$ will allow such maps to be chosen.)

There are no order isomorphisms from $A$ to $B$, either.

Is the following conjecture true?

For any partially ordered sets $A,B$, if there exist isomorphisms from $A$'s linear extensions to $B$'s, then there exists an isomorphism from $A$ to $B$.

If not, could you give me a counter example?

Answer 1

There are two different questions depending on whether the linear extensions are given to us labeled. If we wish to reconstruct a poset $A$ from a labeled list of its linear extensions, then our job is very easy (even if we use "usual" linear extensions with no "=" appearing): for two elements $a, b \in A$, we have $a < b$ in $A$ if and only if $a < b$ in every linear extension of $A$, and so the result follows immediately. (This is the case that Joel David Hamkins addressed a few seconds before I posted :-) .)

If we have unlabeled linear extensions (so really the data that we receive looks like $\{(* < * < *), (* < * = *), (* < * < *)\}$ or the like) then I conjecture that the result is false, with the following potential counter-example.

A Steiner triple system $S$ on a set $X = \{x_1, \ldots, x_{13}\}$ of 13 vertices is a collection of 26 blocks $B_1, \ldots, B_{26}$, each of which is a set of three elements of $X$, such that every two elements of $X$ occur in exactly one block $B_i$. To such a system we may associate a poset $P(S)$ whose vertices are $\{x_1, \ldots, x_{13}, B_1, \ldots, B_{26}\}$ with order relation $\in$. There are two nonisomorphic Steiner triple systems on 13 vertices, yielding two nonisomorphic posets. (Nonisomorphism is easy: the poset conveys exactly the information about which triple contains which elements.) I think that these posets may be a counter-example, for the following (weak) reasons:

Given the list of linear extensions (in your sense) of a poset, it's easy to reconstruct certain basic data about it. In particular, we can find for each $i$ the number of elements whose shortest saturated chain to a minimal (or maximal) element is of length $i$ by looking for the linear extension that is most "bottom-heavy" (or "top-heavy"), in the sense that the initial block of equal elements is as large as possible (which will happen exactly when it consists of all the minimal elements), and the next block of equal elements is as large as possible given that the previous condition is met (which will happen exactly when it consists of all elements that cover a minimal element), and so on. By varying this idea slightly, we can also determine the list of up-degrees of each minimal element in the Hasse diagram (i.e., we know how many elements cover each minimal element), and the list of the number of elements that cover each pair of minimal elements, and so on. This data is not enough to reconstruct the poset on its own, since we don't know how things correspond in the different extensions, and indeed the two posets described above share this data but aren't isomorphic.

Unfortunately, it's clear that knowing all the linear extensions gives us more information than what I've used in the above paragraph. Unfortunately, these posets are too large for me to just slap them into a computer and check whether they really have the same set of extensions. Also, I can't find my copy of Enumerative Combinatorics at the moment to check what is actually known about this sort of thing.

Answer 2

Let me consider another reasonable interpretation of the question, which has a nice answer.

It seems to me that the OP is considering the extent to which a partial order on a set is determined by the collection of its linear completions. Specifically, let $A$ be any set, not necessarily finite, and let $\lt$ be a partial order on $A$. The question is, to what extent is $\lt$ determined by the collection of its linear completions? That is, to what extent is $\lt$ determined by the set of linear orders $\lt'$ on $A$ such that $\lt\subset\lt'$, meaning $a\lt b\rightarrow a\lt' b$?

The answer is that $\lt$ is completely determined by the set of its linear completions. The reason is that $\lt$ is precisely equal to the intersection of all linear orders containing $\lt$. To see this, observe first that if $a\lt b$, then clearly $a\lt'b $ for any linear completion $\lt'$ of $\lt$. Conversely, if $a\not\lt b$, then let $\lt_0$ be the transitive closure of $\lt$ with the pair $\langle b,a\rangle$, so that $b\lt_0 a$. This is a partial order extending $\lt$ placing $b$ below $a$. Now, by Zorn's lemma (unnecessary in the finite or countable case), the order $\lt_0$ has a linear completion $\lt'$, which is also a linear completion of $\lt$. Thus, there is a linear completion of $\lt$ for which $\not a\lt' b$. It follows that $\lt$ is precisely the common order among all linear completions.

In particular, if two partial orders on $A$ have the same sets of completions, then they are equal.