Order-couniversality of the complete infinitary tree: an application of zero-divisor graphs. (English) Zbl 1498.13017
The paper completely classifies \(\mathfrak{S}\)-couniversal posets, where \(\mathfrak{S}\) refers the class of countably infinite bounded partially ordered sets \(P\) (with minimum and maximum elements 0 and 1, respectively) such that \(x\) has infinitely many immediate predecessors and only finitely many upper bounds for every \(x \in P \backslash\{0\}\).
The paper includes some natural examples of such posets. For example, consider a poset created by adding 0 to the countable downward-oriented rooted tree \(\mathcal{T}\) such that every node has infinitely many children. The ideal-lattice of the ring of integers \(\mathbb{Z}\) is another illustration.
Given a class \(\mathcal{K}\) of partially ordered sets, a poset \(P \in \mathcal{K}\) is said to be \(\mathcal{K}\)-couniversal if for every \(Q \in \mathcal{K}\) there exists a bijective poset-homomorphism \(\varphi: P \rightarrow Q ;\) that is, \(\varphi\) is bijective, and if \(x \leq_{P} y\) then \(\varphi(x) \leq_Q \varphi(y)\).
Clearly, a \(\mathcal{K}\)-couniversal poset exists only if the members of \(\mathcal{K}\) have equal cardinalities, but the converse can fail.
In this paper, the zero-divisor graphs of posets are used to classify \(\mathfrak{S}\)-couniversal posets. By the zero-divisor graph \(\Gamma(P)\) of a poset \(P\), we mean the graph whose vertices are the elements are nonzero zero-divisors of \(P\) such that two distinct vertices \(x\) and \(y\) are adjacent if and only if the lower cone of \(\{x,y\}\) contains only the least element 0.
The following is the main result of the paper.
{Theorem:} Let \(\mathcal{S}\) be the set of nonempty finite sequences of positive integers under the partial order defined by \(\sigma \leq \tau\) if and only if \(\sigma\) is an extension of \(\tau\), together with least and greatest elements \(\mathbf{0}\) and \(\mathbf{1}\), respectively. If \(P \in \mathfrak{S}\), then \(P\) is \(\mathfrak{S}\)-couniversal if and only if \(Z(P)=P \backslash\{1\}\) and \(\Gamma(\mathcal{S})\) is (isomorphic to) a spanning subgraph of \(\Gamma(P)\).
The paper includes some natural examples of such posets. For example, consider a poset created by adding 0 to the countable downward-oriented rooted tree \(\mathcal{T}\) such that every node has infinitely many children. The ideal-lattice of the ring of integers \(\mathbb{Z}\) is another illustration.
Given a class \(\mathcal{K}\) of partially ordered sets, a poset \(P \in \mathcal{K}\) is said to be \(\mathcal{K}\)-couniversal if for every \(Q \in \mathcal{K}\) there exists a bijective poset-homomorphism \(\varphi: P \rightarrow Q ;\) that is, \(\varphi\) is bijective, and if \(x \leq_{P} y\) then \(\varphi(x) \leq_Q \varphi(y)\).
Clearly, a \(\mathcal{K}\)-couniversal poset exists only if the members of \(\mathcal{K}\) have equal cardinalities, but the converse can fail.
In this paper, the zero-divisor graphs of posets are used to classify \(\mathfrak{S}\)-couniversal posets. By the zero-divisor graph \(\Gamma(P)\) of a poset \(P\), we mean the graph whose vertices are the elements are nonzero zero-divisors of \(P\) such that two distinct vertices \(x\) and \(y\) are adjacent if and only if the lower cone of \(\{x,y\}\) contains only the least element 0.
The following is the main result of the paper.
{Theorem:} Let \(\mathcal{S}\) be the set of nonempty finite sequences of positive integers under the partial order defined by \(\sigma \leq \tau\) if and only if \(\sigma\) is an extension of \(\tau\), together with least and greatest elements \(\mathbf{0}\) and \(\mathbf{1}\), respectively. If \(P \in \mathfrak{S}\), then \(P\) is \(\mathfrak{S}\)-couniversal if and only if \(Z(P)=P \backslash\{1\}\) and \(\Gamma(\mathcal{S})\) is (isomorphic to) a spanning subgraph of \(\Gamma(P)\).
Reviewer: Vinayak Joshi (Pune)
MSC:
| 13A70 | General commutative ring theory and combinatorics (zero-divisor graphs, annihilating-ideal graphs, etc.) |
| 06A06 | Partial orders, general |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Akbari, S.; Mohammadian, A., On the zero-divisor graph of a commutative ring, J. Algebra, 274, 847-855 (2004) · Zbl 1085.13011 |
| [2] | Anderson, D. F.; Frazier, A.; Lauve, A.; Livingston, P. S., The Zero-Divisor Graph of a Commutative Ring, II, Lecture Notes in Pure and Applied Mathematics, vol. 220, 61-72 (2001), Marcel Dekker: Marcel Dekker New York, Basel · Zbl 1035.13004 |
| [3] | Anderson, D. F.; LaGrange, J. D., Commutative Boolean monoids, reduced rings, and the compressed zero-divisor graph, J. Pure Appl. Algebra, 216, 1626-1636 (2012) · Zbl 1254.13003 |
| [4] | Anderson, D. F.; Livingston, P. S., The zero-divisor graph of a commutative ring, J. Algebra, 217, 434-447 (1999) · Zbl 0941.05062 |
| [5] | Beck, I., Coloring of commutative rings, J. Algebra, 116, 208-226 (1988) · Zbl 0654.13001 |
| [6] | Halaš, R.; Jukl, M., On Beck’s coloring of posets, Discrete Math., 309, 4584-4589 (2009) · Zbl 1190.06001 |
| [7] | Halter-Koch, F., Ideal Systems: An Introduction to Multiplicative Ideal Theory (1998), Marcel-Dekker: Marcel-Dekker New York · Zbl 0953.13001 |
| [8] | Hedrlín, Z., On universal partly ordered sets and classes, J. Algebra, 11, 503-509 (1969) · Zbl 0209.01602 |
| [9] | Hubička, J.; Nešetřil, J., Some examples of universal and generic partial orders, (Grohe, M.; Makowsky, J. A., Model Theoretic Methods in Finite Combinatorics (2011), American Mathematical Society), 296-318 |
| [10] | Hubička, J.; Nešetřil, J., Universal partial order represented by means of oriented trees and other simple graphs, Eur. J. Comb., 26, 5, 765-778 (2005) · Zbl 1060.05092 |
| [11] | Johnston, J. B., Universal infinite partially ordered sets, Proc. Am. Math. Soc., 7, 507-514 (1956) · Zbl 0071.05003 |
| [12] | Joshi, V.; Khiste, A., The zero divisor graphs of Boolean posets, Math. Slovaca, 64, 511-519 (2014) · Zbl 1349.05188 |
| [13] | Kukiela, M., Reversible and bijectively related posets, Order, 26, 119-124 (2009) · Zbl 1178.06002 |
| [14] | LaGrange, J. D., Annihilators in zero-divisor graphs of semilattices and reduced commutative semigroups, J. Pure Appl. Algebra, 220, 2955-2964 (2016) · Zbl 1332.05070 |
| [15] | LaGrange, J. D., Complemented zero-divisor graphs and Boolean rings, J. Algebra, 315, 600-611 (2007) · Zbl 1133.13005 |
| [16] | LaGrange, J. D.; Roy, K. A., Poset graphs and the lattice of graph annihilators, Discrete Math., 313, 10, 1053-1062 (2013) · Zbl 1261.05041 |
| [17] | Lu, D.; Wu, T., The zero-divisor graphs which are uniquely determined by neighborhoods, Commun. Algebra, 35, 3855-3864 (2007) · Zbl 1131.13005 |
| [18] | Lu, D.; Wu, T., The zero-divisor graphs of posets and an application to semigroups, Graphs Comb., 26, 793-804 (2010) · Zbl 1223.05115 |
| [19] | Mohammadian, A., On zero-divisor graphs of Boolean rings, Pac. J. Math., 251, 375-383 (2011) · Zbl 1225.05127 |
| [20] | Pultr, A.; Trnková, V., Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories (1980), North-Holland · Zbl 0418.18004 |
| [21] | Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Trans. Am. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031 |
| [22] | Tavakkoli, M.; Saeid, A. B.; Poursalavati, N. S., Classification of posets using zero-divisor graphs, Math. Slovaca, 68, 21-32 (2018) · Zbl 1473.05130 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
