×

Path homomorphisms. (English) Zbl 0857.05057

A homomorphism of an oriented graph \(G= (V, E)\) into another graph \(G'=(V',E')\) is a mapping \(f:V\to V'\) such that \(f(x)f(y)\in E'\) for any \(xy\in E\). If there is a homomorphism from \(G\) into \(G'\), we write \(G\to G'\); otherwise we write \(G\nrightarrow G'\). The authors look into homomorphisms of finite oriented paths. It turns out that the poset determined by all finite paths of length at least four and homomorphisms between them is dense: If \(P\) and \(P'\) are such paths for which \(P\to P'\) and \(P'\nrightarrow P\) then there is a path \(P''\) with \(P\to P''\to P'\) but \(P'\nrightarrow P''\) and \(P''\nrightarrow P\). Utilizing this density, the authors prove: (1) Any two-dimensional countable poset is representable by finite oriented paths and their homomorphisms. (2) Any finite-dimensional poset is representable by finite oriented trees and their homomorphisms. However, they are yet unable to determine if every countable poset is representable by finite oriented paths. The authors introduce a notion of a poset class being “on-line representable”. This allows them to strengthen their results and give an “on-line” version of the problem of representing every countable poset.

MSC:

05C38 Paths and cycles
05C99 Graph theory
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1006/jctb.1994.1016 · Zbl 0803.05029
[2] Kom?rek, ?asopis P?st, Mat. 51 pp 348– (1984)
[3] DOI: 10.1016/0012-365X(94)90235-6 · Zbl 0819.05030
[4] DOI: 10.1112/plms/s3-2.1.326 · Zbl 0047.03402
[5] DOI: 10.1006/eujc.1993.1004 · Zbl 0799.05063
[6] DOI: 10.1016/0166-218X(92)90294-K · Zbl 0761.05040
[7] Bang-Jansen, Discrete Math.
[8] DOI: 10.1137/0401029 · Zbl 0678.05018
[9] DOI: 10.1016/0166-218X(90)90017-7 · Zbl 0697.05029
[10] DOI: 10.1002/jgt.3190110402 · Zbl 0647.05025
[11] Hell, SIAM J. on Disc. Math.
[12] Hell, Combinatorics, Paul Erd?s is Eighty 2 (1994)
[13] Hell, Trans. Amer. Math. Soc.
[14] DOI: 10.1016/0012-365X(92)90282-K · Zbl 0803.68080
[15] DOI: 10.1007/BF01300959 · Zbl 0375.05023
[16] Hell, Europ. J. Combin. 12 pp 33– (1991) · Zbl 0715.05027
[17] DOI: 10.1016/0095-8956(90)90132-J · Zbl 0639.05023
[18] DOI: 10.1111/j.1749-6632.1979.tb17773.x
[19] DOI: 10.1007/BF02122553 · Zbl 0657.05028
[20] DOI: 10.1016/0095-8956(84)90056-X · Zbl 0547.05058
[21] Trotter, Dimension theory of partially ordered sets (1992) · Zbl 0764.05001
[22] DOI: 10.1016/0012-365X(78)90062-6 · Zbl 0388.05039
[23] DOI: 10.1016/S0019-9958(81)90226-6 · Zbl 0502.68015
[24] DOI: 10.1007/BF01303514 · Zbl 0794.05037
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.