AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

Sperner's Lemma states the existence of a multicoloured triangle in certain kinds of colorings of triangulations. It's connection to topology is well-known: Brouwer's fixed-point theorem for example can be derived from it. In this talk we investigate a different kind of applications. First we state a version of Sperner's Lemma in which we color the vertices of an n-dimensional polyhedron - and we can get another version by polarizing. We show how this latter statement can lead to short proofs of a variety of results in combinatorics and game theory. For example, the theorem of Boros and Gurvich, that perfect graphs are kernel-solvable, or results about stable matchings and their generalizations. We also show that these polyhedral versions of Sperner's Lemma are PPAD-complete, and pose some open questions. Joint work with Tamás Király.

Natalia Klein

1000

--email hidden

passcode not visible

logged in users only