Universal intervals in the homomorphism order of digraphs

In this thesis we solve some open problems related to the homomorphism order of digraphs. We begin by introducing the basic concepts of graphs and homomorphisms and studying some properties of the homomorphism order of digraphs. Then we present the new results. First, we show that the class of digraphs containing cycles has the fractal property (strengthening the density property) . Then we show a density theorem for the class of proper oriented trees. Here we say that a tree is proper if it is not a path. Such result was claimed in 2005 but none proof have been published ever since. We also show that the class of proper oriented trees, in addition to be dense, has the fractal property. We end by considering the consequences of these results and the remaining open questions in this area.
Outgoing