A Geometric Approach to Combinatorial Fixed-Point Theorems

2013/05/27 by Elyot Grant, Will Ma, Grant, Elyot +1 · 1 citation
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Fixed Point Theorems Analysis #Mathematics and Applications

paper · pdf · doi:10.48550/arxiv.1305.6158

openalex publication_date 2013/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a geometric framework that unifies several different combinatorial fixed-point theorems related to Tucker's lemma and Sperner's lemma, showing them to be different geometric manifestations of the same topological phenomena. In doing so, we obtain (1) new Tucker-like and Sperner-like fixed-point theorems involving an exponential-sized label set; (2) a generalization of Fan's parity proof of Tucker's Lemma to a much broader class of label sets; and (3) direct proofs of several Sperner-like lemmas from Tucker's lemma via explicit geometric embeddings, without the need for topological fixed-point theorems. Our work naturally suggests several interesting open questions for future research.

Citations

• Settling the complexity of computing two-player Nash equilibria

Cited by

• Lower Bounds on Tree Covers

Related

• Beyond Sperner's lemma
• Sperner's Lemma, Brouwer's fixed-point theorem, and cohomology
• Combinatorial Proof of Kakutani's Fixed Point Theorem
• A Tree Sperner Lemma
• On the (in)equivalence of Brouwer's fixed point theorem and Sperner's lemma