2009 seminar talk: The complexity of colored linear orders
Talk held by Alberto Marcone (Udine) at the KGRC seminar on 2009-05-28.
Let C be a countable partial order. A C-colored linear order (X,f) is a countable linear order X with a map f:X → C. If (X,f) and (X',f') are two such C-colored linear orders, an embedding is an order-preserving φ:X → X' such that f(x) ≤C f'(φ(x)) for all x in X. The quasi-order of C-colored linear orders under embeddability is analytic. Its complexity in the reduction hierarchy depends on the combinatorial properties of C. We will present some results and some open problems.