The graph of partial orders

Kh. Sh. Al' Dzhabri   ; V. I. Rodionov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 4 (2013), pp. 3-12

Résumé

Any binary relation $\sigma\subseteq X^2$ (where $X$ is an arbitrary set) generates a characteristic function on the set $X^2$: if $(x,y)\in\sigma$, then $\sigma(x,y)=1$, otherwise $\sigma(x,y)=0$. In terms of characteristic functions on the set of all binary relations of the set $X$ we introduced the concept of a binary reflexive relation of adjacency and determined the algebraic system consisting of all binary relations of a set and of all unordered pairs of various adjacent binary relations. If $X$ is finite set then this algebraic system is a graph (“a graph of graphs”). It is shown that if $\sigma$ and $\tau$ are adjacent relations then $\sigma$ is a partial order if and only if $\tau$ is a partial order. We investigated some features of the structure of the graph $G(X)$ of partial orders. 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 vertices in a graph $G(X)$ is $T_0(n)$, and the number of connected components is $T_0(n-1)$. For any partial order $\sigma$ there is defined the notion of its support set $S(\sigma)$, which is some subset of $X$. If $X$ is finite set, and partial orders $\sigma$ and $\tau$ belong to the same connected component of the graph $G(X)$, then the equality $S(\sigma)=S(\tau)$ holds if and only if $\sigma=\tau$. It is shown that in each connected component of the graph $G(X)$ the union of support sets of its elements is a specific partially ordered set with respect to natural inclusion relation of sets.

Détail

Keywords: binary relation, graph, partial order, finite topology.

Bibliographie

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

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

[3] Rodionov V. I., “A relation in finite topologies”, Journal of Soviet Mathematics, 24 (1984), 458–460 | DOI | MR | Zbl | Zbl

[4] Erne M., “On the cardinalities of finite topologies and the number of antichains in partially ordered sets”, Discrete Mathematics, 35 (1981), 119–133 | DOI | MR | Zbl