Leírás
A classical result by Hell and Nešetřil, first proven in 1990, states that every finite non-bipartite (undirected) graph either has a loop or it primitively positively interprets with parameters the triangle graph. A few decades later this theorem was generalized by Barto, Kozik and Niven to directed graphs; they showed that the same conclusion holds for every finite smooth digraph of algebraic length 1. In my talk I will be presenting some new results about further generalizations of this theorem, most interestingly for infinite graphs. These results, which are commonly referred to as pseudoloop lemmas, have deep algebraic consequences, and they are primarily motivated by the study of Constraint Satisfaction Problems. During my talk I will also be attempting to explain these connections.