An enumeration of distinct and non-isomorphic functional quasi-order relations (Q2166292): Difference between revisions

Motivated by the seminal paper of \textit{P. Alexandroff} [Rec. Math. Moscou, n. Ser. 2, 501--519 (1937; JFM 63.1163.01)], the author studies a link between functional quasi-orders, digraphs and Alexandroff topologies, which leads to providing the generating functions that are associated to orbit-equivalent and orbit-isomorphic functional digraphs. These are results related to the problem of enumerating (i) the number of distinct functional quasi orders and (ii) the number of non isomorphic functional quasi orders, which are formed from a point set. If \(X\) is a finite \(n\)-set, then the number of binary relations on \(X\) is \(2^{n^2}\), the number of reflexive relations is \(2^{n(n-1)}\), the number of antisymmetric relations is \(2^n 3^{n(n-1)/2}\), the number of total orders is \(n!\) and the number of total quasi orders is the ordered Bell number \(\sum_{k=0}^n \binom{n}{k}\), where \(\binom{n}{k}\) is the Stirling number of second kind. The problem of counting the number of quasi orders \(Q_n\) remains unsolved, without any simple formula being known, due to the complexity of counting the number of non homeomorphic topologies (unlabeled case) or of \(Q_n\). One way of tackling this problem is to link monoid actions with Alexandroff topologies. In this paper, the author builds the generating function for distinct non-isomorphic functional quasi-order relations, thus contributing to the above mentioned problem.