Colloquium- Proper graph colouring, optimization, and paradoxical decompositions

When: April 7th, Monday, 1pm-2pm
Where: Phillips B152
Speaker: Prof. Robert Simon (London School of Economics and Political Science)

Title: Proper graph colouring, optimization, and paradoxical decompositions

Abstract: We show that there is an infinite graph of finite degree defined by a Borel equivalence relation on a probability space such that it can be coloured properly with 17 colours but only in ways that induce paradoxical decompositions. We show that there are problems of optimization such that every epsilon-optimal solution for small enough positive epsilon induces a paradoxical decomposition.