A lower bound for the number of topologies on a finite set

Abstract

An expression for the number of different topologies (not considering homeo-morphisms) on a finite set of n elements is not known. However, lower and upper bounds for the same have been obtained. (See Evans et al . 1967 and Krishnamurthy 1966). Krishnamurthy has established a one-one correspondence between (1., 0) matrices of order n with certain properties and the topologies on a set of n elements. (These matrices turn out to be the adjacency matrices of labelled transitive digraphs with n vertices). This note examines these matrices and uses the observations to obtain a lower bound for the number of topologies. First, a few useful observations are made regarding the structure of these matrices. It is noted that entries of 1's off the main diagonal play an impor tant part. Hence the matrices are grouped into classes S(n, k) viz., (n × n) matrices as above with 1's off the main diagonal in exactly k rows. In the next section some of these classes are enumerated fully while estimates are obtained for the rest. This leads to a lower bound of 2+ Σ^n-l_k=1( ⁿ _k ) (2^n-k-I)^k-2 [ (2^n-k-1)² + k(k-1) (3^n-k-2^n-k) + (^k ₂)2^n-k] .. (1) for the number of topologies. The next section suggests further refinements to this formula and shows how sharper bounds can be obtained. Evans et at. (1967) have enumerated the number of digraphs in which no path is of length greater than 1. The concluding section obtains the same result through a consideration of a subclass of the above matrices.