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

As far as I know, it is an open problem to give a formula counting transitive relations on an $n$-element set. Is it easier to count the idempotent relations, that is relations that are both transitive and interpolative? (A relation $\rho$ is interpolative when $x\rho y\implies((\exists z)\ x\rho z \wedge z\rho y).$)

Also, if we denote the number of transitive relations on an $n$-element set by $T_n$ and the number of idempotent relations by $I_n$, can we say what the asymptotic behavior of $I_n/T_n$ is?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

The answer seems to be in Butler, K. K.-H.,The number of idempotents in (0,1)-matrix semigroups, Linear Algebra and Its Applications 5 (1972), 233–246. I will see if I have access to the journal and will tell you more.

Edit. The paper is here for free. It counts the idempotents by D-class so it is not written down in a simple succinct formula. If you google idempotent boolean matrix there are further papers which may be of use.

share|improve this answer
    
This is the answer to your first question. I don't know about the second one. –  Benjamin Steinberg Feb 27 '13 at 14:03
    
Thank you very much. I made a mistake in the second question. I've changed "interpolative" to "idempotent" now. –  Michał Masny Feb 27 '13 at 18:57
add comment

See OEIS sequence A121337 and references given there.

share|improve this answer
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.