A partial order is universal if it contains every countable partial order as a suborder. In 2017, Fiala, Hubi\v{c}ka, Long and Ne\v{s}et\v{r}il showed that every interval in the homomorphism order of graphs is universal, with the only exception being the trivial gap $[K_1,K_2]$. We consider the homomorphism order restricted to the class of oriented paths and trees. We show that every interval between two oriented paths or oriented trees of height at least 4 is universal. The exceptional intervals coincide for oriented paths and trees and are contained in the class of oriented paths of height at most 3, which forms a chain.
翻译:如果部分顺序包含每个可计算部分顺序作为子顺序,则部分顺序是普遍性的。 2017年, Fiala, Hubi\v{c}ka, Long 和 Ne\v{s{s}et\v{r}il 显示,图形同质顺序中的每一个间隔都是普遍性的,唯一的例外是微不足道的间隔 $[K1,K_2]。 我们认为,单质顺序仅限于方向路径和树木类别。我们显示,两向路径或高处方向树之间的每一个间隔至少4是普遍性的。 特殊间隔是方向路径和树木的重叠, 并且包含在构成链条的最多3个高度方向路径的类别中。