1. Characterizing universal intervals in the homomorphism order of digraphs
- Author
-
Oviedo Timoneda, Pablo, Universitat Politècnica de Catalunya. Departament de Matemàtiques, and Serra Albó, Oriol
- Subjects
Oriented tree ,Grafs, Teoria de ,Directed graph ,Digraph ,Homomorphism order ,Density ,Oriented path ,Universality ,Graph theory ,Computer Science::Discrete Mathematics ,Homomorphism ,Partial order ,05 Combinatorics::05C Graph theory [Classificació AMS] ,Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC] - Abstract
In this thesis we characterize all intervals in the homomorphism order of digraphs in terms of universality. To do this, we first show that every interval of the class of digraphs containing cycles is universal. Then we focus our interest in the class of oriented trees (digraphs with no cycles). We give a density theorem for the class of oriented paths and a density theorem for the class of oriented trees, and we strengthen these results by characterizing all universal intervals in these classes. We conclude by summarising all statements and characterizing the universal intervals in the class of digraphs. This solves an open problem in the area.
- Published
- 2020