3
$\begingroup$

It's hard to count the number of posets with a given number of elements; Sloane's A001035 has it only up to 18. Are asymptotic results known?

My actual interest is in transitive relations, Sloane's A006905, but it's not hard to convert between these. I would accept an answer giving either.

[1] Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences 7 (2004).

[2] R. P. Stanley, Enumerative Combinatorics, 1986.

$\endgroup$

2 Answers 2

2
$\begingroup$

The asymptotics for acyclic graphs is not the same as for those that are transitive. The asymptotics for posets is given in D. J. Kleitman and B. L. Rothschild, Trans. Amer. Math. Soc. 205 (1975), 205-220.

$\endgroup$
2
  • $\begingroup$ You're right, I misstated the problem. My ultimate interest is the number of transitive relations on a relation with labeled elements, Pfeiffer's T(n). $\endgroup$
    – Charles
    Sep 5, 2011 at 18:22
  • 1
    $\begingroup$ If $f(n)$ is the number of $n$-element posets, or labelled posets, or transitive relations, or labelled transitive relations, etc., then $f(n)= 2^{\frac{n^2}{4} + o(n^2)}$. If you want an asymptotic rather than logarithmically asymptotic formula, then the situation is more delicate and depends on the precise objects being enumerated. $\endgroup$ Sep 5, 2011 at 21:11
1
$\begingroup$

If you look at:

http://en.wikipedia.org/wiki/Directed_acyclic_graph#Enumeration

And then look at the cited paper by our own contributor B. McKay et al, section 3 (the paper is freely available) they discuss asymptotics, and give references to papers by E. Bender et al (references 1, 2 in the paper). The paper (ref 4) by Gessel counts by number of sources and sinks, which is surely within $\epsilon$ of what you seek.

$\endgroup$
1
  • $\begingroup$ That does seem to answer the question I asked. Unfortunately... what I actually wanted was A001035, not A003024. Any ideas? $\endgroup$
    – Charles
    Sep 5, 2011 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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