Kesavan, S. (1975) A lower bound for the number of topologies on a finite set Proceedings of the Indian National Science Academy  Part A: Physical Sciences, 41 (3). pp. 207212. ISSN 03700046

PDF
 Publisher Version
218kB 
Official URL: http://www.dli.gov.in/rawdataupload/upload/insa/IN...
Abstract
An expression for the number of different topologies (not considering homeomorphisms) 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 oneone 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+ Σ^{nl}_{k=1}( ^{n} _{k} ) (2^{nk}I)^{k2} [ (2^{nk}1)^{2} + k(k1) (3^{nk}2^{nk}) + (^{k} _{2})2^{nk}] .. (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.
Item Type:  Article 

Source:  Copyright of this article belongs to Indian National Science Academy. 
ID Code:  75403 
Deposited On:  22 Dec 2011 11:33 
Last Modified:  18 May 2016 19:25 
Repository Staff Only: item control page