1

I am totally confused about the exercise I have and ask your help:

I have to draw Hasse diagrams for all partial orders on the set $\{1,2,...,n\}$ which have the maximum element (such $m$ that $aRm$ for all $a$ in the set). And I am pretty confused about the following points:

  1. I am thinking: there are $2^{n^2}$ possible subsets of my set $\times $my set. I can estimate the number of reflexive relations: $2^{n^2 - n}$. Good. Somehow I have to do the same for antisymmetric and transitive relations. Then I build and intersection and will get the total number of partial orders on my set (cheating with OEIS I can say that there are 219 of them. But I do not cheat.) But then, how to filter them to the sets that have maximum elements?

  2. In order to draw all possible Hasse diagramms I have to estimate how much of them exist and how do they look like. Well, I have to do the point 1. again, as I have no idea how to draw something you do not know.

So, what is the connection between these diagramms, maximum elements and partial orders? Is my plan in point 1. to difficult? Do I interprete the exercise too complicated? How to find the solution path?

jupiter_jazz
  • 517

1 Answers1

1

You can find them all (up to isomorphism) in the drawing in this question.
They are the examples (j), (k), (n), (m) and (p).
If you're interested in unlabelled versions of the posets, there are only these 5;
if you want them all, just consider for each of the examples mentioned, the ($4! = 24$) permutations of the four elements, giving a total number of $120$.

Update

Actually, to get all of them, it's not about considering all permutations, since even some of these give the same (labelled) poset. So,

  • For the posets of the type (j), there exist $12=4 \times 3$ possibilities, corresponding to the choice of the two greatest elements (then, for the two minimal elements, is the same whether you choose one on the right and the other on the left or vice-versa).
  • For those of type (k), the same thing: $12 = 4 \times 3$ possibilities corresponding to the choice of top and bottom elements.
  • For those of type (n), there exist $4$ possibilities corresponding to the four possible choices for the top element.
  • For those of type (m) or (p), you really have to consider all permutations, that is, $24$ choices each.

So overall, there exist $12 + 12 + 4 + 24 +24 = 76$ different labellings for these five diagrams.

amrsa
  • 12,917