GRAPHS AND MATRICES IN THE STUDY OF FINITE (TOPOLOGICAL) SPACES

Rick Kreminski

Introduction. In a first course in topology (e.g. [10]), one invariably comes across a finite topology, i.e. a topology on a space X with n < ∞ points. Beginning students (and many instructors) are quite surprised when first told that, for instance, if X has just 6 points, there are 209,527 possible topologies on X. This paper is written in part for those who wonder “why so big a number?”, and “how is it obtained?” In fact, there are 115,617,051,977,054,267,807,460 topologies possible on a set with n = 14 elements, and this seems to be the largest n for which the number of topologies is known (see [4]).

The main purpose of this article, however, is not to study this specific enumeration problem. We instead focus on a productive relationship between graph theory, matrix algebra, and finite topologies. While teaching an introductory topology class, we chanced on [13], which alluded to a graph theoretic approach to the study of finite topologies: each topology on X can be identified with a certain directed graph with n nodes (see also [3]). This gives a nice way to literally visualize a topology. We then show how the adjacency matrix associated to the graph (defined in section 3) provides many surprises. For one, the left “eigenvectors” of the matrix directly correspond to the open sets in the topology; and the right “eigenvectors” correspond to the closed sets. In addition, matrices will also allow us to put a natural topology on the space of finite topologies. For much of the discussion, the figures play a crucial role in understanding. (Many of our discoveries have since turned out to be previously known in the fairly scattered literature on this subject. Our approach, however, with its emphasis on the graph and its adjacency matrix, differs from those taken in most of the literature. Our approach allows for some one–line proofs of published results. Many of our observations concerning adjacency matrices, such as those dealing with fineness of topologies and product topologies, seem to be new.) A knowledge of the basic definitions in undergraduate topology, and some discrete mathematics, is all that will be assumed.

In the final two sections, we discuss an (apparently new) enumeration problem associated to finite topologies, and include some preliminary results; then propose a conjecture; and finally raise several questions about finite topological spaces.

1. Finite Topologies, Pre– and Partial Orders, and Directed Graphs. We begin with the observation, slightly generalizing [1] and used in [3], that for a given point set X with n < ∞ elements we have the following one–to–one correspondence, which we will explain below:

{topologies on X} ↔ {relations on X that are reflexive and transitive}.

Relations that are reflexive and transitive are known as “preorders” (and, sometimes, as “quasiorders”, a term we will not use). The first map in the correspondence arises as follows. Given a topology τ on X, define a preorder ≤ on X by x ≤ y if and only if every open set containing x also contains y, i.e. if and only if x ∈ \overline{\{y\}}. (This is equivalent to \overline{\{x\}} ⊆ \overline{\{y\}}.) We leave to the reader the simple check that ≤ is a preorder. Conversely, we specify the second map in the correspondence: given a preorder ≤ on X, define a topology on X by declaring U ⊆ X to be open if and only if for any x ∈ U, if x ≤ y then y ∈ U. Again, we leave it to the reader to see that this indeed defines a topology on X. Finally, one must check that the two maps described above are inverses of one another. (For this, the reader may wish to ponder precisely where finiteness comes in.)

The graphical interpretations of the correspondence maps are as follows:

Construct a graph from a topology on X by including a directed edge from x_{i} to x_{j} if and only if x_{i} ≤ x_{j}, i.e. if and only if every open set containing x_{i} also contains x_{j}.

Compare with Figure 1 (each node should have an edge to itself, but is suppressed for legibility). The reader is encouraged to find the graphs associated to the trivial topology on X, as well as the discrete topology on X, before reading on. [Answers: for the trivial topology, the graph will have a directed edge from each node to every other node; the opposite extreme occurs for the discrete topology: the graph has no edges whatsoever.] Conversely,

Given the graph of a reflexive, transitive relation with nodes {x_{i}}, a set of nodes U is defined to be open in the associated topology if and only if every edge which has an initial point in U has its terminal point in U (i.e. no edges come “out of” U). [Similarly a set of nodes C is closed in the associated topology if and only if every edge which has its initial point in the complement of C has its terminal point in the complement (i.e. no edges come “into” C).]

Thus, one can inspect the graph and quickly deduce which subsets of X are open and which are closed in the associated topology, just from examining the edges. The reader is urged to visually confirm the above criterion for open (and closed) sets by re–examining Figure 1; starting with the graph in Figure 1, one can quickly deduce which sets in X should be open (and closed). We will sometimes use the non–standard terms “reflexive graphs” and “transitive graphs” (meaning, respectively, directed graphs with edges from each node to itself; and directed graphs such that if there is an edge from node m to n and from n to p, then there is an edge from m to p.)

A given point set X admits many different topological structures. Since a topology on X is a collection of subsets of X (namely, the “open” sets), perhaps the crudest bound on the number of topologies on X is the number of possible collections of subsets. Since X has n elements, there are 2^{n} possible subsets of X; thus there are 2^{2^{n}} possible collections of subsets for X; so there can be at most 2^{2^{n}} possible topologies on X. But this bound can be vastly improved from the graph–theoretic viewpoint: there can’t be more topologies on X than directed graphs that have n nodes; and these are easy to count. Namely, for every one of the n(n − 1)/2 distinct pairs of points, we have at most 4 choices for the possible edges connecting the points (e.g. given the pair {a, b}, we could have an edge from a to b; or one from b to a; or both such edges; or neither). Thus, there clearly are at most 4^{n(n−1)}/2, i.e. at most 2^{n(n−1)}, finite topologies on X. ([9] also deduced this bound in a completely different way.)

Another almost immediate, nontrivial, consequence: other than the discrete topology, any topology has at most 3(2^{n−2}) open sets.

\underline{Proof}. Since the topology is not the discrete topology, the corresponding graph has at least one edge. So consider two points a, b connected by an edge, say from a to b. Removing them from consideration for the moment, there are 2^{n−2} total subsets of the remaining elements. Each one of these sets V can lead to, at most, 3 open sets in the topology, namely V ∪ {a, b}, V ∪ {b}, or V (since there is an edge from a to b, every open set containing a contains b; so V ∪ {a} cannot be open). The proof is complete.

We originally conjectured this result based on computer evidence as tabulated in Section 7. (Our bound on the number of open sets possible in a topology is valid for any topological space. In case X is required to be T_{0}, defined below, [11] and [14] show that there is exactly one topology (up to homeomorphism) on X that has precisely 3(2^{n−2}) open sets; two topologies with 5(2^{n−3}) open sets; three with 9(2^{n−4}) open sets; etc.)

Next, recall that a topological space S is T_{0} if and only if given any two distinct points a, b ∈ S, there is an open set containing a that doesn’t contain b, or an open set containing b that doesn’t contain a. (The other separation axioms are not relevant in this article; the only T_{1} topology on X is the discrete topology, which is also the only Hausdorff topology.)

From [1] we have: { T_{0} topologies on X } ↔ { relations on X that are reflexive, antisymmetric and transitive }. Relations that are reflexive, antisymmetric and transitive are known as “partial orders”. The correspondence is identical to that between topologies on X and preorders on X given above; it just happens that the relation is also antisymmetric if and only if the topology is T_{0}. We leave confirmation of this fact to the reader. Visually, we have a way to instantly tell whether a topology is T_{0} or not: T_{0} topologies correspond to directed graphs such that one cannot find two nodes with edges from each to the other. More prosaically, the graphs of T_{0} topologies don’t have double arrows between any two nodes. See Figures 1 and 2. Notice that any topology on X induces a T_{0} topological space (X)_{0} as follows. In the associated graph, take every pair of nodes that have two edges between them (in opposite directions), remove these two edges, and collapse the two nodes down to a single node. This yields the graph of a new topological space, which we denote (X)_{0}. Note that (X)_{0} is a T_{0} topological space on a different point set than X, unless X is already T_{0}; a perfect illustration of an identification space.

We can quickly deduce the following bound: X has at most 3^{n(n−1)/2} T_{0} topologies.

\underline{Proof}. For each of the n(n − 1)/2 pairs of nodes in the associated graph, there are 3 choices as to whether there should be one of the two kinds of directed edge between the pair, or whether there should be no edge at all.

2. More Topological Information from the Graph. Having learned how to identify open and closed subsets in our topology merely by inspection of the associated graph, we show how more subtle topological information is encoded in the graph. Graphs for T_{0} topologies can be streamlined to “Hasse diagrams”, as in Figures 2 and 5a. (To convert back from a Hasse diagram to a directed graph, insert an arrow on every line segment that points upward, and invoke transitivity as needed to add extra edges.) The following proposition can be understood purely from the viewpoint of Hasse diagrams.

\underline{Proposition 1}. Consider a fixed T_{0} topology on X. Let x ∈ X.

(a) {x} is open if and only if x is a maximal element in the partial order sense. The greatest element (if it exists) is also dense as a singleton set (and so is in each nonempty open set).

(b) {x} is closed if and only if x is a minimal element; in either case {x} is nowhere dense. The least element (if it exists) also must reside in each closed set.

(c) The collection of all maximal elements is an open set that is the smallest dense set: it is a subset of every dense set.

\underline{Partial Proof}. If x is maximal, then in the associated graph there are no edges with initial point x that have terminal points outside {x}; hence, {x} is open. If x is the greatest element, then by transitivity every element of X is in the closure of {x}, so {x} is dense. For some of the other facts given, one can use the following fact: for any subset C, x ∈ \overline{C} if and only if in the associated graph there is an edge from x to some element in C [to prove the implication, if not so, then intersect the open sets U_{i} around x that don’t contain c_{i}, for each c_{i} ∈ C, yielding an open set that contradicts that x ∈ \overline{C}; the converse is immediate].

The following can also be deduced simply from the graph, or rather Hasse diagram. Namely, a simple lower bound for the number of T_{0} topologies is 2^{(n+1)(n−1)/4} if n is odd, and 2^{n^{2}/4} if n is even.

\underline{Partial Proof}. In the case of n even, for instance, this is the number of all T_{0} topologies obtained by choosing n/2 elements to be “potential” maximal elements, and n/2 “potential” minimal elements; then there are n^{2}/4 ways to pair these potential maximal elements with the potential minimal elements, so 2^{n^{2}/4} possible choices for whether one decides to have an arrow from any one potential minimal element to any one potential maximal element.

As an illustration, combining this latest bound with our upper bound from page 4, we see that the number of T_{0} topologies on a set with 14 elements must lie between 2^{14^{2}/4} and 3^{14(14−1)/2}, or between 10^{14} and 10^{44}. The exact value from [4] is approximately 10^{23} (which is apparently the largest such value known). Improved asymptotic formulas appear in [2] and [8].

3. Adjacency Matrices and Topologies. First, we recall some basic ideas from graph theory. Any finite directed graph with n nodes, given in some fixed order, is equivalent to an n × n adjacency matrix M consisting of zeroes and ones, where M_{ij} = 1 if and only if there is an edge from node i to node j. Computations involving M use Boolean arithmetic. For a review of these concepts, and the proof of the following Proposition, see the Appendix.

\underline{Proposition 2}. Let M denote an n × n Boolean matrix, and I denote the usual identity matrix. Then M^{2} = M and M + I = M if and only if the graph (and, relation) associated to M is reflexive and transitive, i.e. if and only if M is the matrix associated to a finite topological space.

From now on, M will denote the n×n adjacency matrix for the graph associated to the topology on the finite space X. Then for T_{0} topologies, minimal elements are those x_{i} ∈ X such that their (ith) column in M has all zeroes except for a 1 in the ith spot, i.e. they have the minimal number of 1’s in their column. Maximal elements are those x_{j} ∈ X such that the jth row of M has all zeroes except for a single 1 in the jth spot, i.e. they have a maximal number of 0’s in their row. See Figure 2.

More generally, given an ordering of nodes, we can associate a unique row and a unique column vector for each subset S of X: namely put a 1 in the ith location in the vector if and only if x_{i} is in S. Then, for a general topological space X, we have the following.

\underline{Proposition 3}. Let r be the row vector corresponding to the subset R of X; let c be the column vector corresponding to the subset C of X. Then the row vector rM corresponds to the smallest open set containing R while Mc corresponds to the smallest closed set containing C.

\underline{Partial Proof}. Let v = rM and let V denote the set of points corresponding to v. Geometrically, V is the set of all endpoints (or terminal points) for directed edges that have their initial point in R. (This is clear from the definition of matrix multiplication and adjacency matrix, although it may take a moment’s reflection.) Thus, no edges can originate in V and end outside of V (else some point in R would have an edge ending outside of V). Hence, V must be open. Moreover, it is the smallest open set containing R; for if W were smaller, there would be an edge from some point in R outside W, i.e. an edge from a point inside W to a point outside W, which implies W would not be open.

\underline{Corollary 4}.

(a) The left “eigenvectors” or fixed points of M, i.e. vectors v such that vM = v, correspond exactly with the open sets in X (and the right “eigenvectors” correspond exactly with the closed sets).

(b) The collection of all open sets in X is exactly the collection of sets corresponding to the (Boolean) linear combinations of the row vectors of M, i.e. to the finite sums of the row vectors [the (Boolean) “row space”]. Similarly, the collection of finite sums of column vectors of M corresponds exactly to the collection of closed sets in the topology. The set of clopen sets (sets that are simultaneously open and closed) corresponds to intersection of the row and column space of M. See Figure 3.

In fact, one can recover the Hasse diagram from the adjacency matrix of a T_{0} topology. We’ve seen how to get the minimal and maximal elements: look for rows or columns with only one 1. To get the next level from the bottom in the Hasse diagram from the adjacency matrix, look for all elements with two 1’s in a column; for each such element, one can read off which minimal element is below it. Similarly use the rows for those one level from the top in the Hasse diagram. See Figure 2.

One can immediately tell from the matrix whether or not the topology is T_{0}.

\underline{Proposition 5}. The following are equivalent.

(a) X is T_{0}

(b) M has all distinct rows, i.e. no two identical rows.

(c) M has distinct columns.

For every familiar operation on matrices we perform on the adjacency matrix, we can ask what the topological implications are. For each question, we put the answer in brackets.

(1) Transposing the adjacency matrix M? [We get a new topology that interchanges all open sets and closed sets; this is equivalent to changing the direction of all edges in the associated graph. Compare with [12].]

(2) Taking the real-valued determinant of M? [One gets 1 if the associated topology is T_{0}; otherwise one gets 0. For a hint in the T_{0} case, order the points of the space so that a maximal element is listed first. Consider row reduction starting with the row associated with that maximal element. Consider the new T_{0} topology obtained when that maximal element is removed from the original topology, and consider how its adjacency matrix relates to M. For the non-T_{0} case, at least two rows of the matrix are identical.]

(3) Taking a product MN? [The resulting matrix is the adjacency matrix of some graph; this new graph is the “concatenation” of the two graphs (include an edge from a to b in the new graph if and only if there is a c such that there is an edge from a to c in the graph associated to M and an edge from c to b in the graph associated to N). While it is clear that the concatenation of two such reflexive graphs is reflexive, this new graph typically is not transitive (even in the case of two reflexive transitive graphs with three nodes each); hence the product does not directly correspond to a topology. (For an algebraic proof of reflexivity, M and N represent reflexive graphs, hence M + I = M and N + I = N; then MN = (M + I)(N + I) = MN + N + M + I; but MN + N = (M + I)N = MN, so the right side simplifies to MN +I.) A sufficient condition for when a concatenation of reflexive graphs leads to a topology is that the matrices commute: MN = NM, plus the reflexivity and transitivity properties of M and N, implies that MN = MN + I and that (MN)(MN) = MN. (Of course, the transitive closure of any such concatenation yields a unique topology.)]

We close this section with another way to arrive at a bound found earlier. An n × n Boolean matrix that represents a reflexive graph must have all 1’s on the main diagonal, but otherwise has no restriction on its entries. This means it has exactly n^{2} − n entries that can be arbitrarily chosen to be 0’s or 1’s, so there are exactly 2^{n(n−1)} different possible Boolean matrices representing reflexive graphs. Hence, 2^{n(n−1)} is an upper bound for the number of topologies on X, as obtained in section 1 above.

4. Bases for Finite Topologies. In any finite topology, there is a “minimal” basis, i.e. a collection of open sets that form a basis and that have to be in any basis. It can be constructed from the graph or from the adjacency matrix.

\underline{Proposition 6}. The minimal basis on a topological space X consists of the open sets represented by the rows of M.

\underline{Proof}. For given any point x_{i}, consider the smallest open set containing x_{i}, i.e. the points represented by the ith row of M. The collection of such open sets, coming from the rows of M, form the minimal basis. In general, one obtains a basis of |(X)_{0}| elements.

For T_{0} topologies, the minimal basis can also be obtained by taking all sets of the following form: for each point x, take the union of all chains containing x, then subtract the set of all y such that y < x.

5. Product Topologies. We now consider the product topology on the products of finitely many finite topologies. Let M_{X} denote the adjacency matrix for a finite topology on X. Note of course that M_{X} is not uniquely determined; a different ordering of the points in X will yield a different matrix, namely QM_{X}Q^{T} where Q is a permutation matrix. We have the following.

\underline{Proposition 7}.

(a) Let X and Y be finite topological spaces. Then (with respect to a suitable ordering of elements of X) the adjacency matrix for the product topology on X × Y is the tensor product of the adjacency matrices: M_{X×Y} = M_{X} ⊗ M_{Y}. (See Figure 4 for a reminder of what the tensor product A ⊗ B of two matrices A and B looks like; one replaces a_{ij} in A by a_{ij}B, i.e. one replaces the entry a_{ij} by the matrix a_{ij}B.)

(b) Visually, the Hasse diagram for the product of two T_{0} spaces is the “tensor product” of the Hasse diagrams; see Figure 5a.

How can we tell if a finite topology is a product topology? (Exclude the case where one of the factors is the trivial topology on a one–point set.) There is at least one obvious necessary condition: a product of two finite topological spaces obviously must have a composite number of elements, since |X × Y | = |X||Y |.

More can be said. The above proposition urges us to find (useful) necessary conditions for when a matrix is (similar to) the tensor product of two matrices. More specifically, we seek necessary conditions on an a × a matrix, A, consisting of 0’s and 1’s, for it to be of the form M ⊗N or more generally P (M ⊗N)P^{T}; here P is a permutation matrix and M and N are of dimension m×m and n×n respectively and only have 0’s and 1’s. Of course, thinking about how one constructs tensor products of matrices, a must be mn; but that is just saying that the space has a composite number of elements, which was already noted above. We mention a generalization, again obtained by thinking how tensor products are constructed.

\underline{Proposition 8}. Let K_{i} denote the number of 1’s in the ith row of a matrix K. Then if A = M ⊗ N or A = P (M ⊗ N)P^{T} where M and N are matrices whose entries are just 0’s and 1’s, the list of elements {A_{i}} must exactly coincide with the list {M_{j}N_{l}}. (And a similar statement can be made if one replaces “row” by “column”.)

We used the term “list”, not “set”, since repeated values are allowed. For instance, {A_{i}} is {1, 2, 2, 2, 4, 4, 3, 6, 6} for A given in Figure 4, while {M_{i}} is {1, 2, 3} and {N_{j}} is {1, 2, 2}. Proposition 8 is a nontrivial restriction on the A_{i}, giving a practical way to decide that some topologies can’t be product topologies. For instance, Figure 5b cannot be the Hasse diagram for a product topology since {A_{i}} = {1, 2, 2, 2, 4, 4, 3, 6, 4} cannot be of the form {M_{j}N_{l}} for nontrivial M and N. [For if X was a nontrivial product of two topological spaces, each factor space would have to have three elements each. Now since 18 isn’t listed in {A_{i}} and 1 is listed, either {M_{i}} or {N_{i}} must be {1, 3, 6}. But since 1, 2 and 4 are listed, the other collection must have the form {1, 2, 4}. But then the list would be {A_{i}} = {1, 3, 6, 2, 6, 12, 4, 12, 24}, which is not the correct list for Figure 5b.]

\underline{Corollary 9}.

(a) Let |K|_{1} = ∑ k_{ij}(= ∑ K_{i}) denote the number of 1’s appearing in a matrix K of 0’s and 1’s. Then |A|_{1}=|M|_{1}|N|_{1}.

(b) The number of rows in A having only one 1 must be the product of the number of rows in M and N having only one 1. (A similar statement holds for the columns of A, M and N respectively.)

A proof is immediate if one ponders tensor products of matrices. We note that (a) has the following geometric interpretation: the number of edges in the directed graph associated to A is the product of the number of edges in M’s graph and the number of edges in N’s graph. Also, note that (b) is the matrix analog of the statement: (x, y) is maximal in the product topology X × Y if and only if x is maximal in X and y is maximal in Y; and by considering columns instead of rows, (x, y) is minimal in the topology on X × Y if and only if x is minimal in X and y is minimal in Y. Note that we cannot say that any product topology must have a composite number of minimal and maximal elements, for its associated T_{0} topology, since the non–trivial exceptions are where one of the factor spaces has a least or a greatest element in its induced T_{0} topology.

6. Topologies on Spaces of Topologies. We can put a (T_{0}) topology on the space of topologies as follows, which is very natural from our viewpoint. First, consider the case where two topologies τ and σ satisfy the condition that all sets that lie in σ (i.e. that σ considers open) also lie in τ (i.e. are also considered to be open by τ). We will denote this by τ ≤ σ; one says that τ is “finer” than σ. Then note that the set T_{n} of all topologies on some fixed set X with n elements is naturally partial ordered under refinement (i.e., for τ, τ′ ∈ T_{n}, say τ ≤ τ′ if and only if τ is finer than τ′). That this is a partial order follows quickly; for instance, for transitivity if all τ_{3}–open sets are τ_{2}–open, and all τ_{2}–open sets are τ_{1}–open, then all τ_{3}–open sets are τ_{1}–open. An algebraic way of deducing transitivity will follow from

\underline{Proposition 10}. Let M_{i} denote the adjacency matrix for the graph associated to the topology τ_{i}. Then τ_{1} is finer than τ_{2} if and only if M_{2}M_{1} = M_{2}.

The proof is immediate: A set U open in τ_{2} is open in τ_{1} if and only if it is represented by a left “eigenvector” of M_{1}; and the rows of M_{2} comprise the minimal basis for τ_{2}.

This way of algebraically determining the partial ordering under fineness presents an amusing way to note for instance that the ordering is transitive: for if M_{3}M_{2} = M_{3} and M_{2}M_{1} = M_{2} then M_{3}M_{2}M_{1} = M_{3}M_{2} from the second equation, and so M_{3}M_{1} = M_{3} using the first.

Figure 6 depicts the case n = 2; the case n = 4 is considered in Figure 7, but see below for details.

The partial order on the collection of topologies on the set X yields a graph G_{n}, with one node corresponding to each topology, i.e. T_{n} yields a directed graph with |T_{n}| nodes. It therefore corresponds to a topology T_{n} on the set T_{n}! Note that T_{n} is T_{0} but not T_{1} (so nonmetrizable). We also note that since the graph G_{n} has a least element (the discrete topology is finer than all topologies) and a greatest element (the trivial topology is coarser than all topologies), there is exactly one “point” that is open as a singleton set and it in fact is dense in T_{n}; and there is exactly one point that is closed.

We introduce another partial ordering relevant to the space of finite topologies, now on the set of homeomorphism classes of topologies. Specifically, let X_{n} denote some fixed space with n elements. Then let T_{n}^{h} denote the set of all homeomorphism classes of topologies on the space X_{n}. Let τ_{1} and τ_{2} be topologies on X_{n}. Then define τ_{1} << τ_{2} if and only if τ_{1} is homeomorphic to a topology that is finer than τ_{2}. (The relation << is clearly well–defined on homeomorphism classes of topologies on X_{n}.) This relation could be expressed perhaps most readily in terms of the adjacency matrices; then τ_{1} << τ_{2} if and only if M_{2}(P M_{1}P^{T}) = M_{2} where P is some permutation matrix. Then we have the following.

\underline{Proposition 11}. << is a partial ordering on T_{n}^{h}.

\underline{Proof}. First, note that for a permutation matrix Q, QQ^{T} = I. Then transitivity holds since if (1) M_{2}(P M_{1}P^{T}) = M_{2} and (2) M_{3}(QM_{2}Q^{T}) = M_{3}, then from the first equation M_{3}QM_{2}Q^{T} QP M_{1}P^{T} = M_{3}QM_{2}, so applying the second equation yields M_{3}QP M_{1}P^{T} = M_{3}QM_{2}, hence, M_{3}QP M_{1}P^{T} Q^{T} = M_{3}QM_{2}Q^{T} which is M_{3} by the second equation once more; so τ_{1} << τ_{3}. Antisymmetry holds most readily by an elementary combinatorial argument: since τ_{1} is finer than a homeomorphic copy of τ_{2}, τ_{1} as a collection of sets consists of a (homeomorphic) copy of the open sets of τ_{2}, with possibly some additional sets; but τ_{1} could not contain more open sets than τ_{2}, by the same reasoning applied to τ_{2} and τ_{1}; therefore τ_{1} consists solely of a homeomorphic copy of the sets of τ_{2}.

This partial ordering on the set T_{n}^{h} induces a natural T_{0} (not T_{1}) topology T_{n}^{h} on the set T_{n}^{h}; i.e. T_{n}^{h} is a natural topology on the set of all homeomorphism classes on X_{n}. See Figure 7, where the Hasse diagram for the partial ordering on T_{4}^{h} is given; each node in the diagram corresponds to a homeomorphism class of a connected topology on X_{4}.

7. How Many? (Counts). It is surprisingly difficult to precisely count the numbers of topologies, numbers of T_{0} topologies, numbers of homeomorphism classes of topologies, numbers of homeomorphism classes of T_{0} topologies, and numbers of such connected topologies, for even small spaces. We used a computer to simply count the numbers of Boolean matrices that had the appropriate properties, as described in Propositions 2 and 5 and in the comments at the beginning of Section 5. (Note in passing that topologically connected components in a topology correspond to connected components in the graph; this fact was used to help count the number of connected topologies.) As in the previous section, let X_{n} denote a fixed set with n elements. Then see Table Ia for our results, for various values of n. Our values are not new [e.g. [13], and see [4] for tables up to n = 14 for (connected) (T_{0}) topologies].

In addition, for a given topology, one may wonder how many open sets it admits. While we gave some bounds for these quantities earlier, again for precise values we turned to a computer. One way to count the number of open sets in a given topology is to simply count all left “eigenvectors” of the associated adjacency matrix. Alternately, note that the total number of open sets for any (not necessarily T_{0}) topology is determined from the T_{0} topology it generates, so it suffices to know how many open sets T_{0} spaces have. Then Observation 12 below indicates how one can obtain all the open sets in a T_{0} topology from the associated Hasse diagram, and this method seemed the best way in practice to count the number of open sets. See Table Ib. In addition, the number of clopen sets (sets which are both closed and open) for some specific topologies is included in the table; the number of clopen sets in a given topology on X is exactly 2^{c} where c is the number of connected components of the space.

Given a Hasse diagram, the idea of the level of a node is easy to visualize (while somewhat awkward to state). For a Hasse diagram, a maximal element is in level 1; and recursively x is in level i + 1 if x is not in level i or less, but for some y in level i we have x < y, and for no z is it true that x < z < y. (Visually, x directly connects to an element of level i in the Hasse diagram.)

\underline{Observation 12}. In a T_{0} topology, one can recover the open sets from the Hasse diagram as follows. Beginning at the top of the diagram, the maximal elements comprise all open sets of 1 element. Pairing any two maximal elements, or adding an element from level two in the diagram to a maximal element yields all open sets of two elements, provided when one goes down to level two, none of those nodes spawn a tree upwards from it with it as a root since such trees form open sets. One continues in this manner, getting all open sets of three elements, etc.

(See Figures 1, 2, and 4. This observation was used to count the number of open sets in some finite topologies, yielding the results in Table Ib.) Lastly, of course each finite topology is compact, and one may wonder about the number of sets needed in an open cover.

\underline{Proposition 13}. Every open cover of X admits a finite subcover with at most |(X)_{0}| distinct elements; some finite topological spaces admit covers that require exactly this many elements in the subcover.

\underline{Partial Proof}. First observe that in any topology, an open set U is determined by its minimal elements: U is the set of all elements greater than or equal to its minimal elements (if one such element was omitted, the set would have an edge originating inside that terminated outside, hence would not be open). Thus, any cover requires at most m distinct elements where m is the number of minimal elements in (X)_{0}.

We close this section with a new enumeration problem, a conjecture, and a question. Once again, we let X_{n} denote some specific set with n elements (for simplicity one can assume X_{n} is {1, 2, …, n}). Any topology on X_{n} is trivially homeomorphic to a product topology, in a canonical way: X_{n} ≈ X_{n} × X_{1}. Define a topology τ on X_{n} to be “prime” if the topological space (X_{n}, τ) is not homeomorphic to a nontrivial product of topological spaces. Clearly if n is prime, then no matter what topology is placed on X_{n}, the topology must be prime.

However, if n isn’t prime, still some of the topologies on X_{n} may be prime. For n ≥ 2, define a topology τ on X_{n} to be “composite” if it isn’t prime, i.e. if (X_{n}, τ) can be expressed as a product of two or more nontrivial topological spaces. (The space with n = 1 points will not be considered prime nor composite.) We provide some values for the number of composite topologies on X_{n} for n ≤ 11 in Table II. It is possible that the number of prime and the number of composite topologies on X_{n} has not been considered before. We make the following conjecture.

\underline{Conjecture 14}. (“Unique factorization into primes holds for connected finite topological spaces.”) Let τ be a topology on X_{n} so that X_{n} is connected; let n ≥ 2, and let ≈ denote “homeomorphic to”. Assume (X, τ) ≈ P_{1} × P_{2} × ⋯ × P_{k} for some prime topological spaces P_{j} = (Y_{j}, τ_{j}). Then k is uniquely determined, and the collection of topological spaces is unique up to trivial reordering.

Note that since the conjecture discusses X_{n} up to homeomorphism, we are really identifying any prime topological space P_{j} with any space homeomorphic to it. Then Conjecture 14 is true for 2 ≤ n ≤ 11, as the reader can see by comparing the values in Table II (obtained by computer) with the values in Table Ia, as well as those in the electronic version of [13], available at

http://www.research.att.com/∼njas/sequences

We should point out that our original conjecture did not include the hypothesis that the space be connected. Apparently an earlier version of [1] (from 1940) included a weaker form of our original conjecture, namely for the T_{0} case; this led to Hashimoto’s counterexample published in 1948 in [6]. There, a T_{0} space with n = 63 points which has two distinct factorizations is given. A somewhat more general (T_{0}) counterexample is given in [15]. [See problem 8, posed on pages 154– 155 (although there is a misprint in 8b); and its solution, given on page 176.] These counterexamples necessarily consist of spaces that are not connected, since Hashimoto later showed in [7] that Conjecture 14 is true for all connected finite T_{0} topological spaces.

Finally, we ask the following question. Define τoπ(x) to be the total number of (homeomorphism classes of) prime topologies on all the spaces X_{1}, X_{2}, … X_{k} with k ≤ x. The notation is by analogy with the number theoretic prime–counting function π, wherein π(x) is the number of prime numbers less than or equal to x. To our knowledge, τoπ has not been discussed anywhere in the literature. A listing of its values for x ≤ 7 can now be constructed based on our new values in Table II and the values in the electronic version of [13]. By analogy with the prime number theorem in number theory, we ask: What are the asymptotics of τoπ(x)?

8. A Final Thought. This paper has dealt exclusively with topological spaces with only finitely many points. But topological spaces with infinitely many points naturally arise in our context as well. We leave the reader with one such infinite space to examine. Consider X, namely the space obtained by taking the cartesian product of ALL (homeomorphically distinct, say) finite topological spaces, equipping X with the product topology. What is it? We leave the following three facts as exercises: X is not T_{1}, hence not metrizable. It has cardinality ℝ as a point set. And the Cantor set appears as a certain quotient space. X somehow “contains” all information about all finite topologies. Surely there is something X has to tell us. (One could also contemplate, for example, the product of all prime topologies, i.e. all the finite topological spaces that cannot be expressed as a nontrivial product. Or the product of the connected finite topological spaces; etc.)

Appendix. In Boolean algebra, 1+1=1, and Boolean arithmetic with 0 and 1 admits the usual distributive, commutative and associative laws for multiplication and addition. There is no cancellation law, however; there are no additive inverses. Boolean multiplication of matrices proceeds just as usual (except that, whenever encountered, 1+1=1). All arithmetic operations involving matrices and vectors in this paper use Boolean arithmetic unless otherwise stated. Then the ij entry of M^{2} is 1 if and only if there is a path from node i to node j traversing two edges; and M + M^{2} + M^{3} + ⋯ + M^{n−1} has ij entry 1 exactly if there is some path from node i to node j. We now present the proof of Proposition 2, the fact about adjacency matrices that characterizes topologies.

\underline{Proof}. We first prove the implication.

(a) Reflexivity for the graph is equivalent to M + I = M (since m_{ii} = 1 if and only if m_{ii} + 1 = 1) while

(b) graph transitivity is equivalent to M + M^{2} + M^{3} + ⋯ + M^{n−1} = M (since graph transitivity is equivalent to the statement that there is some path from node i to node j if and only if there is an edge from node i to node j).

Now note that if the graph is reflexive, then by (a) M+I = M, hence M^{2}+M = M^{2}, M^{3} + M^{2} = M^{3}, etc, which would telescope the sum in (b). So the graph is reflexive and transitive if and only if M + I = M and M^{n−1} = M. On the one hand, if M^{2} = M, then (multiplying each side by M repeatedly) we see M to any positive integer power is M; hence the implication is true, and we have half the claim. On the other hand, if the graph is reflexive and transitive then we must have M +I = M by reflexivity (see (a) above), hence M^{2} +M = M^{2}; and M^{2} +M = M by transitivity (i.e. nodes connectable by a path of length 2 must be connectable by a path of length 1); together these imply M^{2} = M, and the converse is proved.

The author thanks Richard Stanley for helpful discussion on the original form of the conjecture, who also pointed out the particular relevant material in [15]; and Jimmie Lawson, for pointing out reference [12].

n  Number of Number of Number of Number of Number of Number of
topologies T_{0} top. homeom. homeom. connected connected
for X_{n}  for X_{n} classes for classes for top. (up T_{0} top.
X_{n}  T_{0} top. to hom.) (up to hom.)
on X_{n}  for X_{n}  for X_{n}
1  1  1  1  1  1  1
2  4  3  3  2  2  1
3  29  19  9  5  6  3
4  355  219  33  16  21  10
5  6942  4231  139  63  94  44
6  209527  etc.

(for other values, see [4] or the electronic version of [13], at http://www.research.att.com/∼njas/sequences)

Table Ia: Counts

Homeomorphism class Number of  Homeomorphism class Number of
label ^{∗}  open, clopen sets  label ^{∗}  open, clopen sets
0  16, 16  1  12, 8
3  10, 4  7  9, 2
18  10, 4  19  8, 4
20  9, 4  22  8, 2
23  7, 2  54  7, 2
55  6, 2  292  9, 2
293  7, 2  295  6, 2
310  6, 2  311  5, 2

Table Ib: Number of open sets and clopen sets in T_{0} homeomorphism classes on X_{4}, a space with 4 elements.

∗ When the label is expressed base two, it yields the entries in the adjacency matrix starting with row 1 and ending with row 4, skipping over the diagonal entries since they must always be 1. For the connected topologies here (those with exactly 2 clopen sets), Figure 7 shows what they look like.

n  Number of Number of Number of Number of Number of Number of
composite composite homeom. homeom. composite composite
topologies T_{0} top. classes for classes for connected connected
for X_{n}  for X_{n} comp. top. comp. T_{0} top. (up T_{0} top.
for X_{n} top. for X_{n} to hom.) (up to hom.)
for X_{n}  for X_{n}
2  0  0  0  0  0  0
3  0  0  0  0  0  0
4  35  25  6  3  3  1
5  0  0  0  0  0  0
6  3767  2641  27  10  12  3
7  0  0  0  0  0  0
8  —  —  91  30  40  10
9  —  —  45  15  21  6
10  —  —  417  126  188  44
11  0  0  0  0  0  0

Table II: Counts for numbers of composite topologies Missing data values are not known by the author at this time. The corresponding values for number of prime topologies, number of prime T_{0} topologies, etc., are obtained simply by subtracting the values from Table II from those in Table Ia.

\underline{References}

1. G. Birkhoff, Lattice Theory, American Mathematical Society, Providence, RI, 1967.

2. G. Brightwell, H. Proemel, and A. Steger, “The Average Number of Linear Extensions of a Partial Order,” (preprint).

3. J. W. Evans, F. Harary, and M. S. Lynn, “On the Computer Enumeration of Finite Topologies,” Communications of the ACM, 10 (1967), 295–313.

4. M. Erne and K. Stege, “Counting Finite Posets and Topologies,” Order, 8 (1991), 247–265.

5. F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York, 1973.

6. J. Hashimoto, “On the Product Decompositions of Partially Ordered Sets,” Mathematica Japonicae, 1 (1948), 120–123.

7. J. Hashimoto, “On Direct Product Decomposition of Partially Ordered Sets,” Annals of Mathematics, 54 (1951), 315–318.

8. D. Kleitman and B. Rothschild, “Asymptotic Enumeration of Partial Orders on a Finite Set,” Transactions of the American Mathematical Society, 205 (1971), 205–220.

9. V. Krishnamurthy, “On the Number of Topologies on a Finite Set,” American Mathematical Monthly, 73 (1966), 154–157.

10. J. Munkres, Topology – A First Course, Prentice–Hall, Inc. Englewood Cliffs, NJ, 1975.

11. R. A. Razen, “Transversals and Finite Topologies,” Combinatorial Mathematics, Springer–Verlag, New York, 1978.

12. H. Sharp, Jr., “Quasiorderings and Topologies on Finite Sets,” Proceedings of the American Mathematical Society, 17 (1966), 1344–1349.

13. N. Sloane and S. Plouffe, Encyclopedia of Integer Sequences, Academic Press, San Diego, CA, 1995.

14. R. Stanley, “On the Number of Open Sets of Finite Topologies,” Journal of Combinatorial Theory (Series A), 10 (1971), 74–79.

15. R. Stanley, Enumerative Combinatorics, Volume I, Cambridge University Press, Cambridge, UK, 1997.

Rick Kreminski Department of Mathematics Texas A & M University - Commerce Commerce, TX 75429 email: kremin@boisdarc.tamu-commerce.edu

Figure 1.

The open sets are {x1, x2}, {x2}, {x2, x3, x4}, {x1, x2, x3, x4} and ∅.

[ \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} ]

Figure 2.

Directed graph for T_{0} topology, Hasse diagram, and adjacency matrix.

[ 1 1 0 0 ] [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix} ] = [ 1 1 0 0 ] .

Figure 3a.

[ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 0 \\ 1 \\ 1 \end{matrix} ] = [ \begin{matrix}1 \\ 0 \\ 1 \\ 1 \end{matrix} ] .

Figure 3b.

Boolean multiplication used. Open set in (3a) is {x1, x2}; closed set in (3b) is {x1, x3, x4} using the topology from Figure 1.

[ \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ] ⊗ [ \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ]

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \end{matrix} ] .

Figure 4.

Product topology of X × Y; tensor product of the two

associated graphs; tensor product of the adjacency matrices, with respect to the basis {x1y1, x1y2, x1y3,

x2y1, x2y2, x2y3, x3y1, x3y2, x3y3}.

Figure 5a.

Tensor product of the Hasse diagrams corresponding to the T_{0} topologies in Figure 4.

Figure 5b.

Hasse diagram for a T_{0} topology on a space with 9 points. Can this be a product topology? The adjacency

matrix is identical to that in Figure 4 except for the final row, which would be identical to the 6th row.

[ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] = [ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ]

[ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ] ≠ [ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] .

Figure 6a. Figure 6b and Figure 6c.

The graph G_{2} and Hasse diagram for T_{2}.

Topology on T_{2} is {{t1}, {t1, t2}, {t1, t3}, {t1, t2, t3}, {t1, t2, t3, t4}, ∅}.

Figure 7.

Hasse diagram for the topology on the space of homeomorphism classes on a set with 4 elements.

Each individual Hasse diagram represents a homeomorphism class of topologies; each class’ label from Table 1b is included.