Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
That does seem to answer the question I asked. Unfortunately... what I actually wanted was A001035, not A003024. Any ideas? –  Charles Sep 5 '11 at 18:21

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.

share|improve this answer
    
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). –  Charles Sep 5 '11 at 18:22
    
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. –  Richard Stanley Sep 5 '11 at 21:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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