Finite Paths are Universal |
| |
Authors: | Email author" target="_blank">J?Hubi?kaEmail author J?Ne?et?il |
| |
Institution: | (1) Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, 11800 Praha, Czechia |
| |
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 new on-line dimensions.
Mathematics Subject Classifications (2000) 06A06, 06A07, 05E99, 05C99.J. Nešetřil: Supported by a Grant LN00A56 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona. |
| |
Keywords: | universal posets universal graphs homomorphisms on line embeddings |
本文献已被 SpringerLink 等数据库收录! |