# Sperner Lemma Applications

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.)

-

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

-

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.

-

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.

-