Section
|
Mathematics
|
Title
|
The graph of partial orders
|
Author(-s)
|
Al' Dzhabri Kh.Sh.a,
Rodionov V.I.a
|
Affiliations
|
Udmurt State Universitya
|
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
|
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. 3-12.
|
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 York-London: 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. 458-460.
- Erne M. On the cardinalities of finite topologies and the number of antichains in partially ordered sets, Discrete Mathematics, 1981, vol. 35, pp. 119-133.
|
Full text
|
|