(1) Department of Applied Mathematics, Charles University, Malostranské nám. 25, 11800 Praha, Czech Republic;(2) Institute of Theoretical Computer Sciences (ITI), Charles University, Malostranské nám. 25, 11800 Praha, Czech Republic
Abstract:
We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions. *Supported by Grants LN00A56 and 1M0021620808 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.
