Geodesic
The graph of reflexive-transitive relations and the graph of finite topologies
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 25 (2015) no. 1, pp. 3-11 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Any binary relation $\sigma\subseteq X^2$ (where $X$ is an arbitrary set) generates on the set $X^2$ a characteristic function: if $(x,y)\in\sigma$, then $\sigma(x,y)=1$, otherwise $\sigma(x,y)=0$. In terms of characteristic functions we introduce on the set of all binary relations of the set $X$ the concept of a binary reflexive relation of adjacency and determine an algebraic system consisting of all binary relations of the set and of all unordered pairs of various adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs”). It is shown that if $\sigma$ and $\tau$ are adjacent relations then $\sigma$ is a reflexive-transitive relation if and only if $\tau$ is a reflexive-transitive relation. Several structure features of the graph $G(X)$ of reflexive-transitive relations are investigated. In particular, if $X$ consists of $n$ elements, and $T_0(n)$ is the number of labeled $T_0$-topologies defined on the set $X$, then the number of connected components is equal to $\sum_{m=1}^nS(n,m)T_0(m-1)$, where $S(n,m)$ are Stirling numbers of second kind. (It is well known that the number of vertices in a graph $G(X)$ is equal to $\sum_{m=1}^nS(n,m)T_0(m)$.)
Keywords: graph, reflexive-transitive relation, finite topology. 
@article{VUU_2015_25_1_a0,
     author = {Kh. Sh. Al' Dzhabri},
     title = {The graph of reflexive-transitive relations and the graph of finite topologies},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {3--11},
     year = {2015},
     volume = {25},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2015_25_1_a0/}
}
TY  - JOUR
AU  - Kh. Sh. Al' Dzhabri
TI  - The graph of reflexive-transitive relations and the graph of finite topologies
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2015
SP  - 3
EP  - 11
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2015_25_1_a0/
LA  - ru
ID  - VUU_2015_25_1_a0
ER  - 
%0 Journal Article
%A Kh. Sh. Al' Dzhabri
%T The graph of reflexive-transitive relations and the graph of finite topologies
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2015
%P 3-11
%V 25
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2015_25_1_a0/
%G ru
%F VUU_2015_25_1_a0
Kh. Sh. Al' Dzhabri. The graph of reflexive-transitive relations and the graph of finite topologies. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 25 (2015) no. 1, pp. 3-11. http://geodesic.mathdoc.fr/item/VUU_2015_25_1_a0/

[1] Al' Dzhabri Kh. Sh., Rodionov V. I., “The graph of partial orders”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, 3–12 (in Russian) | Zbl

[2] Kolmogorov A. N., Fomin S. V., Elements of theory of functions and functional analysis, Nauka, Moscow, 1981, 544 pp. | MR

[3] Aigner M., Combinatorial theory, Springer-Verlag, Berlin–Heidelberg–New York, 1979, 492 pp. | MR | MR | Zbl

[4] Ore O., Theory of graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, 1962, 270 pp. | MR | MR | Zbl

[5] Harary F., Palmer E., Graphical enumeration, Academic Press, New York–London, 1973, 272 pp. | MR | MR | Zbl

[6] Comtet L., “Recouvrements, bases de filtre et topologies d'un ensemble fini”, C. R. Acad. Sci. Sér. A–B, 262 (1966), A1091–A1094 | MR

[7] Evans J. W., Harary F., Lynn M. S., “On the computer enumeration of finite topologies”, Comm. ACM, 10 (1967), 295–297 | DOI | Zbl

[8] Gupta H., “Number of topologies on a finite set”, Res. Bull. Panjab. Univ. (N.S.), 19 (1968), 231–241 | MR | Zbl