# Monomorphic and bimorphic partial orders

Pierre Ille, Jean-Xavier Rampon

► To cite this version:

Pierre Ille, Jean-Xavier Rampon. Monomorphic and bimorphic partial orders. The Australasian Journal of Combinatorics, 2024, 89 (2), pp.179-195. hal-04766238

HAL Id: hal-04766238

https://hal.science/hal-04766238v1

Submitted on 4 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Monomorphic and bimorphic partial orders

PIERRE ILLE

Aix Marseille Univ, CNRS, I2M
Marseille, France
pierre.ille@univ-amu.fr

JEAN-XAVIER RAMPON

FST-Université de Nantes, 2 rue de la Houssinière
BP 92208, 44322 Nantes Cedex 3, France
jean-xavier.rampon@univ-nantes.fr

## Abstract

A (finite) partial order $P$ is monomorphic if for all $v, w \in V(P)$, $P - v \simeq P - w$. Moreover, a partial order $P$ is bimorphic if there exist $x, y \in V(P)$ such that $P - x \not\subset P - y$, and for every $v \in V(P)$, we have $P - v \simeq P - x$ or $P - v \simeq P - y$. Using the modular decomposition, we characterize the monomorphic partial orders and the bimorphic partial orders. Their reconstruction follows from these characterizations.

## 1 Introduction

A digraph $D$ is defined by a (finite) vertex set $V(D)$ and an arc set $A(D)$, where an arc is an ordered pair of distinct vertices. We denote $|V(D)|$ by $v(D)$. Let $D$ be a digraph. With $W \subseteq V(D)$, we associate the subdigraph $D[W]$ of $D$ induced by $W$ defined by $V(D[W]) = W$ and $A(D[W]) = A(D) \cap (W \times W)$. When $W = V(D) \setminus W'$, $D[W]$ is also denoted by $D - W'$, and by $D - w$ when $W' = \{w\}$.

We associate with a digraph $D$ its dual $D^*$ defined on $V(D^*) = V(D)$ as follows. For any $v, w \in V(D^*)$, $vw \in A(D^*)$ if $wv \in A(D)$.

A digraph $D$ is transitive provided that for any $u, v, w \in V(D)$, if $uv, vw \in A(D)$, then $uw \in A(D)$. A (strict) partial order is a transitive digraph. Consider a partial order $P$. For distinct $v, w \in V(P)$, $v <_P w$ means $vw \in A(P)$. For $v, w \in V(P)$, $v \le_P w$ means $v = w$ or $v <_P w$. For distinct $v, w \in V(P)$, $v \nparallel_P w$ means $vw \notin A(P)$ and $wv \notin A(P)$. We associate with a partial order $P$ its comparability graph $\text{Comp}(P)$ defined on $V(\text{Comp}(P)) = V(P)$ as follows. For distinct $v, w \in V(P)$, $vw \in E(\text{Comp}(P))$ if $v <_P w$ or $w <_P v$. A total order is a partial order whose comparability graph is complete. Given $k \ge 1$, the usual total order on $\{0, \dots, k-1\}$ is denoted by $T_k$. A partial order is discrete if its comparability graph is empty.
As examples of partial orders, $\Lambda$ is the partial order defined on $V(\Lambda) = \{0, 1, 2\}$ by $E(\Lambda) = \{02, 12\}$. Set $\vee = \Lambda^*$. Furthermore, the partial order $\nW$ is defined on $V(\nW) = \{0, 1, 2, 3\}$ by $E(\nW) = \{02, 12, 13\}$.

Let $P$ and $Q$ be partial orders. An *isomorphism* from $P$ onto $Q$ is a bijection $f$ from $V(P)$ onto $V(Q)$ such that for all $v, w \in V(P)$, we have $v <_P w$ if and only if $f(v) <_Q f(w)$. The partial orders $P$ and $Q$ are *isomorphic*, which is denoted by $P \cong Q$, if there exists an isomorphism from $P$ onto $Q$.

Let $P$ be a partial order. We define an equivalence relation $\cong_P$ on $V(P)$ as follows. For any $v, w \in V(P)$, $v \cong_P w$ if $P - v$ and $P - w$ are isomorphic. This equivalence relation comes naturally from the reconstruction problem (see Section 1.2). It comes also from the notions of similar vertices and pseudo-similar vertices [12]. A partial order $P$ is said to be *monomorphic* (or $(v(P) - 1)$-monomorphic [3]) if $\cong_P$ admits a unique equivalence class. A partial order $P$ is said to be *bimorphic* if $\cong_P$ admits exactly two equivalence classes. We characterize the monomorphic partial orders and the bimorphic partial orders. We deduce their reconstruction (see Section 1.2).

## 1.1 Modular decomposition

Let $P$ be a partial order. A subset $M$ of $V(P)$ is a *module* (or an *order-autonomous set*) of $P$ if for each $v \in V(P) \setminus M$, one of the next three statements holds

* for every $x \in M$, $v <_P x$;

* for every $x \in M$, $x <_P v$;

* for every $x \in M$, $v \|_P x$.

For instance, $\emptyset$, $V(P)$ and $\{v\}$ ($v \in V(P)$) are modules of $P$, called the *trivial modules* of $P$. A partial order $P$ is *indecomposable* if all its modules are trivial, otherwise it is *decomposable*. A partial order $P$ is *prime* if it is indecomposable with $v(P) \ge 3$. It is easy to verify that every partial order on 3 vertices is decomposable. Moreover, a partial order on 4 vertices is prime if and only if it is isomorphic to $\nW$.

Let $P$ be a partial order. For disjoint modules $M$ and $N$ of $P$, one of the next three statements holds

* for any $v \in M$ and $w \in N$, $v <_P w$;

* for any $v \in M$ and $w \in N$, $w <_P v$;

* for any $v \in M$ and $w \in N$, $v \|_P w$.

This property allows us to define the quotient as follows. A *modular partition* of $P$ is a partition of $V(P)$ into modules of $P$. An element of a modular partition is called a *block* of the partition. Recall that a *transversal* of a modular partition $\Pi$ of $P$ is a subset $W$ of $V(P)$ such that $|W \cap M| = 1$ for every $M \in \Pi$. With a modular partition $\Pi$ of $P$, we associate the *quotient $P/\Pi$* of $P$ by $\Pi$ as being the unique partial
order defined on $V(P/\Pi) = \Pi$ such that for a transversal $W$ of $\Pi$, the function which maps each $w \in W$ to the unique block of $\Pi$ containing $w$ is an isomorphism from $P[W]$ onto $P/\Pi$.

Let $P$ be a partial order. A subset $M$ of $V(P)$ is a strong module of $P$ if $M$ is a module of $P$ such that for every module $N$ of $P$, if $M \cap N \neq \emptyset$, then $M \subseteq N$ or $N \subseteq M$. For instance, the trivial modules of $P$ are strong modules too. We denote by $\mathcal{G}(P)$ the family of the strong modules of $P$ which are maximal under inclusion among the proper strong modules of $P$. The next theorem is due to Gallai [4] (see [11, Theorem 1.2]). We use the following notation.

**Notation 1.1.** Let $G$ be a graph. Recall that $\overline{G}$ denotes the complement of $G$. In the sequel, the collection of the vertex sets of the (connected) components of $G$ is denoted by $\mathcal{C}(G)$.

**Theorem 1.2.** Given a partial order $P$ such that $v(P) \geq 2$, $\mathcal{G}(P)$ is a modular partition of $P$ and one of the next three assertions holds

* $\text{Comp}(P)$ is disconnected, $\mathcal{G}(P) = \mathcal{C}(\text{Comp}(P))$, and $P/\mathcal{G}(P)$ is discrete;

* $\overline{\text{Comp}(P)}$ is disconnected, $\mathcal{G}(P) = \mathcal{C}(\overline{\text{Comp}(P)})$, and $P/\mathcal{G}(P)$ is a total order;

* $\text{Comp}(P)$ and $\overline{\text{Comp}(P)}$ are connected, $\mathcal{G}(P)$ is the set of the maximal proper modules of $P$, and $P/\mathcal{G}(P)$ is prime.

**Remark 1.3.** Consider a partial order $P$ such that $v(P) \geq 3$. Since the elements of $\mathcal{G}(P)$ are proper modules of $P$, we have $|\mathcal{G}(P)| \geq 2$. Consequently, if $\mathcal{G}(P)$ admits an element $M$ such that $|M| \geq 2$, then $P$ is decomposable. Moreover, if $\mathcal{G}(P) = \{\{v\} : v \in V(P)\}$, then $P \simeq (P/\mathcal{G}(P))$. Clearly, a transitive order or a discrete partial order with at least 3 vertices are decomposable. It follows that $P$ is prime if and only if $P/\mathcal{G}(P)$ is prime and $\mathcal{G}(P) = \{\{v\} : v \in V(P)\}$.

## 1.2 Reconstruction

Given digraphs $D$ and $\Delta$ such that $V(D) = V(\Delta)$, $D$ and $\Delta$ are hypomorphic if $D - v$ and $\Delta - v$ are isomorphic for each $v \in V(D)$. A digraph $D$ is then said to be reconstructible if every digraph, which is hypomorphic to $D$, is isomorphic to $D$. A collection $\mathcal{C}$ of partial orders is recognizable if for any hypomorphic partial orders $P$ and $Q$, we have $P$ is a member of $\mathcal{C}$ if and only if $Q$ is a member of $\mathcal{C}$.

We recall Kelly's lemma.

**Lemma 1.4** (Kelly [9]). Consider hypomorphic partial orders $P$ and $Q$. For each partial order $R$ such that $v(R) < v(P)$, we have

$$|\{X \subseteq V(P) : P[X] \simeq R\}| = |\{X \subseteq V(Q) : Q[X] \simeq R\}|.$$

We use the following result obtained from Lemma 1.4 by choosing $R = T_2$.
**Corollary 1.5.** Given hypomorphic partial orders P and Q, if $v(P) \ge 3$, then $|A(P)| = |A(Q)|$.

The reconstruction of partial orders, the comparability graph of which is disconnected, is due to Harary [5] and Das [2].

**Lemma 1.6.** Given a partial order P such that $v(P) \ge 3$, if $P/\mathcal{G}(P)$ is discrete, then P is reconstructible.

Recall that a graph is *coconnected* if its complement is connected. The reconstruction of partial orders, the comparability graph of which is not coconnected, is due to Kratsch and Rampon [10].

**Proposition 1.7.** Given a partial order P such that $v(P) \ge 3$, if $P/\mathcal{G}(P)$ is a total order, then P is reconstructible.

We do not know if decomposable partial orders P such that $P/\mathcal{G}(P)$ is prime are reconstructible. However, the following result provides a partial answer in this case. It is obtained by translating [1, Theorem 4.1] (or [13, Corollary 7.4]) in terms of partial orders.

**Proposition 1.8.** Consider a partial order P such that $P/\mathcal{G}(P)$ is prime. Suppose that $v(P) - v(P/\mathcal{G}(P)) \ge 2$. Let $O$ be an orbit of $P/\mathcal{G}(P)$ under the action of its automorphism group. Let $X \in O$ such that $|X| \ge 2$. If there exists $x \in X$ such that for each $Y \in O$, $P[Y] \not= P[X \setminus \{x\}]$, then P is reconstructible.

We use Proposition 1.8 to prove that decomposable bimorphic partial orders are reconstructible (see the proof of Proposition 5.1). Furthermore, we do not know if prime partial orders are reconstructible. Nevertheless, Ille [6] proved that they are recognizable.

**Theorem 1.9.** Let P be a prime partial order such that $v(P) \ge 12$. For every partial order Q, if P and Q are hypomorphic, then Q is prime as well.

**Remark 1.10.** Schröder [13, Theorem 1.8] proved that prime graphs with at least 4 vertices are recognizable. Furthermore, a partial order is prime if and only if its comparability graph is too (for instance, see Ille and Rampon [8, Corollary 1]). Therefore, Theorem 1.9 holds for prime partial orders with at least 4 vertices.

Lastly, Ille and Rampon [7] established the reconstruction of partial orders by assuming that both partial orders share the same comparability graph.

**Theorem 1.11.** Consider hypomorphic partial orders P and Q such that $v(P) \ge 4$. If $\text{Comp}(P) = \text{Comp}(Q)$, then P and Q are isomorphic.

Obviously, the class of monomorphic partial orders and the class of bimorphic partial orders are recognizable. We prove that monomorphic partial orders and bimorphic partial orders are reconstructible (see Corollary 4.5 and Proposition 5.1).
## 1.3 Main results

Let $P$ be a partial order. We denote by $\min(P)$ the set of the minimal vertices of $P$. The set of the maximal vertices of $P$ is denoted by $\max(P)$. Furthermore, given partial orders $P$ and $Q$, the fact $P$ and $Q$ are isomorphic is denoted by $P \simeq Q$.

**Definition 1.12.** Let $P$ be a partial order. We associate with $P$ the set $\tau(P)$ of the subsets $W$ of $V(P)$ such that $P[W]$ is a total order. The height $\text{ht}(P)$ of $P$ is defined by

$$ \text{ht}(P) = \max(\{|W| : W \in \tau(P)\}) - 1. $$

Let $P$ be a partial order. Given $W \subseteq V(P)$, we say that $P$ is $W$-transitive if for $v, w \in W$, there exists an automorphism $\varphi$ of $P$ such that $\varphi(v) = w$. Recall that $P$ is said to be vertex-transitive if it is $V(P)$-transitive. Clearly, the only (finite) vertex-transitive partial orders are the discrete ones.

We obtain the following characterization of monomorphic partial orders in Section 4.

**Theorem 1.13.** Given a partial order $P$ such that $v(P) \ge 2$, $P$ is monomorphic if and only if either $P$ is a total order or $P/\mathcal{G}(P)$ is discrete and there exists $k \ge 1$ such that for every $X \in \mathcal{G}(P)$, $P[X] \simeq T_k$.

The characterization of bimorphic partial order follows from the next four results by applying Theorem 1.2. We establish the next four theorems in Section 5.

**Theorem 1.14.** Given a partial order $P$ such that $\text{Comp}(P)$ is disconnected, $P$ is bimorphic if and only if one of the following two assertions holds

(A1) there exist $l > k \ge 1$ such that for every $X \in \mathcal{G}(P)$, $P[X] \simeq T_k$ or $T_l$,
• there exist $X, Y \in \mathcal{G}(P)$ such that $P[X] \not\simeq P[Y]$;

(A2) there exists a bimorphic and connected partial order $Q$ such that for every $X \in \mathcal{G}(P)$, $P[X] \simeq Q$.

**Theorem 1.15.** Given a partial order $P$ such that $v(P) \ge 3$ and $\overline{\text{Comp}(P)}$ is disconnected, $P$ is bimorphic if and only if (at least) one of the following two assertions holds

(B1) $|\mathcal{G}(P)| = 2$ and for each $X \in \mathcal{G}(P)$, $P[X]$ is monomorphic;

(B2) $\mathcal{G}(P)$ contains a unique block $X$ such that $|X| \ge 2$, moreover $P[X]$ is monomorphic and $\min(P/\mathcal{G}(P)) = \{X\}$ or $\max(P/\mathcal{G}(P)) = \{X\}$.

**Theorem 1.16.** If $P$ is a prime partial order, then $P$ is bimorphic if and only if $\text{ht}(P) = 1$, $P$ is $\min(P)$-transitive, and $P$ is $\max(P)$-transitive (see Example 1.18).

**Theorem 1.17.** Given a partial order $P$ such that $\text{Comp}(P)$ and $\overline{\text{Comp}(P)}$ are connected, $P$ is bimorphic if and only if all of the following statements hold
(S1) $P/\mathcal{G}(P)$ is prime and bimorphic (see Theorem 1.16);

(S2) there exists a monomorphic partial order $Q_1$ such that for every $X \in \min(P/\mathcal{G}(P))$, $P[X] \simeq Q_1$;

(S3) there exists a monomorphic partial order $Q_2$ such that for every $X \in \max(P/\mathcal{G}(P))$, $P[X] \simeq Q_2$.

**Example 1.18.** Trotter [14] introduced the crowns in the following way. Consider $n \ge 3$ and $2 \le m \le n - 1$. The crown $C_n^m$ is defined on $V(C_n^m) = \{x_0, \dots, x_{n-1}\} \cup \{y_0, \dots, y_{n-1}\}$ as follows. Given $v, w \in V(C_n^m)$, $v <_{C_n^m} w$ if there exist $i, j \in \{0, \dots, n-1\}$ and $k \in \{0, \dots, m-1\}$ such that $v = x_i$, $w = y_j$, and $j \equiv i + k \bmod n$. The crown $C_n^m$ satisfies the following properties

• $\mathrm{ht}(C_n^m) = 1$, $\min(C_n^m) = \{x_0, \dots, x_{n-1}\}$, and $\max(C_n^m) = \{y_0, \dots, y_{n-1}\}$;

• $C_n^m$ is $\min(C_n^m)$-transitive and $C_n^m$ is $\max(C_n^m)$-transitive; precisely, the permutation of $V(C_n^m)$, defined by $x_i \mapsto x_{(i+1 \bmod n)}$ and $y_i \mapsto y_{(i+1 \bmod n)}$, is an automorphism of $C_n^m$;

• $C_n^m$ is self-dual;

• $C_n^m$ is prime.

It follows that $C_n^m$ is bimorphic by Theorem 1.16.

## 2 Preliminaries

Let $P$ be a partial order. For each $v \in V(P)$, the unique block of $\mathcal{G}(P)$ containing $v$ is denoted by $X(v)$.

**Lemma 2.1.** Let $P$ be a partial order such that $v(P) \ge 2$. Suppose that $\mathrm{Comp}(P)$ is disconnected. For $v, w \in V(P)$, if $v \cong_P w$, then $P[X(v)] \simeq P[X(w)]$. Moreover, for $v, w \in V(P)$, if $v \cong_P w$ and $|X(v)| \ge 2$, then $P[X(v) - v] \simeq P[X(w) - w]$.

*Proof.* By Theorem 1.2, $\mathcal{G}(P) = \mathcal{C}(\mathrm{Comp}(P))$ and $P/\mathcal{G}(P)$ is discrete. Let $x \in V(P)$. Clearly, for every $X \in \mathcal{G}(P)$ such that $x \notin X$, $\mathrm{Comp}(P)[X]$ is a component of $\mathrm{Comp}(P - x)$. Therefore, one of the following cases holds

1. $X(x) = \{x\}$, $\mathrm{Comp}(P - x)$ is connected, and $\mathcal{G}(P) = \{V(P) \setminus \{x\}, \{x\}\}$;

2. $X(x) = \{x\}$, $\mathrm{Comp}(P - x)$ is disconnected and $\mathcal{G}(P) = \mathcal{G}(P - x) \cup \{\{x\}\}$;

3. $|X(x)| \ge 2$, $\mathrm{Comp}(P - x)$ is disconnected,

$$ \mathcal{G}(P - x) = (\mathcal{G}(P) \setminus \{X(x)\}) \cup \mathcal{C}(\mathrm{Comp}(P[X(x)] - x)), \quad (1) $$
and hence for each $Y \in \mathcal{G}(P)$, we have

$$ 
\begin{aligned}
& |\{Z \in \mathcal{G}(P-x) : P[Z] \simeq P[Y]\}| \\
& = |\{Z \in \mathcal{G}(P) : P[Z] \simeq P[Y]\}| - 1 \text{ if } P[X(x)] \simeq P[Y] \\
\text{or} \\
& \geq |\{Z \in \mathcal{G}(P) : P[Z] \simeq P[Y]\}| \text{ if } P[X(x)] \not\simeq P[Y].
\end{aligned} 
\quad (2) $$

Note that $\mathrm{Comp}(P-x)$ is connected only in the first case. Furthermore, when $\mathrm{Comp}(P-x)$ is disconnected, we have $|\mathcal{G}(P-x)| = |\mathcal{G}(P)| - 1$ in the second case whereas $|\mathcal{G}(P-x)| \geq |\mathcal{G}(P)|$ in the third one.

Now, consider $v, w \in V(P)$ such that $v \cong_P w$. One of the three cases above holds for both $v$ and $w$. In the first two cases, $X(v) = \{v\}$ and $X(w) = \{w\}$, so $P[X(v)] \simeq P[X(w)]$. Lastly, suppose that the third case holds for $v$ and $w$. It follows from (2) that $P[X(v)] \simeq P[X(w)]$. Moreover, it follows from (1) that $P[X(v) - v] \simeq P[X(w) - w]$. $\square$

Schröder [12] obtained similar results in the proof of [12, Proposition 2.3] when $v \in \min(P)$, $w \in \max(P)$, and $\mathrm{rk}_P(w) > 0$.

**Lemma 2.2.** Let $P$ be a partial order such that $v(P) \geq 2$. Suppose that $\overline{\mathrm{Comp}(P)}$ and $\overline{\mathrm{Comp}(P)}$ are connected. For $v, w \in V(P)$, if $v \cong_P w$, then $P[X(v)] \simeq P[X(w)]$. Moreover, for $v, w \in V(P)$, if $v \cong_P w$ and $|X(v)| \geq 2$, then $P[X(v) - v] \simeq P[X(w) - w]$.

*Proof.* By Theorem 1.2, $\mathcal{G}(P)$ is the set of the maximal proper modules of $P$, and $P/\mathcal{G}(P)$ is prime. Given $x \in V(P)$, one of the following cases holds

1. $X(x) = \{x\}$ and $(P-x)/\mathcal{G}(P-x)$ is not prime;

2. $X(x) = \{x\}$, $(P-x)/\mathcal{G}(P-x)$ is prime, and $|\mathcal{G}(P-x)| \leq |\mathcal{G}(P)| - 1$;

3. $|X(x)| \geq 2$, $\mathcal{G}(P-x) = (\mathcal{G}(P) \setminus \{X(x)\}) \cup \{X(x) \setminus \{x\}\}$, $(P-x)/\mathcal{G}(P-x)$ is prime, and (2) holds.

We conclude as in Lemma 2.1. $\square$

**Lemma 2.3.** Let $P$ be a partial order such that $v(P) \geq 2$. Suppose that $\overline{\mathrm{Comp}(P)}$ is disconnected. For $v, w \in V(P)$, if $v \cong_P w$ and $\max(|X(v)|, |X(w)|) \geq 2$, then $X(v) = X(w)$.

*Proof.* By Theorem 1.2, $\mathcal{G}(P) = \mathcal{C}(\overline{\mathrm{Comp}(P)})$ and $P/\mathcal{G}(P)$ is a total order. Let $x \in V(P)$. Clearly, for every $X \in \mathcal{G}(P)$ such that $x \notin X$, $\overline{\mathrm{Comp}(P)}[X]$ is a component of $\overline{\mathrm{Comp}(P-x)}$. Hence, one of the following cases holds

1. $X(x) = \{x\}$, $\overline{\mathrm{Comp}(P-x)}$ is connected, and $\mathcal{G}(P) = \{V(P) \setminus \{x\}, \{x\}\}$;

2. $X(x) = \{x\}$, $\overline{\mathrm{Comp}(P-x)}$ is disconnected, and $\mathcal{G}(P) = \mathcal{G}(P-x) \cup \{\{x\}\}$;
3. $|X(x)| \ge 2$, $\overline{\text{Comp}(P-x)}$ is disconnected, and

$$ \mathcal{G}(P-x) = (\mathcal{G}(P) \setminus \{X(x)\}) \cup \mathcal{C}(\overline{\text{Comp}(P[X(x)] - x)}). $$

Now, consider $v, w \in V(P)$ such that $v \cong_P w$. One of the three cases above holds for both $v$ and $w$. In the first two cases, $X(v) = \{v\}$ and $X(w) = \{w\}$, so $P[X(v)] \cong P[X(w)]$. Therefore, suppose that the third case holds for $v$ and $w$. We denote the blocks of $\mathcal{G}(P)$ by $X_0, \dots, X_n$, where $n \ge 1$, in such a way that

$$ P/\mathcal{G}(P) = X_0 < \dots < X_n. $$

We can assume that there exist $i \le j \in \{0, \dots, n\}$ such that $X(v) = X_i$ and $X(w) = X_j$. We have

$$ (P - v)/\mathcal{G}(P - v) = X_0 < \dots < X_{i-1} < Y < \dots, $$

where $Y \in \mathcal{C}(\overline{\text{Comp}(P[X_i] - v)})$. If $i < j$, we obtain

$$ (P - w)/\mathcal{G}(P - w) = X_0 < \dots < X_{i-1} < X_i < \dots. $$

It follows that $i = j$, that is, $X(v) = X(w)$. $\square$

**Definition and notation 2.4.** Let $P$ be a partial order. Consider $v \in V(P)$. The *filter* of $v$ in $P$ is the set $\uparrow_P(v) = \{w \in V(P) : v \le_P w\}$. Set $f_P(v) = |\uparrow_P(v)|$. The *ideal* of $v$ in $P$ is the set $\downarrow_P(v) = \{w \in V(P) : w \le_P v\}$. Set $i_P(v) = |\downarrow_P(v)|$. The *rank* $\text{rk}_P(v)$ of $v$ in $P$ is defined by

$$ \text{rk}_P(v) = \text{ht}(P[\downarrow_P(v)]). $$

**Proposition 2.5.** Let $P$ be a partial order. Consider distinct vertices $u, v, w$ of $P$ such that $u <_P w$, $v <_P w$, and $u \|_P v$, so $P[\{u, v, w\}] \cong \Lambda$. If $f_P(v) \ge f_P(u)$, then $u \not\cong_P w$.

*Proof.* We prove that

$$ |\{z \in V(P - u) : f_{P-u}(z) \ge f_P(v)\}| \ge |\{z \in V(P - w) : f_{P-w}(z) \ge f_P(v)\}| + 1, \quad (3) $$

which implies $u \not\cong_P w$.

Consider the sets

$$ \left\{ \begin{array}{l} X = \{x \in (V(P) \setminus \downarrow_P(w)) : f_P(x) \ge f_P(v)\} \\ \text{and} \\ Y = \{y \in \downarrow_P(w) : f_P(y) > f_P(v)\}. \end{array} \right. $$

We verify that

$$ \{z \in V(P - w) : f_{P-w}(z) \ge f_P(v)\} = X \cup Y. \quad (4) $$
Let $x \in X$. Since $x \notin \downarrow_P(w)$, we have $\uparrow_P(x) = \uparrow_{P-w}(x)$. Thus, $f_P(x) = f_{P-w}(x)$. Since $x \in X$, we have $f_P(x) \ge f_P(v)$, and hence $f_{P-w}(x) \ge f_P(v)$. Let $y \in Y$. Since $y \in \downarrow_P(w)$ and $f_P(y) > f_P(v)$, we obtain $y \ne w$. It follows that $\uparrow_P(y) = \uparrow_{P-w}(y) \cup \{w\}$. Thus, $f_P(y) = f_{P-w}(y) + 1$. Since $y \in Y$, we have $f_P(y) > f_P(v)$, and hence $f_{P-w}(y) \ge f_P(v)$. Consequently, we have

$$ (X \cup Y) \subseteq \{z \in V(P - w) : f_{P-w}(z) \ge f_P(v)\}. $$

Conversely, consider $z \in V(P - w)$ such that $f_{P-w}(z) \ge f_P(v)$. First, suppose that $z \notin \downarrow_P(w)$. As previously seen, we have $\uparrow_P(z) = \uparrow_{P-w}(z)$. Therefore, we have $f_P(z) \ge f_P(v)$, and hence $z \in X$. Second, suppose that $z \in \downarrow_P(w)$. We obtain $z \in (\downarrow_P(w) \setminus \{w\})$. As previously seen, we have $\uparrow_P(z) = \uparrow_{P-w}(z) \cup \{w\}$, so $f_P(z) = f_{P-w}(z) + 1$. Thus, $f_P(z) > f_P(v)$, and hence $z \in Y$. It follows that (4) holds.

Moreover, we verify that

$$ X \cup Y \cup \{v\} \subseteq \{z \in V(P - u) : f_{P-u}(z) \ge f_P(v)\}. \qquad (5) $$

Since $u \|_P v$, we have $\uparrow_P(v) = \uparrow_{P-u}(v)$. Thus, we have $f_P(v) = f_{P-u}(v)$. Since $v \ne u$, $v \in \{z \in V(P - u) : f_{P-u}(z) \ge f_P(v)\}$. Let $x \in X$. Since $x \notin \downarrow_P(w)$ and $u <_P w$, we have $x \notin \downarrow_P(u)$. We obtain $\uparrow_P(x) = \uparrow_{P-u}(x)$, so $f_P(x) = f_{P-u}(x)$. Since $x \in X$, we have $f_P(x) \ge f_P(v)$, and hence $f_{P-u}(x) \ge f_P(v)$. Let $y \in Y$. Since $f_P(y) > f_P(v)$ and $f_P(v) \ge f_P(u)$, we obtain $y \ne u$. Since $y \in \downarrow_P(w)$, we have $(\uparrow_P(y) \setminus \{u\}) \subseteq \uparrow_{P-u}(y)$. Thus, we have $f_{P-u}(y) \ge f_P(y) - 1$, and hence $f_{P-u}(y) \ge f_P(v)$. It follows that (5) holds.

Since $X$, $Y$, and $\{v\}$ are pairwise disjoint, it follows from (4) and (5) that (3) holds. Consequently, $u \not\cong_P w$. $\square$

## 3 Schröder's results

We use the following two important results due to Schröder [12] (see Theorems 2.4 and 4.5).

**Theorem 3.1.** Let $P$ be a connected partial order. Suppose that there exists $v, w \in V(P)$ such that $v \cong_P w$ and $rk_P(v) < rk_P(w)$. If $(v, w) \notin (\min(P) \times \max(P))$, then there exists a nontrivial module $M$ of $P$ such that $v \in M$, $P[M]$ is connected, and there exists $w' \in M$ satisfying

* $(v, w') \in (\min(P[M]) \times \max(P[M]))$;

* $v \cong_{P[M]} w'$.

**Theorem 3.2.** Let $P$ be a connected partial order. Suppose that $P$ is not a total order. If there exist $(v, w) \in (\min(P) \times \max(P))$ such that $v \cong_P w$, then for every $x \in V(P) \setminus \{v, w\}$, $x \not\cong_P v$.
# 4 Monomorphic partial orders

We recall the following claim which is a direct consequence of [7, Lemma 5].

**Claim 4.1.** Let $P$ be a partial order into which $\bigwedge$ and $\bigvee$ do not embed. If $\text{Comp}(P)$ is connected, then $P$ is a total order.

*Proof of Theorem 1.13.* To begin, a total order is obviously monomorphic. Furthermore, suppose that $P/\mathcal{G}(P)$ is discrete and there exists $k \ge 1$ such that for every $X \in \mathcal{G}(P)$, $P[X] \simeq T_k$. Clearly, $P$ is monomorphic.

Conversely, suppose that $P$ is monomorphic. By Proposition 2.5, $\bigwedge$ does not embed into $P$. Since the dual $P^*$ of $P$ is monomorphic as well, $\bigwedge^*$ does not embed into $P^*$. Hence, $\bigvee$ does not embed into $P$. By Claim 4.1, $P$ is a total order if $\text{Comp}(P)$ is connected. Hence, suppose that $\text{Comp}(P)$ is disconnected. By Theorem 1.2, $\mathcal{G}(P) = \mathcal{C}(\text{Comp}(P))$ and $P/\mathcal{G}(P)$ is discrete. Consider $X \in \mathcal{G}(P)$. By Claim 4.1, $P[X]$ is a total order because $\text{Comp}(P[X])$ is connected and $P[X]$ contains neither $\bigwedge$ nor $\bigvee$. Since $P$ is monomorphic, there exists $k \ge 1$ such that for every $X \in \mathcal{G}(P)$, $P[X] \simeq T_k$. □

**Remark 4.2.** It follows from Theorem 1.13 that there does not exist a finite partial order which is both prime and monomorphic. Now, consider the partial order $\le_P$ defined on $\mathbb{Z}$ as follows. Given $m, n \in \mathbb{Z}$, $m \le_P n$ if there exist $k, l \ge 0$ such that $n - m = 3k + 4l$. It is not difficult to verify that $P$ is prime. Furthermore, the permutation of $\mathbb{Z}$, defined by $n \mapsto n + 1$, is an automorphism of $P$. It follows that $P$ is vertex-transive (without being discrete). In particular, we obtain that $P$ is monomorphic as well. Two problems follow.

**Problem 4.3.** Do there exist infinite partial orders that are monomorphic and prime, but not vertex-transitive? (Observe that the usual order on $\mathbb{N}$ is monomorphic, but neither prime nor vertex-transitive.)

**Problem 4.4.** Characterize the infinite monomorphic partial orders.

The next result is an immediate consequence of Theorem 1.13, Lemma 1.6, and Proposition 1.7. It can be proved directly from the characterization provided in Theorem 1.13 as well.

**Corollary 4.5.** Given a partial order $P$ such that $v(P) \ge 3$, if $P$ is monomorphic, then $P$ is reconstructible.

# 5 Bimorphic partial orders

*Proof of Theorem 1.14.* Let $P$ be a partial order such that $\text{Comp}(P)$ is disconnected. Clearly, if Assertion (A1) or Assertion (A2) holds, then $P$ is bimorphic. Conversely, suppose that $P$ is bimorphic. Denote by $C_1$ and $C_2$ the equivalence classes of $\cong_P$. For $i = 1$ or 2, set

$$ \mathcal{G}_i(P) = \{X \in \mathcal{G}(P) : X \cap C_i \neq \emptyset\}. $$
Given $i = 1$ or $2$, it follows from Lemma 2.1 that there exists a partial order $Q_i$ such that $P[X] \simeq Q_i$ for every $X \in \mathcal{G}_i(P)$. We distinguish the following two cases.

1. Suppose that $\mathcal{G}_1(P) \cap \mathcal{G}_2(P) \neq \emptyset$. Hence, we obtain $Q_1 \simeq Q_2$. Since $P$ is bimorphic, $Q_1$ is bimorphic too. Thus, Assertion (A2) holds.

2. Suppose that $\mathcal{G}_1(P) \cap \mathcal{G}_2(P) = \emptyset$. We verify that $Q_1$ is a total order. This is clear when $v(Q_1) = 1$. Hence, suppose that $v(Q_1) \ge 2$. Let $X \in \mathcal{G}_1(P)$. For $v, w \in X$, it follows from Lemma 2.1 that $P[X - v] \simeq P[X - w]$. Therefore, $P[X]$ and hence $Q_1$ are monomorphic. Since $\mathrm{Comp}(Q_1)$ is connected, it follows from Theorem 1.13 that $Q_1$ is a total order. Similarly, $Q_2$ is a total order. Since $P$ is not monomorphic, it follows from Theorem 1.13 that $v(Q_1) \neq v(Q_2)$. Consequently, Assertion (A1) holds. $\square$

*Proof of Theorem 1.15.* Consider a partial order $P$ such that

$$v(P) \ge 3 \text{ and } \overline{\mathrm{Comp}(P)} \text{ is disconnected.}$$

Clearly, if Assertion (B1) or Assertion (B2) holds, then $P$ is bimorphic. Conversely, suppose that $P$ is bimorphic. We denote the blocks of $\mathcal{G}(P)$ by $X_0, \dots, X_n$, where $n \ge 1$, in such a way that

$$P/\mathcal{G}(P) = X_0 < \dots < X_n.$$

Set

$$\mathcal{G}_{\ge 2}(P) = \{X \in \mathcal{G}(P) : |X| \ge 2\}.$$

It follows from Lemma 2.3 that $|\mathcal{G}_{\ge 2}(P)| \le 2$. Since $P$ is not monomorphic, $P$ is not a total order, so $\mathcal{G}_{\ge 2}(P) \neq \emptyset$. Therefore, we have $|\mathcal{G}_{\ge 2}(P)| = 1$ or $2$. We distinguish the following two cases.

1. Suppose that $|\mathcal{G}_{\ge 2}(P)| = 2$. It follows from Lemma 2.3 that $\mathcal{G}(P) = \mathcal{G}_{\ge 2}(P)$. Clearly, Assertion (B1) holds.

2. Suppose that $|\mathcal{G}_{\ge 2}(P)| = 1$. Denote by $X$ the unique element of $\mathcal{G}_{\ge 2}(P)$. For a contradiction, suppose that $n \ge 2$ and $X = X_i$, where $i \in \{1, \dots, n-1\}$. Set

$$Y = \bigcup_{0 \le j \le i-1} X_j \quad \text{and} \quad Z = \bigcup_{i+1 \le j \le n} X_j.$$

Let $x \in X$, $y \in Y$, and $z \in Z$. It follows from Lemma 2.3 that $x \not\cong_P y$ and $x \not\cong_P z$. Furthermore, it is not difficult to verify that $y \not\cong_P z$, which contradicts the fact that $P$ is bimorphic. Consequently, we obtain $X = X_0$ or $X = X_n$, that is, Assertion (B2) holds. $\square$

*Proof of Theorem 1.16.* Consider a prime partial order $P$. Clearly, if $\mathrm{ht}(P) = 1$, $P$ is $\min(P)$-transitive, and $P$ is $\max(P)$-transitive, then $\cong_P$ has two equivalence classes, namely $\min(P)$ and $\max(P)$. Conversely, suppose that $P$ is bimorphic.
For a contradiction, suppose that there exist $(v, w) \in (\min(P) \times \max(P))$ such that $v \cong_P w$. It follows from Theorem 3.2 that $\cong_P$ has two equivalence classes, namely $\{v, w\}$ and $V(P) \setminus \{v, w\}$. Since $P$ is prime, we have $\min(P) \neq \{v\}$ and $\max(P) \neq \{w\}$. Consider $v' \in \min(P) \setminus \{v\}$ and $w' \in \max(P) \setminus \{w\}$. Since $v' \cong_P w'$, it follows from Theorem 3.2 that $\cong_P$ has two equivalence classes, namely $\{v', w'\}$ and $V(P) \setminus \{v', w'\}$. It follows that $P \cong \mathbb{W}$, which is impossible because $\cong_P$ admits three equivalence classes. Consequently, for any $v \in \min(P)$ and $w \in \max(P)$, we have

$$v \not\cong_P w. \qquad (6)$$

Denote by $C_1$ and $C_2$ the equivalence classes of $P$. By exchanging $C_1$ and $C_2$ if necessary, it follows from (6) that $\min(P) \subseteq C_1$ and $\max(P) \subseteq C_2$. Since $P$ is prime and bimorphic, it follows from Theorem 3.1 that

$$V(P) = \min(P) \cup \max(P),$$

and hence $\min(P) = C_1$ and $\max(P) = C_2$. In particular, we obtain $\min(P) = 1$. Let $w, w' \in \max(P)$. Since $P - w \cong_P P - w'$, we have $i_p(w) = i_p(w')$. Now, let $v, v' \in \min(P)$ and consider an isomorphism $\varphi$ from $P - v$ onto $P - v'$. Since $i_p(w) = i_p(w')$ for any $w, w' \in \max(P)$, we obtain $\varphi(\uparrow_P(v) \setminus \{v\}) = \uparrow_P(v') \setminus \{v'\}$. Consequently, the extension of $\varphi$ by $v \mapsto v'$ is an automorphism of $P$. It follows that $P$ is $\min(P)$-transitive. Similarly, $P$ is $\max(P)$-transitive. $\square$

**Proof of Theorem 1.17.** Consider a partial order $P$ such that

$\mathrm{Comp}(P)$ and $\overline{\mathrm{Comp}(P)}$ are connected.

Clearly, if Statements (S1), (S2), and (S3) hold, then $P$ is bimorphic. Conversely, suppose that $P$ is bimorphic. Denote by $C_1$ and $C_2$ the equivalence classes of $\cong_P$. For $i = 1$ or 2, set

$$\mathcal{G}^i(P) = \{X \in \mathcal{G}(P) : X \cap C_i \neq \emptyset\}.$$

Moreover, set

$$\mathcal{G}_{\ge 2}(P) = \{X \in \mathcal{G}(P) : |X| \ge 2\}.$$

Furthermore, by Theorem 1.16, we can assume that $P$ is decomposable. It follows from Theorem 1.2 that $\mathcal{G}_{\ge 2}(P) \neq \emptyset$. For instance, suppose that

$$\mathcal{G}^1(P) \cap \mathcal{G}_{\ge 2}(P) \neq \emptyset.$$

By Lemma 2.2, we have

$$\mathcal{G}^1(P) \subseteq \mathcal{G}_{\ge 2}(P).$$

Let $X, Y \in \mathcal{G}^1(P)$. Given $x \in X$ and $y \in Y$ such that $x \cong_P y$, consider an isomorphism $\varphi$ from $P - x$ onto $P - y$. Since $|X| \ge 2$, we have $\mathcal{G}(P - x) = (\mathcal{G}(P) \setminus \{X\}) \cup \{X \setminus \{x\}\}$ and $(P - x)/\mathcal{G}(P - x)$ is prime. The analogue holds for $P - y$. It follows that the bijection

$$\varphi: \begin{array}{ccc} \mathcal{G}(P - x) & \longrightarrow & \mathcal{G}(P - y) \\ Z & \longmapsto & \varphi(Z) \end{array}$$
is an isomorphism from $(P-x)/\mathscr{G}(P-x)$ onto $(P-y)/\mathscr{G}(P-y)$. Furthermore, since $\varphi$ is an isomorphism from $P-x$ onto $P-y$, there exists $k \ge 1$ such that $\varphi^k(y) = x$. It follows that

$$ (\varphi)^k(Y) = X. $$

Clearly, the bijection

$$ \varphi_x : \mathscr{G}(P) \longrightarrow \mathscr{G}(P-x) \\ Z \longmapsto Z \setminus \{x\} $$

is an isomorphism from $P/\mathscr{G}(P)$ onto $(P-x)/\mathscr{G}(P-x)$. We define the isomorphism $\varphi_y$ from $P/\mathscr{G}(P)$ onto $(P-y)/\mathscr{G}(P-y)$ in an analogous way. We obtain that

$$ ((\varphi_y)^{-1} \circ \varphi \circ \varphi_x)^k(Y) = X. $$

Since $(\varphi_y)^{-1} \circ \varphi \circ \varphi_x$ is an automorphism of $P/\mathscr{G}(P)$, we obtain that $P/\mathscr{G}(P)$ is $\mathscr{G}^1(P)$-transitive. By exchanging $P$ and $P^*$ if necessary, we can assume that

$$ \mathscr{G}^1(P) \cap \min(P/\mathscr{G}(P)) \neq \emptyset. $$

Since $P/\mathscr{G}(P)$ is $\mathscr{G}^1(P)$-transitive, we obtain

$$ \mathscr{G}^1(P) \subseteq \min(P/\mathscr{G}(P)). $$

To conclude, we distinguish the following two cases.

1. Suppose that $\mathscr{G}^2(P) \cap \mathscr{G}_{\ge 2}(P) \neq \emptyset$. As for $\mathscr{G}^1(P)$, we obtain $\mathscr{G}^2(P) \subseteq \mathscr{G}_{\ge 2}(P)$ and $P/\mathscr{G}(P)$ is $\mathscr{G}^2(P)$-transitive. Since $\mathscr{G}^1(P) \subseteq \min(P/\mathscr{G}(P))$, we obtain $\mathscr{G}^2(P) \cap \max(P/\mathscr{G}(P)) \neq \emptyset$. Since $P/\mathscr{G}(P)$ is $\mathscr{G}^2(P)$-transitive, we obtain

$$ \mathscr{G}^2(P) = \max(P/\mathscr{G}(P)). $$

It follows that $\mathscr{G}^1(P) = \min(P/\mathscr{G}(P))$ and for $i = 1$ or $2$,

$$ C_i = \bigcup_{X \in \mathscr{G}^i(P)} X. $$

It follows from Lemma 2.2 that there exists a monomorphic partial order $Q_1$ such that for every $X \in \min(P/\mathscr{G}(P))$, $P[X] \simeq Q_1$. Hence, Statement (S2) holds. Similarly, Statement (S3) holds. Furthermore, since $P/\mathscr{G}(P)$ is $\mathscr{G}^1(P)$-transitive and $\mathscr{G}^2(P)$-transitive, $P/\mathscr{G}(P)$ is monomorphic or bimorphic. Since $P/\mathscr{G}(P)$ is prime, it follows from Theorem 1.13 that $P/\mathscr{G}(P)$ is not monomorphic. Hence, Statement (S1) holds.

2. Suppose that $|X| = 1$ for every $X \in \mathscr{G}^2(P)$. Thus, we have

$$ C_2 = \bigcup_{X \in \mathscr{G}^2(P)} X. $$

It follows that

$$ C_1 = \bigcup_{X \in \mathscr{G}^1(P)} X. $$
Since $\mathcal{G}^1(P) \subseteq \min(P/\mathcal{G}(P))$, we obtain $\max(P/\mathcal{G}(P)) \subseteq \mathcal{G}^2(P)$.

For a contradiction, suppose that $\min(P/\mathcal{G}(P)) \setminus \mathcal{G}^1(P) \neq \emptyset$. There exist $v, w \in C_2$ such that $\{v\} \in \min(P/\mathcal{G}(P))$ and $\{w\} \in \max(P/\mathcal{G}(P))$. We have $v \in \min(P)$ and $w \in \max(P)$. It follows from Theorem 3.2 that $(V(P) \setminus \{v, w\}) \subseteq C_1$. Since $\max(P/\mathcal{G}(P)) \subseteq \mathcal{G}^2(P)$, we obtain $\max(P/\mathcal{G}(P)) = \{\{w\}\}$, which contradicts the fact that $P/\mathcal{G}(P)$ is prime. Consequently, we have

$$ \min(P/\mathcal{G}(P)) = \mathcal{G}^1(P). $$

It follows that $P/\mathcal{G}(P)$ is $\min(P/\mathcal{G}(P))$-transitive.

For a contradiction, suppose that $\min(P/\mathcal{G}(P)) \cup \max(P/\mathcal{G}(P)) \subsetneq \mathcal{G}(P)$. There exist $v, w \in V(P)$ such that

$$ \{v\} \in (\mathcal{G}(P) \setminus (\min(P/\mathcal{G}(P)) \cup \max(P/\mathcal{G}(P)))) $$

$\{w\} \in \max(P/\mathcal{G}(P))$, and $\{v\} <_{P/\mathcal{G}(P)} \{w\}$. We have $v, w \in C_2$ and $w \in \max(P)$. Since $\{v\} \notin \min(P/\mathcal{G}(P))$, there exists $X \in \min(P/\mathcal{G}(P))$ such that $X <_{P/\mathcal{G}(P)} \{v\}$. Therefore, $v \notin \min(P)$. It follows from Theorem 3.1 that there exists a nontrivial module $M$ of $P$ such that $v \in M$, which is impossible because $\{v\} \in \mathcal{G}(P)$ and $P/\mathcal{G}(P)$ is prime. Consequently, we obtain

$$ \min(P/\mathcal{G}(P)) \cup \max(P/\mathcal{G}(P)) = \mathcal{G}(P), $$

and hence

$$ \mathcal{G}^2(P) = \max(P/\mathcal{G}(P)). $$

It remains to prove that $P/\mathcal{G}(P)$ is bimorphic. Let

$$ \{v\}, \{w\} \in \max(P/\mathcal{G}(P)). $$

We have $v, w \in C_2$. Hence, there exists an isomorphism $\varphi$ from $P - v$ onto $P - w$. Clearly, $\mathcal{G}(P) \setminus \{\{v\}\}$ is a modular partition of $P - v$ and $\mathcal{G}(P) \setminus \{\{w\}\}$ is a modular partition of $P - w$. We verify that

$$ \text{for each } X \in (\mathcal{G}(P) \setminus \{\{v\}\}), \varphi(X) \in (\mathcal{G}(P) \setminus \{\{w\}\}). \quad (7) $$

Indeed, since $P/\mathcal{G}(P)$ is prime and $\min(P/\mathcal{G}(P))$-transitive, there exists $f \geq 3$ such that

$$ \text{for every } X \in \min(P/\mathcal{G}(P)), f_{P/\mathcal{G}(P)}(X) = f. \quad (8) $$

It follows from (8) that $\max(P - v) = \max(P) \setminus \{v\}$. Similarly, $\max(P - w) = \max(P) \setminus \{w\}$. We obtain $\varphi(\max(P) \setminus \{v\}) = \max(P) \setminus \{w\}$. Consequently, (7) holds for $X \in (\max(P/\mathcal{G}(P)) \setminus \{\{v\}\})$. Now, let $X \in \min(P/\mathcal{G}(P))$. Set

$$ \mathcal{M} = \{Y \in \min(P/\mathcal{G}(P)) : Y \cap \varphi(X) \neq \emptyset\}. $$

Since $\varphi(X)$ is a module of $P - w$, we obtain that the union of the elements of $\mathcal{M}$ is a module of $P - w$. Therefore, $\mathcal{M}$ is a module of $(P/\mathcal{G}(P)) - \{w\}$. It follows
from (8) that $\mathcal{M}$ is a module of $P/\mathcal{G}(P)$. Since $P/\mathcal{G}(P)$ is prime, we have $|\mathcal{M}| = 1$, that is $\varphi(X) \in \min(P/\mathcal{G}(P))$. Consequently, (7) holds. We obtain $(P/\mathcal{G}(P)) - \{v\} \simeq (P/\mathcal{G}(P)) - \{w\}$. It follows that $P/\mathcal{G}(P)$ is monomorphic or bimorphic. Since $P/\mathcal{G}(P)$ is prime, it follows from Theorem 1.13 that $P/\mathcal{G}(P)$ is bimorphic. $\square$

**Proposition 5.1.** *Given a partial order *P* such that *v*(*P*) ≥ 3, if *P* is bimorphic, then *P* is reconstructible.*

*Proof.* If $P/\mathcal{G}(P)$ is discrete, then it suffices to apply Lemma 1.6. Furthermore, if $P/\mathcal{G}(P)$ is a total order, then it suffices to apply Proposition 1.7. By applying Theorem 1.2, we can suppose that $P/\mathcal{G}(P)$ is prime.

To begin, suppose that $P$ is decomposable. By Theorem 1.17, the following statements hold

• $P/\mathcal{G}(P)$ is prime and bimorphic;

• there exists a monomorphic partial order $P_1$ such that for every $X \in \min(P/\mathcal{G}(P))$, $P[X] \simeq P_1$;

• there exists a monomorphic partial order $P_2$ such that for every $X \in \max(P/\mathcal{G}(P))$, $P[X] \simeq P_2$.

Since $P$ is decomposable, $v(P_1) \ge 2$ or $v(P_2) \ge 2$. For instance, assume that $v(P_1) \ge 2$. By Theorem 1.16 applied to $P/\mathcal{G}(P)$, $P/\mathcal{G}(P)$ is $\min(P/\mathcal{G}(P))$-transitive. Hence, $\min(P/\mathcal{G}(P))$ is an orbit of $P/\mathcal{G}(P)$ and it suffices to apply Proposition 1.8.

Lastly, suppose that $P$ is prime. Let $Q$ be a partial order hypomorphic to $P$. Clearly, $Q$ is bimorphic too. Moreover, it follows from Remark 1.10 that $Q$ is prime too. By Theorem 1.16, we have $ht(P) = 1$, $P$ is $\min(P)$-transitive, and $P$ is $\max(P)$-transitive. The same holds for $Q$.

Let $v \in \min(P)$. We have $\max(P - v) = \max(P)$. Furthermore, since $P$ is prime and $\max(P)$-transitive, we have $i_P(w) \ge 3$ for every $w \in \max(P)$. It follows that $\min(P - v) = \min(P) \setminus \{v\}$. Analogously, for each $v \in \max(Q)$, $\min(Q - v) = \min(Q)$ and $\max(Q - v) = \max(Q) \setminus \{v\}$. Consequently, we obtain $\min(P) = \min(Q)$ and $\max(P) = \max(Q)$. Since $P$ is $\min(P)$-transitive and $Q$ is $\min(Q)$-transitive, it follows from Corollary 1.5 that $f_P(v) = f_Q(v)$ for every $v \in \min(P)$. Given $w \in \max(P)$, it follows that the extension of an isomorphism from $P - w$ onto $Q - w$ by $w \mapsto w$ is an isomorphism from $P$ onto $Q$. $\square$

# 6 Epilogue: *k*-morphic partial orders

Given $k \ge 1$, a partial order $P$ is *k*-morphic if $\cong_P$ has exactly $k$ equivalence classes. As in the proof of Theorem 1.16, the next result follows from Theorems 3.1 and 3.2.

**Fact 6.1.** Let $k \ge 2$. Given a prime partial order $P$ such that $ht(P) = k - 1$, if $P$ is $k$-morphic, then the following statements hold
(T1) for each $i \in \{0, \dots, k-1\}$, $\{v \in V(P) : \mathrm{rk}_P(v) = i\}$ is an equivalence class of $\cong_P$;

(T2) for each $i \in \{0, \dots, k-1\}$, $\{v \in V(P) : \mathrm{rk}_{P^*}(v) = i\}$ is an equivalence class of $\cong_P$;

(T3) for each $v \in V(P)$, $\mathrm{rk}_P(v) + \mathrm{rk}_{P^*}(v) = \mathrm{ht}(P)$.

*Proof.* Statement (T1) follows from Theorems 3.1 and 3.2 as in the proof of Theorem 1.16. Since $\cong_{P^*}$ and $\cong_P$ coincide, Statement (T2) is the analogue of Statement (T1) for $P^*$. Finally, Statement (T3) follows from Statements (T1) and (T2) by considering $W \in \tau(P)$ such that $\mathrm{ht}(P) = |W| - 1$ (see Definition 1.12). $\square$

Given Fact 6.1, we conjecture the following

**Conjecture 6.2.** Let $k \ge 2$. Given a prime partial order $P$ such that $\mathrm{ht}(P) = k-1$, $P$ is $k$-morphic if and only if the following statement holds

(U1) for every $0 \le l \le k-1$, $P$ is $\{v \in V(P) : \mathrm{rk}_P(v) = l\}$-transitive.

**Remark 6.3.** Let $k \ge 2$. Consider a prime partial order $P$ such that $\mathrm{ht}(P) = k-1$. If $P$ satisfies Statement (U1), then $P$ satisfies Statement (T3).

## Acknowledgements

The authors thank two referees for their constructive suggestions that allowed for notable improvements to the manuscript.

## References

[1] R. Brignall, N. Georgiou and R. J. Waters, Modular decomposition and the reconstruction conjecture, *J. Comb.* **3** (2012), 123–134.

[2] S. K. Das, On the structure of finite $T_0+T_5$ spaces, *Canad. J. Math.* **25** (1973), 1148–1158.

[3] R. Fraïssé, “Theory of relations”, Revised edition, Appendix by Norbert Sauer; Studies in Logic and the Foundations of Mathematics, 145, North-Holland Publishing Co., Amsterdam, 2000, ii+451 pp.

[4] T. Gallai, Transitiv orientierbare Graphen, *Acta Math. Acad. Sci. Hungar.* **18** (1967), 25–66.

[5] F. Harary, On the reconstruction of a graph from its collection of subgraphs, in: “Theory of Graphs and its Applications”, (Ed.: M. Fielder), Prague, 1964, pp. 47–52.
[6] P. Ille, Recognition problem in reconstruction for decomposable relations, in: “Finite and Infinite Combinatorics in Sets and Logic”, (Eds.: B. Sands, N. Sauer and R. Woodrow), Kluwer Academic Publishers, 1993, pp. 189–198.

[7] P. Ille, J.-X. Rampon, Reconstruction of posets with the same comparability graph, *J. Combin. Theory Series B* 74 (1998), 368–377.

[8] P. Ille and J.-X. Rampon, A counting of the minimal realizations of the posets of dimension two, *Ars Combin.* 78 (2006), 157–165.

[9] P.J. Kelly, A congruence theorem for trees, *Pacific J. Math.* 7 (1957), 961–968.

[10] D. Kratsch and J.-X. Rampon, Towards the reconstruction of posets, *Order* 11 (1994), 317–341.

[11] F. Maffray and M. Preissmann, A translation of Tibor Gallai's Paper: Transitiv orientierbare Graphen, in: “Perfect Graphs”, (Eds.: J.L. Ramirez-Alfonsin and B.A. Reed), Wiley, New York, 2001, pp. 25–66.

[12] B. S. W. Schröder, Pseudo-similar points in ordered sets, *Discrete Math.* 310 (2010), 2815–2823.

[13] B. S. W. Schröder, Set recognition of decomposable graphs and steps towards their reconstruction, *Abh. Math. Semin. Univ. Hambg.* 92 (2022), 1–25.

[14] W. T. Trotter, Dimension of the crown $S_n^k$, *Discrete Math.* 8 (1974), 85–103.

(Received 30 May 2022; revised 9 Mar 2024, 4 May 2024)