Topological Methods in Combinatorics and Game Theory

Course offered at UFMG in 2020/2 (remotely)


Team link | Classes link


Classes on Mondays and Wednesdays, at 9h25


Course notes


Assignment 1 (due December 28th January 4th)

Assignment 2 (due January 15th January 22nd)

Assignment 3 (due February 19th)


Final project topics


About the course

Whenever you stir coffee in a mug, there is always a point not moving. At the same time, there are always at least two antipodal points on Earth’s Equator with the same temperature.

What do these things have to do with colouring vertices in a graph or finding the equilibria of some games? Join this course and we will explore applications and connections of some classical results in algebraic topology to combinatorics and to game theory.

Not to be confused with a course on Topological Graph Theory. No graphs will be drawn in this course.


Main topics

Fixed point type of results and applications to combinatorics and game theory. Other topological methods, such as Scarf’s Lemma and Tucker’s Lemma.


Syllabus

Simplicial complexes. Triangulations. Spheres and boundaries. Sperner’s Lemma. Independence complex of a graph. Theorems of Hall and Konig to hypergraphs. Brouwer’s fixed point theorem. Applications to game theory and Nash Equilibrium. Scarf’s Lemma and applications to combinatorics and games. Tucker’s Lemma and Borsuk-Ulam Theorem. Colouring Kneser Graphs.


Evaluation

70 points on assignments. A final project worth 30 points, that involves reading and presenting a research paper.


References

Penny Haxell’s course notes

Matoušek’s book

Lovász’s notes

Deloera’s notes


Lectures

1st

2nd

3rd

4th

5th

6th

7th

8th

9th

10th

11th

12th

13th

14th

15th

16th

17th

18th

19th

20th