Archive:
Subtopics:
Comments disabled |
Fri, 08 Jun 2007
Counting transitive relations
A relation is transitive if, whenever it has both (a, b) and (b, c), it also has (a, c). For the last week I've been trying to find a good way to calculate the number of transitive relations on a set with three elements. There are 13 transitive relations on a set with 2 elements. This is easy to see. There are 16 relations in all. The only way a relation can fail to be transitive is to contain both (1, 2) and (2, 1). There are clearly four such relations. Of these four, the only one that is transitive has (1, 1) and (2, 2) also. Similarly it's quite easy to see that there are only 2 relations on a 1-element set, and both are transitive. There are 512 relations on a set with 3 elements. How many are transitive? It would be very easy to write a computer program to check them all and count the transitive ones. That is not what I am after here. In fact, it would also be easy to enumerate the transitive relations by hand; 512 is not too many. That is not what I am after either. I am trying to find some method or technique that scales reasonably well, well enough that I could apply it for larger n. No luck so far. Relations on 3-sets can fail to be transitive in all sorts of interesting ways. Say that a relation has the F_{abc} property if it contains (a,b) and (b,c) but not (a,c). Such a relation is intransitive. Now clearly there are 64 F_{abc} relations for each distinct choice of a, b, and c. But some of these properties overlap. For example, {(a,b), (b,c), (c,a)} has not only the F_{abc} property but also the F_{bca} and F_{cab} properties. Of the 64 relations with the F_{abc} property, 16 have the F_{bca} property also. 16 have the F_{aba} property. None have the F_{acb} property. There are 12 of these properties, and they overlap in a really complicated way. After a week I gave in and looked in the literature. I have a couple of papers in my bag I haven't read yet. But it seems that there is no simple solution, which is reassuring. One problem is that the number of relations on n elements grows very rapidly (it's 2^{n2}) and the number of transitive relations is a good-sized fraction of these.
[Other articles in category /math] permanent link |