Course description:

Descriptive combinatorics is an emerging field concerned with problems on the borderline between logic/set theory, group theory, measure theory, and combinatorics. Generally, it investigates combinatorial problems on infinite graphs.

Topics:

• Basic results: Borel graphs, graphings and their properties, Borel/measurable/Baire chromatic numbers, easy bounds;
• The LOCAL model of distributed computing: definition, lower and upper bounds, connections to the Borel context;
• Lower and upper bounds: games, Ramsey theory, dichotomies;
• Matchings: equidecompositions, Banach-Tarski paradox and Tarskis circle squaring;
• Further selected topics, if time permits (Complexity, equivalence relations, Toast algorithms, Lovasz Local Lemma);