3
$\begingroup$

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
    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.2012-04-26
  • 1
    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?"2012-04-26
  • 0
    @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.2012-04-27

1 Answers 1

2

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.

  • 0
    Did you mean [this](http://www.springerlink.com/content/d4dbce7pmctuenmg/) link? The paper is quite beyond my reach. But thanks for taking the trouble. :)2012-04-26
  • 0
    @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.2012-04-26
  • 0
    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.2012-04-26
  • 0
    @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.2012-04-26
  • 0
    [Here](http://en.wikipedia.org/wiki/Hasse_diagram#A_.22good.22_Hasse_diagram) are some examples.2012-04-26
  • 0
    @MichaelHardy :Thanks.2012-04-26