This article is cited in
6 papers
MATHEMATICS
The graph of partial orders
Kh. Sh. Al' Dzhabri,
V. I. Rodionov Udmurt State University, ul. Universitetskaya, 1, Izhevsk, 426034, Russia
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(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.
Keywords:
binary relation, graph, partial order, finite topology.
UDC:
519.175+519.115.5
MSC: 05C30 Received: 13.08.2013