×

zbMATH — the first resource for mathematics

Covering graphs and subdirect decompositions of partially ordered sets. (English) Zbl 0603.06001
The covering graph C(\({\mathcal L})\) of a partially ordered set (poset) \({\mathcal L}=(L,\leq)\) is defined to be the undirected graph whose edges are those pairs (a,b) of L for which either a covers b or vice versa and whose vertices are the elements of L. All posets \({\mathcal L}\) dealt with in the present paper are assumed to be almost discrete, i.e. whenever a,b\(\in L\), \(a<b\), then there are elements \(a_ 0,a_ 1,...,a_ n\in L\) such that \(a_ 0=a\), \(a_ n=b\) and \(a_ i\) covers \(a_{i-1}\), \(i=1,2,...,n\). Let \(\{\) \({\mathcal L}_ i\}_{i\in I}\) be a system of posets. By \(\prod_{i\in I}{\mathcal L}_ i={\mathcal L}\) or (sub)\(\prod_{i\in I}{\mathcal L}_ i\) there is denoted the direct or subdirect product of \({\mathcal L}_ i\), \(i\in I\), respectively. An isomorphism \(\phi\) of a poset \({\mathcal L}'\) into \({\mathcal L}\) such that \(\phi\) (\({\mathcal L}')=(sub)\prod_{i\in I}{\mathcal L}_ i\) is said to be a subdirect product representation of \({\mathcal L}'\). The subdirect product representation \(\phi\) of \({\mathcal L}'\) is said to induce a subdirect product representation of the graph C(\({\mathcal L}')\) if \(\phi\) : C(\({\mathcal L}')\to \prod_{i\in I}C({\mathcal L}_ i)\) is a subdirect product representation of the graph C(\({\mathcal L}')\). Analogous notions and notations are defined for graphs. Let us have a subdirect decomposition \(\phi\) : C(\({\mathcal L})\to (sub)\prod_{i\in I}{\mathcal G}_ i\) of the covering graph C(\({\mathcal L})\). Then the condition that (\(\alpha)\phi\) induces a subdirect decomposition of \({\mathcal L}\) need not be valid in general. The main result of the present paper is the statement that the following condition (\(\beta)\) is necessary for (\(\alpha)\) to be valid: (\(\beta)\) If K is a saturated subset of L such that \({\mathcal K}=(K,\leq)\) is isomorphic to \({\mathcal L}_ 1\), then there is \(i\in I\) such that \(\phi_ j(K)=1\) for each \(j\in I\setminus \{i\}\). (\({\mathcal L}_ 1\) is a poset with four elements \(a_ 1,a_ 2,b_ 1,b_ 2\) such that \(a_ i\) is covered by \(b_ j\) \((i,j=1,2)\) and there are no other covering relations in \({\mathcal L}_ 1.)\) Another setting of this theorem is the following: Let \(\psi\) be a subdirect product representation of the graph C(\({\mathcal L}')\). If \(\psi\) induces a subdirect product representation of \({\mathcal L}'\), then the condition (\(\beta)\) is fulfilled. If, especially, \({\mathcal L}'\) is connected and \(\psi\) is a weak direct product (or direct product) representation of C(\({\mathcal L}')\), then \(\psi\) induces a weak direct product (or direct product) representation of \({\mathcal L}'\) iff the condition (\(\beta)\) holds. If \({\mathcal L}\) is a semilattice and \(\psi\) as in the preceding proposition, then the condition (\(\beta)\) is valid. Some counterexamples complete the paper.
Reviewer: F.Šik

MSC:
06A06 Partial orders, general
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] BIRKHOFF G.: Some applications of universal algebra. Colloquia Math. Soc. J. Bolyai 29, Universal algebra (Esztergom 1977), North Holland. Amsterdam 1982, 107-128.
[2] GEDEONOVÁ E.: The orientability of the direct product of graphs. Math. Slovaca 31, 1981, 71-78.
[3] JAKUBÍK J.: О графичєском изоморфизмє структур. Чєхослов. мат. ж. 4, 1954, 131-141.
[4] JAKUBÍK J.: Weak product decompositions of discrete lattices. Czechoslov. Math. J. 21, 1971, 399-412. · Zbl 0224.06003
[5] JAKUBÍK J.: Weak product decompositions of partially ordered sets. Colloquium math. 25, 1972, 13-26.
[6] JAKUBÍK J.: On isomorphism of graphs of lattices. Czechoslov. Math. J. 35, 1985, 188-200. · Zbl 0575.06004
[7] JAKUBÍK J.: On lattices determined up to isomorphisms by their graphs. Czechoslov. Math. J. 34, 1984, 305-314. · Zbl 0557.06004
[8] JAKUBÍK J.: On weak direct decompositions of lattices and graphs. Czechoslov. Math. J. 35, 1985, 269-277. · Zbl 0576.06006
[9] ЯКУБИК Я., КОЛИБИАР М.: О нскотормх свойствах пар сгрукгур. Чєхослов. мат. ж. 4, 1954, 1-27.
[10] KOLIBIAR M.: Über direkte Produkte von Relativen. Acta Fac. Rer. Nat. Univ. Comen. 10, 1965, 1-9. · Zbl 0136.26002
[11] MILLER D. J.: Weak cartesian products of graphs. Colloquium math. 21, 1970, 55-74. · Zbl 0195.54301
[12] ŠIK F.: Über subdirekte Summen geordneter Gruppen. Czechoslov. Math. J. 10, 1960, 400-424. · Zbl 0102.26501
[13] TOMKOVÁ M.: On multilattices with isomorphic graphs. Math. Slovaca 32, 1982, 63-74. · Zbl 0496.06005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.