Ross Willard, Department of Pure Mathematics, University of Waterloo
“Bipartite graphs satisfying Maltsev conditions”
Every finite connected bipartite graph G = (V,E) with vertex partition A, B can be associated with three related structures: (1) the digraph (V,E*) in which each edge of G is oriented from A to B; (2) a 2-sorted structure with universes A, B and binary relation E*; (3) a structure with universe E* and two equivalence relations. From the point of view of homo- morphism, retract, and constraint satisfaction problems with template G, I show that these structures are essentially equivalent to G. I will then describe some applications to bipartite graphs satisfying certain Maltsev conditions.