# 2009 seminar talk: The complexity of colored linear orders

Talk held by Alberto Marcone (Udine) at the KGRC seminar on 2009-05-28.

### Abstract

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.