Covering graphs and subdirect decompositions of partially ordered sets. (English) Zbl 0603.06001

Jakubík, Ján

Math. Slovaca 36, 151-162 (1986).

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

Keywords:

covering graph; partially ordered set; posets; subdirect product representation

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