Tuesday, August 14, 2018 10:00 am
-
10:00 am
EDT (GMT -04:00)
Renzhi Song, Department of Pure Mathematics, University of Waterloo
"Series-Parallel Posets and Polymorphisms"
The complexity of the retraction problem for series-parallel posets is known to be in P for those that satisfy the 4-crown condition. We will show how we can improve on this to show that it is in NL. Furthermore we will show that satisfying the 4-crown condition is equivalent to admitting Freese-McKenzie polymorphisms. This establishes an equivalence between all of properties mentioned above for series-parallel posets.
MC 2009