I've been reading about lattices and partial orders (my reference: Applied Abstract Algebra by Lidl, Pilz) while this question struck me.

Let X be a finite set. Is there any way to determine the total number of non-isomorphic partial orderings of this set?

I searched math.SE a bit, but couldn't find any similar question. Any kind of response/help will be appreciated. Best regards.

  • 1
    $\begingroup$ How do you define isomorphism between Hasse diagrams, so that two Hasse diagrams fail to be isomorphic even while the posets they represent are the same (i.e. isomorphic)? I know that two Hasse diagrams for the same partial ordering can look very different from each other, but I don't know what definition of isomorphism one would use. $\endgroup$ – Michael Hardy Apr 26 '12 at 17:25
  • 1
    $\begingroup$ The question is phrased in a misleading way. What it seems to mean, if we are to judge by the O.P.'s comments and by his acceptance of an answer, is: "Let $X$ be a finite set. Is there any way to determine the total number of non-isomorphic partial orderings of this set?" $\endgroup$ – Michael Hardy Apr 26 '12 at 18:09
  • $\begingroup$ @MichaelHardy : Yes, that is what I actually meant. I thought every partial order has a unique representation by Hasse diagram. I've changed the question accordingly. Thanks a million for pointing this out. $\endgroup$ – Sayantan Apr 27 '12 at 0:55

No general result seems to be known; known values beyond the trivial ones seem to have been found by computer enumeration. This is sequence A001035 in the On-Line Encyclopedia of Integer Sequences; the first link has a number of references that may be of interest.

| cite | improve this answer | |
  • $\begingroup$ Did you mean this link? The paper is quite beyond my reach. But thanks for taking the trouble. :) $\endgroup$ – Sayantan Apr 26 '12 at 16:24
  • $\begingroup$ @Sayantan: You’re welcome. I actually wasn’t thinking of any of the links in particular; I just thought that this was probably the handiest set of references on the subject. $\endgroup$ – Brian M. Scott Apr 26 '12 at 16:28
  • $\begingroup$ That OEIS entry seems to be about the number of posets with $n$ vertices, not the number of Hasse diagrams corresponding to one poset. Two different Hasse diagrams corresponding to the same poset, representing the exact same partial ordering, may look quite different from each other. But the posets they represent are isomorphic to each other. I don't know what it means to say the Hasse diagrams themselves are or are not isomorphic to each other in such a situation. $\endgroup$ – Michael Hardy Apr 26 '12 at 16:44
  • $\begingroup$ @MichaelHardy : I didn't know that same poset can be represented by two different Hasse diagrams. (Can you please give an example?) I guess that makes my question ambiguous. In that case my question should be regarding the number of posets, not their Hasse diagrams. $\endgroup$ – Sayantan Apr 26 '12 at 16:53
  • $\begingroup$ Here are some examples. $\endgroup$ – Michael Hardy Apr 26 '12 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.