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

Let $T(n)$ denote the number of transitive binary relations on an $n$-element set. So T(1) = 2 and T(2) = 13, for of the 16 possible relations on a 2-element set {a,b}, the only three which are not transitive are

(i) {(a,b), (b,a)}, (ii) {(a,a), (a,b), (b,a)}, (iii) {(b,b), (a,b), (b,a)}.

There is some literature on this function - a wikipedia entry, a sequence in Sloane up to $n=18$, a few research papers on this and similar kinds of functions, including some complicated formulas for $T(n)$. However, I have not seen anywhere a "nice asymptotic estimate" for $T(n)$. Using the data in Sloane I computed, for $1 \leq n \leq 18$, the function $f(n) = \frac{\log_{2} T(n)}{n^2}$, obtaining the following approximate values

1, 0.9251, 0.8242, 0.7477, 0.6894, 0.6435, 0.6063, 0.5755, 0.5494, 0.5270, 0.5075, 0.4903, 0.4751, 0.4614, 0.4491, 0.4380, 0.4278, 0.4184

So my general question is whether anything (non-trivial) is known about the asymptotics of $T(n)$, and a more specific question is whether $f(n) \rightarrow 0$ as $n \rightarrow \infty$ ?

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

If $P(n)$ is the number of partial orders, then $\log_2 P(n) = n^2/4 + o(n^2)$, an old result of Kleitman. Look in MathSciNet for many different sharpenings. Now if $T(n)$ is the number of transitive relations, then Klaska proved that $T(n)$ and $2^n P(n)$ are asymptotically equal. Therefore, $\log_2 T(n) = n^2/4 + o(n^2)$. Ref to Klaska: MR1446401 (98c:05006) Klaška, Jiří. Transitivity and partial order. Math. Bohem. 122 (1997), no. 1, 75–82.

share|improve this answer
    
Commenting on my own answer: When I worked on enumerating partial orders with Gunnar Brinkmann, we found that the proven asymptotically behavior was not visible on small sizes. For example, Kleitman proved that most partial orders have only 3 levels, of size about $n/4,n/2,n/4$, but as far as we could generate all of them (about $4\times 10^{14}$ isomorphism types) only a tiny fraction had 3 levels. I guess this slow convergence to asymptotic behaviour is also true for transitive relations, which is why your constants don't look like they are converging to 1/4 even though they are. –  Brendan McKay Sep 20 '11 at 12:34
add comment

Yes, a lot is known. Transitive relations are the same (essentially; there is a slight problem with self-loops) as strongly connected digraphs. See:

http://www.math.uwaterloo.ca/~nwormald/papers/dicores.pdf

and references therein.

EDIT oops, answers a wrong (but related) question... Formulas (though not asymptotics) for the quantities in question appear in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.6879&rep=rep1&type=pdf

Another Edit Partial orders (as mentioned by @Aaron) have been asymptotically enumerated, and the log is asymptotic to $n^2/4.$ (see Kleitman, D. J.; Rothschild, B. L. Asymptotic enumeration of partial orders on a finite set. Trans. Amer. Math. Soc. 205 (1975), 205–220. )

share|improve this answer
    
I don't think that's true. Almost all digraphs are strongly connected, so if $D(n)$ is the number of them (with any rule for loops), then $\log_2 D(n) / n^2 \to 1$. –  Brendan McKay Sep 20 '11 at 11:52
    
I don't think so. Any strict partial order gives a transitive relation and a (loop free) digraph. Of these, most are not connected. The $n!$ linear orders give digraphs which are connected, but none are strongly connected. –  Aaron Meyerowitz Sep 20 '11 at 11:52
add comment

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.