Labeled posets are universal

DOI10.1016/J.EJC.2007.02.005MaRDI QIDQ2472843zbMATH OpenOpenAlexFDO

Authors Erkko Lehtonen

Publication date 25 February 2008

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2007.02.005

zbMATH Keywords

partially ordered sets with \( k\) labelsrepresentations of \(k\)-posets by directed graphs

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Review text

The main goal of this paper is to study partially ordered sets labeled with \( k\) labels (\(k\)-posets) and their homomorphisms. Section 2 deals with some preliminary results on these notions. In Section 3 it is proved that the homomorphicity order of finite \(k\)-posets is a distributive lattice. In Section 4 it is shown that the homomorphicity orders of finite \(k\)-posets and \(k\)-lattices are universal, in the sense that every countable poset can be embedded into them. Section 5 deals with representations of \(k\)-posets by directed graphs. An interesting categorical isomorphism between \(k\)-posets and their digraph representations is established.

Recommendations

• On the homomorphism order of labeled posets
• Some notes on the universality of three-orders on finite labeled posets.
• Universal partial order represented by means of oriented trees and other simple graphs
• Finite paths are universal
• An universality argument for graph homomorphisms

Cites work

• Algebra and theory of order-deterministic pomsets
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• Finite paths are universal
• Free shuffle algebras in language varieties
• scientific article; zbMATH DE number 3735177 (Why is no real title available?)
• scientific article; zbMATH DE number 1500515 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2154085 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Modeling concurrency with partial orders
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• On universal partly ordered sets and classes
• The equational theory of pomsets
• Theories of orders on the set of words
• Universal partial order represented by means of oriented trees and other simple graphs

Cited in

(13)

• Algebra and theory of order-deterministic pomsets
• An algebra over the operad of posets and structural binomial identities
• Complexity issues for preorders on finite labeled forests
• An universality argument for graph homomorphisms
• Fine hierarchies via Priestley duality
• Some notes on the universality of three-orders on finite labeled posets.
• The Wadge order on the Scott domain is not a well-quasi-order
• On the homomorphism order of labeled posets
• Clonoids of Boolean functions with a monotone or discriminator source clone
• Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
• Universality of intervals of line graph order
• Fine hierarchies and m-reducibilities in theoretical computer science
• Definability in substructure orderings. II: Finite ordered sets

This page was built for publication: Labeled posets are universal

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