Abstract
The idea of "Lemke pivoting in a family of oiks (Euler complexes)" generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a "room-partitioning", this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O={O1, ... ,Ok} can be reduced to a pair of oiks O'={O1+ ... +Ok,O0} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known.
| Original language | English |
|---|---|
| Pages (from-to) | 1273-1280 |
| Number of pages | 8 |
| Journal | Electronic Notes in Discrete Mathematics |
| Volume | 36 |
| Issue number | C |
| DOIs | |
| Publication status | Published - 1 Jan 2010 |
Keywords
- Brouwer Theorem
- Euler complex (oik)
- Exchange algorithm
- KKM-Theorem
- Lemke-Howson algorithm
- Manifold
- Pivot
- Room
- Sperner Lemma
- Wall
Fingerprint
Dive into the research topics of 'Sperner Oiks'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver