Going from partial order to a linear one is easy, we just do topological ordering.
I am wondering about the other way around. In particular: let $>$ be a linear order over a set $A$. Let $\Gamma$ be the set of all possible partial orders over $A$ agreeing with $>$. I have two questions:
- What is the largest possible size of partial order $>_p$. The size of $>_p$ is the number of pairs $a>_p b$.
- Any way to construct such a partial order?
I was thinking it should be $n-1$ where $|A|=n$. However because of the transitive relation I am not quite sure.
The only partial order on $A$ that actually agrees with $>$ is $>$ itself; I assume that you’re really talking about partial orders that don’t disagree with $>$, i.e., partial orders that are subsets of $>$. The largest is of course $>$ itself, but it appears that you further want to limit yourself to partial orders that are not linear.
All linearly ordered sets of cardinality $n$ are order-isomorphic, and the only partial order on a one-element set is linear, so so we might as well let $A=[n]=\{1,\ldots,n\}$ with the usual order and $n\ge 2$. For $k,\ell\in[n]$ let $k\preceq\ell$ iff $k\le\ell$ and $\langle k,\ell\rangle\ne\langle n-1,n\rangle$. The Hasse diagram of the resulting partial order looks like this:
The original linear order has $\sum_{k=1}^n=\frac12n(n+1)$ pairs, and we’ve removed only one of these pairs, $\langle n-1,n\rangle$, so $\preceq$ has
$$\frac12n(n+1)-1=\frac{n^2+n-2}2=\frac12(n-1)(n+2)$$
pairs.