Counting Unlabelled Topologies and Transitive Relations

Gunnar Brinkmann Applied Mathematics and Computer Science Ghent University B–9000 Ghent Belgium

                   Gunnar.Brinkmann@ugent.be

Brendan D. McKay^{1} Department of Computer Science Australian National University Canberra ACT 0200 Australia

                       bdm@cs.anu.edu.au

Abstract We enumerate isomorphism classes of several types of transitive relations (equiva-

lently, finite topologies) up to 15 or 16 points.

1 Introduction

Pfeiffer [3] presented a classification of various types of order relations and determined their numbers up to 12 points. In this paper, we extend the counts to 15 or 16 points. We defer to [3] for historical survey, and only give enough background to precisely define the objects we are counting.

We consider only directed graphs (digraphs) that do not have multiple edges but may have up to one loop per point. A transitive relation digraph (TRD) is a digraph such that presence of edges (x, y) and (y, z) implies that (x, z) is also present (even if x, y, z are not distinct). (We cannot use the more natural term “transitive digraph” since its most common definition does not allow loops; this has the unfortunate consequence that transitive digraphs don’t correspond to transitive relations.)

1Research supported by the Australian Research Council.

A strong component of a digraph is a maximal set of points P such that there is a directed path within P from x to y for each pair x, y ∈ P. (This permits the zero-length path from x ∈ P to itself.)

If a strong component of a TRD has only one point, there may or may not be a loop on that point. However, larger strong components of a TRD have loops on every point and edges in both directions between each pair of points. If the strong components of a TRD are contracted to single points, the result is a TRD that has no directed cycles apart from loops.

Two digraphs are isomorphic if there is a bijection between their point-sets that induces a bijection between their edge-sets. Thus we can refer to isomorphism classes of digraphs.

Of course a digraph can be viewed as representing some kind of order relation ≤, where x ≤ y iff there is an edge (x, y). In the language and notation of Pfeiffer, we have the following correspondences:

• A transitive relation corresponds to an arbitrary TRD. Let t(n) be the number of isomorphism classes of transitive relations. This is Sloane’s sequence \underline{A091073}.

• A quasi-order corresponds to a TRD such that every single-point strong component has a loop. Let q(n) be the number of isomorphism classes of quasi-orders. This is Sloane’s sequence \underline{A001930}.

• A soft order corresponds to a TRD whose strong components each have only one point (with or without loop). Let s(n) be the number of isomorphism classes of soft orders. This is Sloane’s sequence \underline{A079265}.

• A partial order corresponds to an TRD whose strong components are all single points with loops. Because we can remove and replace the loops in a unique fashion, the counts here are the same as for acyclic TRDs. Let p(n) be the number of isomorphism classes of partial orders.

There are also relationships with finite topologies: general topologies are in bijective correspondence with quasi-orders, and T_{0}-topologies are in bijective correspondence with partial orders. These bijections preserve isomorphism, so we are also counting isomorphism classes of topologies.

For enumerative purposes, we will define some specialized numbers.

• q(n, m) is the number of isomorphism classes of TRDs with n points and m strong components, such that each single-point strong component has a loop.

• t(n, m) is the number of isomorphism classes of TRDs with n points and m strong components (with single-point strong components having a loop or not).

In terms of these specialized numbers, we have

q(n) = ∑_{m=1}^{n} q(n, m),  t(n) = ∑_{m=1}^{n} t(n, m),
p(n) = q(n, n),  s(n) = t(n, n).

2 Computing t(n, m) and q(n, m) for small n

Our main tool is a program which generates non-isomorphic partially ordered sets (posets). In our paper [1], we gave values of p(n) up to n = 16 based on output from that program.

Given a poset P, we can make a TRD G by replacing each point by a directed clique (perhaps of a single point). Such directed cliques become the strong components of G. If points v, w of P become strong components c_{v}, c_{w} of G, then an edge (v, w) of P becomes the set of all possible edges from c_{v} to c_{w} in G. Clearly non-isomorphic posets lead to nonisomorphic TRDs, since G uniquely determines P. The only remaining issue is that some of the TRDs made from P may be isomorphic due to symmetries (automorphisms) of P.

Given a poset P, we can represent its expansion to a TRD by assigning a positive integer weight to each point. This weight corresponds to the size of the directed clique that the point will be expanded to. We also consider extended weights where there are two types of weight with value 1 (corresponding to loop and non-loop).

For any permutation γ, define

C_{γ}(x) = ∏_{i=1}^{k} (1 − x^{a_{i}})^{−1}

C′_{γ}(x) = ∏_{i=1}^{k} (1 + (1 − x^{a_{i}})^{−1}),

where a_{1}, a_{2}, …, a_{k} are the cycle lengths of γ.

Theorem 2.1. Let 1 ≤ m ≤ n. Then

q(n, m) = [x^{n−m}] ∑_{P}( |Aut(P)|^{−1} ∑_{γ∈Aut(P)} C_{γ}(x))

t(n, m) = [x^{n−m}] ∑_{P}( |Aut(P)|^{−1} ∑_{γ∈Aut(P)} C′_{γ}(x)),

where the first sum in each case is over isomorphism class representatives P of posets on m points, Aut(P) is the automorphism group of P, and [x^{n−m}] denotes extraction of the coefficient of x^{n−m}.

Proof. We prove the formula for q(n, m); the other is similar. Let P be a poset with m points. By the Frobenius-Burnside Lemma, the number of equivalence classes under Aut(P) of weight assignments with total weight n is the average over γ ∈ Aut(P) of the number w_{n}(γ) of such weight assignments fixed by γ.

Consider one such element γ ∈ Aut(P) with cycles of length a_{1}, a_{2}, …, a_{k}. A weight assignment is fixed by γ iff it is constant on each cycle of γ, so w_{n}(γ) is the coefficient of x^{n} in

∏_{i=1}^{k}(x^{a_{i}} + x^{2a_{i}} + x^{3a_{i}} + ⋯) = x^{m}C_{γ}(x).

The result now follows by averaging over γ.

As mentioned earlier, q(n, n) = p(n). We can also identify q(n, n−1) as the total number of orbits of Aut(P) over all posets on n − 1 points. Using our previously-computed value of p(16), this enabled us to determine q(n, m) for n ≤ 16 and t(n, m) for n ≤ 15 by computing the automorphism groups of all the posets up to 15 points. Except in some simple (but common) situations where the poset generator had already determined Aut(P), this was computed using nauty [2].

The resulting values are given in Tables 1–3. The programs were run twice in case of machine errors. We also successfully recovered the numbers given by Pfeiffer [3] and the values of p(n) up to n = 15 given by Brinkmann and McKay [1].

n  q(n)  s(n)  t(n)
1  1  2  2
2  3  7  8
3  9  32  39
4  33  192  242
5  139  1490  1895
6  718  15067  19051
7  4535  198296  246895
8  35979  3398105  4145108
9  363083  75734592  90325655
10  4717687  2191591226  2555630036
11  79501654  82178300654  93810648902
12  1744252509  3984499220967  4461086120602
13  49872339897  249298391641352  274339212258846
14  1856792610995  20089200308020179  21775814889230580
15 89847422244493  2081351202770089728 2226876304576948549
16 5637294117525695

Table 1: Quasi-orders, soft orders, and transitive relations

1 1  1  10 1  1  14 1  1
2 1  1  10 2  14  14 2  20
2 2  2  10 3  120  14 3  256
3 1  1  10 4  849  14 4  2790
3 2  3  10 5  5123  14 5  27637
3 3  5  10 6  27439  14 6  260840
4 1  1  10 7  127965  14 7  2385741
4 2  5  10 8  501591  14 8  21304106
4 3  11  10 9  1487301  14 9  184860968
4 4  16  10 10  2567284  14 10  1535230287
5 1  1  11 1  1  14 11  11832383054
5 2  6  11 2  15  14 12  80018898562
5 3  22  11 3  150  14 13  425004096962
5 4  47  11 4  1193  14 14  1338193159771
5 5  63  11 5  8406  15 1  1
6 1  1  11 6  53443  15 2  21
6 2  8  11 7  309719  15 3  299
6 3  35  11 8  1599822  15 4  3525
6 4  113  11 9  7040921  15 5  38420
6 5  243  11 10  23738557  15 6  401602
6 6  318  11 11  46749427  15 7  4124565
7 1  1  12 1  1  15 8  41997196
7 2  9  12 2  17  15 9  424381067
7 3  52  12 3  182  15 10  4221560826
7 4  213  12 4  1632  15 11  40603719604
7 5  682  12 5  13011  15 12  365485856203
7 6  1533  12 6  96226  15 13  2906408331804
7 7  2045  12 7  664467  15 14  18255153928204
8 1  1  12 8  4268404  15 15  68275077901156
8 2  11  12 9  24858756  16 1  1
8 3  71  12 10  124784466  16 2  23
8 4  367  12 11  484673601  16 3  343
8 5  1503  12 12  1104891746  16 4  4396
8 6  4989  13 1  1  16 5  52033
8 7  12038  13 2  18  16 6  597502
8 8  16999  13 3  218  16 7  6804011
9 1  1  13 4  2154  16 8  77823441
9 2  12  13 5  19320  16 9  897440095
9 3  95  13 6  162404  16 10  10402896209
9 4  570  13 7  1304373  16 11  119938485210
9 5  2923  13 8  10009358  16 12  1348204100877
9 6  12591  13 9  72589838  16 13  14281079724622
9 7  44842  13 10  483531684  16 14  134410089884839
9 8 118818  13 11  2803234294  16 15 1003992754517006
9 9 183231  13 12 12677658783  16 16 4483130665195087
13 13 33823827452

Table 2: Values of q(n, m) for various n, m

1 1  2  9 1  1  13 1  1
2 1  1  9 2  15  13 2  21
2 2  7  9 3  174  13 3  335
3 1  1  9 4  1769  13 4  4852
3 2  6  9 5  17694  13 5  70797
3 3  32  9 6  170391  13 6  1066041
4 1  1  9 7  1577763  13 7  16906476
4 2  8  9 8  12823256  13 8  282183725
4 3  41  9 9  75734592  13 9  4922404711
4 4  192  10 1  1  13 10  87597193530
5 1  1  10 2  17  13 11  1521294651297
5 2  9  10 3  207  13 12  23426706135708
5 3  63  10 4  2380  13 13  249298391641352
5 4  332  10 5  26352  14 1  1
5 5  1490  10 6  294156  14 2  23
6 1  1  10 7  3243880  14 3  381
6 2  11  10 8  34592661  14 4  5964
6 3  84  10 9  325879156  14 5  93159
6 4  583  10 10  2191591226  14 6  1521101
6 5  3305  11 1  1  14 7  26315265
6 6 15067  11 2  18  14 8  486434324
7 1  1  11 3  248  14 9  9568317752
7 2  12  11 4  3068  14 10  197959166598
7 3  112  11 5  37919  14 11  4196507844123
7 4  883  11 6  472519  14 12  86930341478767
7 5  6537  11 7  6031290  14 13  1595279690032943
7 6 41054  11 8  77251333  14 14 20089200308020179
7 7 198296 11 9  960789368  15 1  1
8 1  1  11 10 10587762484  15 2  24
8 2  14  11 11 82178300654  15 3  435
8 3  139  12 1  1  15 4  7190
8 4  1294  12 2  20  15 5  120514
8 5 11096  12 3  288  15 6  2110489
8 6 90758  12 4  3911  15 7  39534004
8 7 643701 12 5  52415  15 8  798048843
8 8 3398105 12 6  724866  15 9  17393487215
12 7  10377573  15 10  406531057397
12 8  153952401  15 11  10041016241522
12 9  2314756589  15 12  254873608116034
12 10 33895893064  15 13  6326335208572503
12 11 440211138507 15 14 138933427209562650
12 12 3984499220967 15 15 2081351202770089728

Table 3: Values of t(n, m) for various n, m

References

[1] G. Brinkmann and B. D. McKay, Posets on up to 16 points, Order 19 (2002), 147–179.

[2] B. McKay, nauty – a program for graph isomorphism and automorphism, available at

    http://cs.anu.edu.au/∼bdm/nauty/.

[3] G. Pfeiffer, Counting transitive relations, J. Integer Seq. 7 (2004), paper 04.3.2.

2000 Mathematics Subject Classification: Primary 06A99; Secondary 05C20, 05C30. Keywords: transitive relation, finite topology, order, directed graph.

(Concerned with sequences \underline{A001930}, \underline{A079265}, and \underline{A091073} .)

Received October 19 2004; revised version received March 18 2005. Published in Journal of Integer Sequences, March 29 2005.

Return to Journal of Integer Sequences home page.