  RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013, Issue 4, Pages 3–12 (Mi vuu396) 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. Full text: PDF file (235 kB) References: PDF file   HTML file
UDC: 519.175+519.115.5
MSC: 05C30

Citation: Kh. Sh. Al' Dzhabri, V. I. Rodionov, “The graph of partial orders”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2013, no. 4, 3–12 Citation in format AMSBIB
\Bibitem{Al Rod13} \by Kh.~Sh.~Al' Dzhabri, V.~I.~Rodionov \paper The graph of partial orders \jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki \yr 2013 \issue 4 \pages 3--12 \mathnet{http://mi.mathnet.ru/vuu396} 

• http://mi.mathnet.ru/eng/vuu396
• http://mi.mathnet.ru/eng/vuu/y2013/i4/p3

 SHARE:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Kh. Sh. Al Dzhabri, “Graf refleksivno-tranzitivnykh otnoshenii i graf konechnykh topologii”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 25:1 (2015), 3–11  2. Kh. Sh. Al Dzhabri, V. I. Rodionov, “Graf atsiklicheskikh orgrafov”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 25:4 (2015), 441–452  3. V. I. Rodionov, “O perechislenii chastichnykh poryadkov, opredelennykh na konechnom mnozhestve”, Sib. elektron. matem. izv., 13 (2016), 318–330  4. Kh. Sh. Al Dzhabri, V. I. Rodionov, “Ob opornykh mnozhestvakh atsiklicheskikh i tranzitivnykh orientirovannykh grafov”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 27:2 (2017), 153–161   • Number of views: This page: 234 Full text: 61 References: 44 First page: 1 Contact us: math-net2020_04 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020