From: strauch@emmy.mathematik.uni-dortmund.de (Michael Strauch)
Newsgroups: sci.math,sci.math.symbolic,sci.math.research
Subject: Re: WANTED: algorithm to produce all finite topologies
Date: 9 Feb 1994 16:43:23 GMT

gerstner@mathematik.tu-muenchen.de (Manfred Gerstner) writes:


>I'm sorry to bring up this topic again. But nevertheless I need an efficient
>algorithm to print out all topologies.

>I think of entering a *small* number n and receiving a list of sequences
>of subsets of  X := {1,2,...,n}; every sequence being a topology of X.
>(or equivalently: being a base of that topology). It would be fine, if 
>each topology comes up exactly once - or even better, only one representant
>up to homeomorphism.

>By "efficient" I mean that I can wait for the result.

>References or ideas for this algorithm are welcome  
> -  or a list for n = 1 to, say, 7 or 8.

Look at "New Results from an Algorithm for Counting Posets" from J. C.
Culberson and G. J. E. Rawlins, published in Order 7 (90/91), no 4, p 361-374.
There you will find a detailed description for an algorithm for counting
and generating all unlabled finite posets (or non-homeomorphic finite
topologies), which is efficient enough for computing all cases n <= 11. 

M. Erne and K. Stege did use the results from this article to compute the
number of labled topologies for n<=14. You will find their work in
"Counting Finite Posets and Topologies", Order 8 (91), p 247-265.

- Michael Strauch -
strauch@emmy.mathematik.uni-dortmund.de

==============================================================================

From: hogan@cs.colorado.edu (HOGAN APOLLO FRANCI)
Newsgroups: sci.math
Subject: Re: finite topological spaces
Date: 17 Apr 1995 18:54:45 GMT

In article <3mstl7$1jgj@tequesta.gate.net>,
Theodore Hwa <hwatheod@gate.net> wrote:
>The following question has occurred to me.  Let P(S) denote the power set 
>of the set S.  Then for a given positive integer n, how many of the 
>elements of P(P({1,2,...,n})) are topologies on the set {1,2,..,n}?  
>
> Any further  suggestions on this problem?

I am currently reading a book "Fundamentals of Pattern Recognition" by
  Monique Pavel which describes exactly what you're talking about:
  the finite topologies. She refers to Krishnamurthy, V. "On the
  number of topologies on a finite set" Amer. Math. Monthly, Vol. 73
  (1966), pp. 154-157. And mentions that yes, f(1)=1, f(2)=4 and that
  a bound for f(n) is 2^(n*(n-1))-1. Krishnamurthy also "proved that
  f(n) is precisely the number of certain nxn matrices of 0's and 1's
  with a_ii=1 for all i and with the following property:
 	For every ordered pair (R_i,R_j), i,j=1,2,...,n, of rows of
(a_ij) and for every index k, a_ji=1=a_ik implies a_jk=1."
(Pavel, 17)
	She also points out another reference, J.W.Evans, F.Harary,
and M.S.Lynn: "On the computer enumeration of finite topologies,"
Comm. A.C.M.,Vol.10 (1967), pp.295-313.

Good luck!

--Apollo

GCS/M/O -d+ p--- c++() l u++ e+ m++ s n++ h(--) f-(+) !g w+ t r- y+(*) 
-- 
--Apollo

GCS/M/O -d+ p--- c++() l u++ e+ m++ s n++ h(--) f-(+) !g w+ t r- y+(*) 

==============================================================================

From: karner@aut.alcatel.at (Georg Karner)
Newsgroups: sci.math
Subject: Re: Number of topologies
Date: 8 May 1995 08:35:13 GMT

The topic has been discussed on this newsgroup some time ago.

>>> From sieda@hrz.uni-bielefeld.de ( Torsten Sillke) Sep 30 1993

TOP: finite Topologies, finite Posets (T0 Topologies)
TOP- Posets    : 1, 2, 5, 16,  63, 318, 2045, 16999, 183231, 2567284,
TOP              46749427, 1104891746, 33823827452, ... Sloane 588
TOP- Topologies: 1, 3, 9, 33, 139, 718, 4535, ... Sloane 1133
TOP- Posets (labeled)    : 1, 3, 19, 219, 4231, 130023, 6129859, 
TOP                        431723379, ...
TOP- Topologies (labeled): 1, 4, 29, 355, 6942, 209527, 9535341,
TOP                        642779354, 63260289423, ...
TOP- N. J. A. Sloane, A Handbook of Integer Sequences, p14-16
TOP    posets (labeled):      ser.  588 (1244)
TOP    topologies (labeled):  ser. 1133 (1476)
TOP    connected topologies (labeled):  ser.  648 (1245)
TOP- M Erne, On the cardinalities of finite topologies and the number of   
TOP    antichains in partially ordered sets, Disc Math 35 (1981) 119-133
TOP    table of labeled posets 1..8

>>> From: eclark@gauss.math.usf.edu (Edwin Clark) Feb 14 1994

There is a recent article "The numbers of finite lattices and
finite topologies" by Yasunori Koda (ykoda@rst.fujixerox.co.jp)
in the January 1994 issue of the Bulletin of the Institute of Combinatorics and its applications (subscriptions only $35/year!). He gives the number
of topologies on up to 9 element sets.     For up to 7 element sets
see Sloane's "A handbook of integer sequences".