phone +7 (3412) 91 60 92

Archive of Issues

Iraq; Russia Al Diwaniyah; Izhevsk
Section Mathematics
Title The graph of reflexive-transitive relations and the graph of finite topologies
Author(-s) Al' Dzhabri Kh.Sh.ab
Affiliations Udmurt State Universitya, University of Al-Qadisiyahb
Abstract 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
UDC 519.175, 519.115.5
MSC 05C30
DOI 10.20537/vm150101
Received 12 November 2014
Language Russian
Citation Al' Dzhabri Kh.Sh. The graph of reflexive-transitive relations and the graph of finite topologies, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 1, pp. 3-11.
  1. Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of partial orders, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, pp. 3-12 (in Russian).
  2. Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsional'nogo analiza (Elements of theory of functions and functional analysis), Moscow: Nauka, 1981, 544 p.
  3. Aigner M. Combinatorial theory, Berlin-Heidelberg-New York: Springer-Verlag, 1979, 492 p. Translated under the title Kombinatornaya teoriya, Moscow: Mir, 1982, 558 p.
  4. Ore O. Theory of graphs, Providence: Amer. Math. Soc. Colloq. Publ., 1962, vol. 18, 270 p. Translated under the title Teoriya grafov, Moscow: Nauka, 1980, 336 p.
  5. Harary F., Palmer E. Graphical enumeration, New York-London: Academic Press, 1973, 272 p. Translated under the title Perechislenie grafov, Moscow: Mir, 1977, 324 p.
  6. Comtet L. Recouvrements, bases de filtre et topologies d’un ensemble fini, C. R. Acad. Sci., 1966, vol. AB262, pp. A1091-A1094 (in French).
  7. Evans J.W., Harary F., Lynn M.S. On the computer enumeration of finite topologies, Comm. ACM, 1967, vol. 10, pp. 295-297.
  8. Gupta H. Number of topologies on a finite set, Res. Bull. Panjab. Univ. (N.S.), 1968, vol. 19, pp. 231-241.
Full text
Next article >>