Omomorfismo tra grafi: decidibilità e complessità

The theory of atoms ZFA, an extension of the theory ZF, was defined in 1920s by Abraham Fraenkel. The original goal of this theory was to find a proof of the independence of the axiom of choice from the other axioms of ZF using particular models called permutation models. Permutation models allowed to introduce a new concept of "definability", which in turn allows to deal with decidability problems and achieve different results from classical computer science. The main feature of this new notion of definability is the possibility to actually write such algorithms on machines. So it becomes interesting to inquire which problems have a different solution (e.g. in terms of decidability) in the new setup compared to what happens in classical computer science. Among them we have the decidability of the problem of the existence of a definable homomorphism between definable structures. It has been proved that even when moving to logic with atoms, such problem is still undecidable if we consider arbitrary first order structures. This raises the following question: does the same hold for more natural structures, like graphs? The answer we obtained is that even in the content of logic with atoms, the decidability problem of definable homomorphism between definable graphs remains undecidable. Such solution was obtained by reducing the decidability problem between arbitrary structures to the decidability problem between graphs. A reduction is a function that, in our case, transforms a given structure in a corresponding graph preserving the existence of homomorphisms and their definability. From the technical point of view, the core of the thesis is the definition of a sort of "composition" of Kneser graphs, which we then used to define our reductions. However, soon after the introduction of the "composition" of Kneser graphs, we noticed that such construction yield to many other applications. A first application concerns the study of the structure of connected graphs up to homomorphism. The analogous problem for arbitrary (finite) graphs is well studied: for example, it has been proved that the structure of all graphs up to homomorphism is a lattice. In contrast, we show that the structure of connected graphs is very "far" from being a join-semilattice. Another application concerns the study up to Borel reducibility of the homomorphism relation over the class of countable graphs. We generalize some results of Louveau and Rosendal and we get some completely new results extending the previous ones to uncountable graphs. To the best of our knowledge, the aforementioned results (and their variants) are new, and we expect to obtain even more applications of these techniques in the near future thanks to its flexibility, which allows one to adapt it to many different contexts.