PhD Thesis Defence

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