Finite paths are universal

DOI10.1007/S11083-005-9005-XMaRDI QIDQ5920532zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jan Hubička, J. Nešetřil

Publication date 2 May 2006

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-005-9005-x

zbMATH Keywords

oriented pathpartially ordered set

Mathematics Subject Classification ID

Paths and cycles (05C38) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Review text

The authors prove that, in general, any countable partially ordered set can be represented by finite oriented paths ordered by the existence of homomorphisms between them. This generalizes an analogous result that was known only for partial orders of dimension 2.

Recommendations

• Finite paths are universal
• Path homomorphisms
• Universal partial order represented by means of oriented trees and other simple graphs
• An universality argument for graph homomorphisms
• On the homomorphism order of labeled posets

Cites work

• Automorphism groups of graphs and edge-contraction
• Countable homogeneous partially ordered sets
• Duality and Polynomial Testing of Tree Homomorphisms
• Endomorphism monoids and topological subgraphs of graphs
• Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees)
• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• On locally presented posets
• On universal partly ordered sets and classes
• Path homomorphisms
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• Universal partial order represented by means of oriented trees and other simple graphs

Cited in

(15)

• A surprising permanence of old motivations (a not-so-rigid story)
• Towards a characterization of universal categories
• Universal partial order represented by means of oriented trees and other simple graphs
• Homomorphism order of connected monounary algebras
• Labeled posets are universal
• scientific article; zbMATH DE number 1817186 (Why is no real title available?)
• On Finite Maximal Antichains in the Homomorphism Order
• Path homomorphisms
• scientific article; zbMATH DE number 936885 (Why is no real title available?)
• Finite paths are universal
• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Density and fractal property of the class of oriented trees
• Gadget construction and structural convergence
• Finite dualities and map-critical graphs on a fixed surface
• Minimal universal and dense minor closed classes

This page was built for publication: Finite paths are universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920532)