Algorithms for paths in the lattice of topologies on finite sets (abstract only)

ABSTRACT

A topology on a finite set Sn =[x1,…,xn] is a collection of subsets of Sn containing Sn and the empty set, which is closed under the operations of union and intersection. The class of all topologies on a given Sn is partially ordered by inclusion and forms a lattice we shall denote by L(Sn). J.W. Evans, F. Harary and M.S. Lynn [“On the computer enumeration of finite topologies”, Comm. ACM 10, 295-8 (1967) discussed the large number of topologies for even comparatively small values of n, and the authors [“Topologies on finite sets III”, Congressus Numerantium 33, 185-8 (1981) and its prequels] described the lattice of topologies. In this paper efficient algorithms are developed to enumerate the shortest paths between a pair of arbitrary points in the lattice, as well as to determine the length of the shortest path, and to determine the paths themselves. The problem and its solution have theoretical interest, as well as practical applications to education and psychology [L. Fernandez, H. Levinson and M. Seglin, “A discrete mathematical model for learning and intelligence”, to appear].

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Performance, Theory