Number of partial orders such that a given function is monotone (order homomorphism)?

36 Views Asked by At

Given a set $X$, a poset $(Y, \preceq)$, and an arbitrary function $f: X \to Y$, how many partial orders $\le$ can one construct on $X$ such that $f$ becomes an order homomorphism $(X, \le) \to (Y, \preceq)$?

I am looking for a specific enough description of the set of all such partial orders, such that, in the case that $X$ and $Y$ were finite, one would (hypothetically) be able to use it to count the total number of such partial orders.

Alternatively, are there any references describing this problem and its solution? Are there any additional constraints we can add such that this problem admits a "universal solution" (i.e., one with a universal mapping property)?

Partial progress: For every $y \in Y$, define the "fiber" $F_y \subseteq X$ to be $f^{-1}(\{y\})$. We know that, if $x_1 \le x_2$, then necessarily $f(x_1) \preceq f(x_2)$, and so we might try to reduce the problem to determining

  1. what subsets of $F_y \times F_y \subseteq X \times X$ are allowed for all $y \in Y$, and

  2. what subsets of $F_{y_1} \times F_{y_2} \subseteq X \times X$ are allowed for all $y_1, y_2 \in Y$ such that $y_1 \not=y_2$.

If $y_1 \not\preceq y_2$, then we know based on the above that the only allowed subset of $F_{y_1} \times F_{y_2}$ is the empty set $\emptyset$. On the other hand, for any $y \in Y$, we know that any partial order on $F_{y}$ will be an allowed subset of $F_y \times F_y$.

So the only difficulty seems to be determining which subsets of $F_{y_1} \times F_{y_2}$ are allowed when $y_1 \preceq y_2$ and $y_1 \not= y_2$ ($y_1 \prec y_2$).

Given any partial order on $X$, including those satisfying the constraint, it will restrict to a partial order on $F_y$ for every $y \in Y$. So it seems like we can reduce the problem to: given partial orders on every $F_y$, how many ways are there to choose subsets of $F_{y_1} \times F_{y_2}$ (when $y_1 \prec y_2$) such that the resulting relation on $X$ is a partial order?

Can we choose arbitrary subsets of these $F_{y_1} \times F_{y_2}$ (when $y_1 \prec y_2$) and then take the transitive closure and be guaranteed that the result is a partial order?

I think if we take arbitrary subsets we're guaranteed to maintain antisymmetry (although obviously not transitivity), so the question is about whether we could ever lose antisymmetry upon taking the transitive closure.

(And if so, then how to restrict from arbitrary choices so as to avoid the possibility of losing antisymmetry upon taking the transitive closure?).

Note: In the case that $(Y, \preceq)$ is a total ordered set, I read in one reference that the partial orders satisfying this constraint on $X$ would be called "stratified partial orders". So possibly references on counting stratified partial orders would be relevant.