4
$\begingroup$

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$ ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Sep 20, 2011 at 12:34
1
$\begingroup$

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. )

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Brendan McKay
    Commented Sep 20, 2011 at 11:52
  • $\begingroup$ 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. $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 20, 2011 at 11:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .