WP3: Theory of graph homomorphisms

The investigation in this work package will contribute to the homomorphism aspects of the problems of matching theory included in the work package WP1 and to the algorithmic and probabilistic aspects of graph homomorphisms included in the work package WP2, in particular to the Pentagon problem. 

Our novel approach to graph homomorphisms is an application of algebraic techniques, mainly semidefinite programming, to study the structure of graph homomorphisms. In particular, we have found a new sufficient condition for a graph being a core that is applicable in several interesting instances and has led to a solution of the Cameron–Kazanidis conjecture.

We plan to extend this approach much farther. One particular direction is the development around the notion of quantum homomorphism. This is an interesting area bringing together communication complexity, quantum communication, graph homomorphism and linear algebra. 

Another recent approach (with close connections to WP1) is to extend classical existence problems (is a graphk-colorable?) to counting ones. This started with Lovász–Plummer conjecture, solved by Esperet et al. and with several results and conjectures by Thomassen—on exponentially many colorings in various settings. A new addition to this works in the dual, proving existence of exponentially many nowhere-zero flows. Many more questions in this direction remain unresolved. We will investigate the possibility to extend this line of research to the framework of graphons.  

In the study of Ramsey classes we intend to develop tools introduced for giving the existence of Ramsey expansion for every class of finite structures described by means of finite (or infinite but regular) family of forbidden homomorphic images. This machinery has number of applications. In one direction it is possible to identify new Ramsey classes which can be described in this form and in other direction it leads to new proof-techniques  to study questions related to complexity of Constraint Satisfaction Problems on homogeneous templates. 

We intend to follow this line of research further considering also forbidden monomorphisms. This is known to lead to multiple long-standing open problems (such as the question whether graphs of girth 5 have a Ramsey expansion or questions related to classification of families of forbidden monomorphic images of graphs which still leads to classes with omega-categorical universal object studied by Cherlin and Shelah). We hope to understand better the limitations of current tools and possibly find new techniques by considering these examples.

More generally we aim for a novel theory which explain the affinity of recent results on Ramsey classes, the Extension property for Partial Automorphisms and Stationary Independence Relations. Our aim is to extend current techniques from metrically homogeneous graphs first to structures in symmetric binary language and later to a weaker form to homogeneous structures in general. We also plan to explore more links between properties needed for a class to be Ramsey and well-established notions of model theory.