Number of partial orders that contain a specific relation?

Question

Let be $A=\{1,2,3,4\}$

Find the number of partial order relations of A that contain the relation $R=\{(1,2),(3,4)\}$

I figured out that there is no easy way of counting partial orders, so I sketched all the possible Hasse diagrams (no way to check that out as far as I'm concerned) and then tried to count them by hand.

(1) We have 2 ways. $(1,2)$ up, $(3,4)$ down and viceversa.

(2) We have only 1 way.

(3) and (4) are equivalent, so they give me 2 ways.

(5) and (6) give me 2 ways too.

(7) Gives me 4 ways but 2 of them are mirrored, so 2 ways really.

So we have: $2+1+2+2+2 = 9$ partial orders containing $R=\{(1,2),(3,4)\}$.

I don't have any way to check if I'm right, any help?

Answer 1

Let me count by a different way. I will use $<$ for my partial order and say $x\sim y$ to mean that $x$ and $y$ are incomparable under $<$.

• $1<3$ and $2<4$ - There are 3 partial orders of this type: two total orders based on $2<3$ or $3<2$ and one of your type 7 when $2\sim 3$.
• $3<1$ and $4<2$ - Essentially identical to above, with 3 more.
• $1<3$ and $4<2$ - Just 1 total order: $1<3<4<2$.
• $3<1$ and $2<4$ - Again, just 1.
• $1\sim3$ and $2<4$ - Just 1, of your type 3/4
• $1\sim3$ and $4<2$ - Again, just 1.
• $1<3$ and $2\sim4$ - Just 1, of your type 5/6
• $3<1$ and $2\sim4$ - Again, just 1.
• $1\sim3$ and $2\sim4$ - Just 1, of your type 2.

That's all 9 ways that $\{1,3\}$ and $\{2,4\}$ can be related (or not related), which gives us a total of 13 total orders, as you did after your original miscount.