Sperner Lemma Applications

Question

I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of this lemma, namely, Monsky's theorem, which states that it is impossible to dissect a square into an odd number of triangles having equal areas.

Browsing through a few questions this evening I found two references to Sperner's lemma with respect to totally different applications. I searched the site, and didn't found a question which asks about other applications of Sperner's lemma, so I thought I'll ask the question myself.

What other applications of Sperner's lemma are there?

(I made the question community wiki.)

Answer 1

Francis Su wrote a paper called Rental Harmony: Sperner's Lemma in Fair Division that, as the name indicates, uses Sperner's lemma to solve some fair division problems. It the 2001 Merten Hasse award winning paper, and as such can be found free of charge here

Answer 2

Ron Aharoni and Penny Haxell have applied Sperner's Lemma to simplicial complexes associated with families of hypergraphs to prove various results on independent transversals. In particular, they obtain a topological proof of Hall's theorem. Here's a paper, and an overview on Gil Kalai's blog.

Answer 3

I'm not sure if this is an "application", but the problem of finding a Sperner Triangle is complete for the complexity class PPAD, which contains the problems of finding an approximate Brouwer fixed point, computing an approximate Nash equilibrium or approximate Arrow-Debreu equilibrium, and many others. Thus an algorithm for finding a Sperner Triangle also allows you to compute solutions to these other problems "about equally quickly". (For instance, the paper posted by Thierry can be interpreted as showing that the fair division problem considered is in PPAD.)

In particular, Sperner's Lemma (the fact that such a triangle exists) implies that there exists a solution to every problem in PPAD; so for instance, Sperner's Lemma implies the Borsuk-Ulam theorem and the ham sandwich theorem.

This is somewhat backwards reasoning, because we put a problem in PPAD only after we know its solution (e.g. sandwich-cutting hyperplane or Brouwer fixed point) must exist. But still, Sperner's Lemma implies an existence theorem for every problem in PPAD and the proof can be given by reducing the question of finding a solution to that problem to the question of finding a Sperner Triangle.

Answer 4

The Poincaré-Miranda Theorem is an application of the cubical or polytope version of Sperner's lemma. For the proofs, one can consult the following interesting articles, by C. Ahlbach: https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1048&context=hmc_theses

and by M. Müger: https://arxiv.org/pdf/1310.8090.pdf

This last article also proves the theorem of invariance of dimension (two open sets in Euclidean spaces can only be homeomorphic if both dimensions agree) using Sperner's lemma.

Answer 5

Tamás Király and Júlia Pap used the Sperner lemma to prove that every perfect graph with a clique-acyclic orientation has a kernel. Clique-acyclic means no clique contains a proper directed cycle, or equivalently, every clique has a source node. A kernel is a dominating and independent subset of the vertices.

Namely, for a graph $G=(V,E)$, they considered the polytope $P$ on the formal linear combinations of the vertices $(v_1,v_2,...,v_n)$, defined as

$$P=\text{STAB}(G)-\mathbb{R}_+^n$$

where $\text{STAB}(G)=\{x\in \mathbb{R}^n|\sum_{c \in C}x(c)\leq 1 \text{ for every clique } C\}$.

By a well-known result about perfect graphs*, the vertices of $P$ corresponds to maximal independent sets. They colored the facets of $P$ with the source node of the defining clique of the facet. By finding a multicolored vertex of $P$, they concluded that the vertex corresponds to a kernel of $G$.

Note that the authors used a polar dual of the original Sperner lemma; that's why they colored facets and found a multicolored vertex, rather than the other way else.

*See this: "Inequalities (4.1) and (4.3) suffice to describe $\text{STAB}(G)$ iff $G$ is perfect".