Counting finite topologies
Technion, Eldar Fischer, Johann A. Makowsky, Technion · Enumerative Combinatorics and Applications · 2024
A finite topology T = (A, T ) consists of a finite set A together with a family T of subsets of A, the open sets, satisfying the axioms of a topology.T φ (n) is the number of distinct topolgies T of subsets of [n] which satisfy φ, where φ is a property of topologies expressible in TMSOL, topological monadic second order logic.A sequence s(n) of integers is C-finite if it satisfies a linear recurrence relation with constant coefficients.It is MC-finite of for every modulus m the sequence s m (n) = s(n) (mod m) satisfies a linear recurrence relation with constant coefficients depending on m.In general T φ (n) is not C-finite, because it grows too fast.In this paper we show that T φ (n) is MC-finite for every φ ∈ TMSOL.We also show that this is still true for TCMSOL, the extensions of TMSOL with modular counting quantifiers.