Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes

摘要

In this paper, we define three Sperner problems on specific surfaces and prove that they are complete respectively for the classes PPAD, PPADS and PPA. This is the first time that locally 2-dimensional Sperner problems are proved to be complete for any of the polynomial parity argument classes.