Section

Mathematics

Title

The graph of partial orders

Author(s)

Al' Dzhabri Kh.Sh.^{a},
Rodionov V.I.^{a}

Affiliations

Udmurt State University^{a}

Abstract

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(n1).$
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.

Keywords

binary relation, graph, partial order, finite topology

UDC

519.175, 519.115.5

MSC

05C30

DOI

10.20537/vm130401

Received

13 August 2013

Language

Russian

Citation

Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of partial orders, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, issue 4, pp. 312.

References

 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.
 Harary F., Palmer E. Graphical enumeration, New YorkLondon: Academic Press, 1973, 272 p. Translated under the title Perechislenie grafov, Moscow: Mir, 1977, 324 p.
 Rodionov V.I. A relation in finite topologies, Journal of Soviet Mathematics, 1984, vol. 24, pp. 458460.
 Erne M. On the cardinalities of finite topologies and the number of antichains in partially ordered sets, Discrete Mathematics, 1981, vol. 35, pp. 119133.

Full text

