From: bumby@lunar.rutgers.edu (Richard Bumby) Newsgroups: sci.math.research Subject: Re: How Many Topologies on a Finite Set? Date: 2 Jun 1997 17:28:25 -0400 Thomas Haeberlen writes: >How many topologies (up to homeomorphism) can be defined on a finite set >with n elements? >Can anyone give me a good reference to the answer for that question? >............................ The standard reference is: J. W. Evans, F. Harary and M. S. Lynn; On the computer enumeration of finite topologies; Comm. Assoc. Computing Mach. 10 (1967), 295--298. There should be an update to this enumerative work somewhere, but I haven't heard of it. I have this reference handy because I contributed to a paper on the structure of the lattice of topologies. That paper is: R. Bumby, R. Fisher, H. Levinson and R. Silverman; Topologies on Finite Sets; Proc. 9th S-E Conf. Combinatorics, Graph Theory, and Computing (1978), 163--170 The authorship graph of this paper was a star with Hank Levinson at the center. He continued working on this question, and I think there is another paper with a proper subset of the same authors a few years later in the same conference proceedings. This conference is also the natural place to look for announcements of new results on the question. -- R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor 1992--1996 bumby@math.rutgers.edu || bumby@dimacs.rutgers.edu || Phone: [USA] 908 445 0277 * FAX 908 445 5530 ============================================================================== From: prenteln@wiley.csusb.edu (Paul Renteln) Newsgroups: sci.math.research Subject: Re: How Many Topologies on a Finite Set? Date: 3 Jun 1997 05:27:09 GMT In article <3391EF2F.25DB@cip.mathematik.uni-stuttgart.de>, haeberts@cip.mathematik.uni-stuttgart.de wrote: > How many topologies (up to homeomorphism) can be defined on a finite set > with n elements? > > Can anyone give me a good reference to the answer for that question? Is > there a "simple" formula for the number of "different" topologies, > depending on n? Or is this another simple question with a complicated > answer? > The question of the number of topologies on a finite point set is definitely a combinatorial one, and also probably impossible. There is no known formula, although asymptotics are known. See Kleitman, D., and Rothschild, B., ``The number of finite topologies'', Proc. AMS, 25, 1970, 276-282. and Kleitman, D., and Rothschild, B., ``Asymptotic enumeration of partial orders on a finite set'', Trans. Amer. Math. Soc. 205 (1975), 205--220. For other references, consult P. Renteln, ``On the enumeration of finite topologies'', Journal of Combinatorics, Information, and System Sciences, 19 (1994) 201-206 The problem ``reduces'' to finding the number of partial orders on a finite set, which is an equally intractable problem. You might want to see P. Renteln, ``Geometrical Approaches to the Enumeration of Finite Posets: An Introductory Survey'', Nieuw Archief voor Wiskunde, 14 (1996) 349-371. and references therein. -- Paul Renteln Associate Professor Department of Physics California State University San Bernardino 5500 University Parkway San Bernardino, CA 92407 prenteln@wiley.csusb.edu ****************************************************************** A man's life in these parts often depends on a mere scrap of information. The Gunslinger Fistfull of Dollars ******************************************************************