Some Combinatorial and Algorithmic Applications of the Borsuk–Ulam Theorem

摘要

The Borsuk–Ulam theorem has many applications in algebraic topology, algebraic geomtry, and combinatorics. Here we study some combinatorial consequences, typically asserting the existence of a certain combinatorial object. An interesting aspect is the computational complexity of algorithms that search for the object. The study of these algorithms is facilitated by direct combinatorial existence proofs that bypass Borsuk–Ulam.