Ross Willard, Department of Pure Mathematics, University of Waterloo
“Bipartite graphs with interesting polymorphisms”
Given a finite graph G, the Retract Problem Ret(G) is conjectured to be solvable in polynomial time if and only if, for some n > 1, there exists a retraction r of Gn onto the “diagonal subgraph ∆n(G) = {(v, v, . . . , v) : v ∈ V (G)} of Gn which moreover satisfies r(v1,v2,...,vn) = r(v2,...,vn,v1). A retract of this kind is called an n-ary cyclic poly- morphism of G. More generally, a retract of Gn onto ∆n(G) is called an n-ary idempotent polymorphism of G, and there are many open problems regarding the structure of graphs admitting an idempotent polymorphism with specified properties. In this lecture I will survey what is known and state some open problems.
MC 5479
**Please Note Room**