Search

Your search keyword '"Oviedo Timoneda, Pablo"' showing total 4 results
Start Over Author "Oviedo Timoneda, Pablo"
4 results on '"Oviedo Timoneda, Pablo"'

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

2. Characterizing universal intervals in the homomorphism order of digraphs

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Serra Albó, Oriol, Oviedo Timoneda, Pablo, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Serra Albó, Oriol, and Oviedo Timoneda, Pablo

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

3. Universal intervals in the homomorphism order of digraphs

Author

Oviedo Timoneda, Pablo, Hubicka, Jan, Serra Albó, Oriol, Universitat Politècnica de Catalunya. Departament de Matemàtiques, and Univerzita Karlova. Department of Applied Mathematics

Subjects
density, homomorphism, partial order, Matemàtiques i estadística [Àrees temàtiques de la UPC], universality, graph, Morphisms (Mathematics), digraph, Morfismes (Matemàtica), tree
Abstract

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

Published
2019

4. Universal intervals in the homomorphism order of digraphs

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Univerzita Karlova. Department of Applied Mathematics, Hubicka, Jan, Serra Albó, Oriol, Oviedo Timoneda, Pablo, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Univerzita Karlova. Department of Applied Mathematics, Hubicka, Jan, Serra Albó, Oriol, and Oviedo Timoneda, Pablo

Abstract

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

Published
2019

Catalog

Books, media, physical & digital resources
See catalog results