Date:
Wed, 02/07/202511:00-13:00
Location:
Zoom
Zoom link: https://huji.zoom.us/j/81363531262?pwd=H8IZI0eUGcChY9oaCebLbk6WwwMKq8.1
Meeting ID: 813 6353 1262
Passcode: 915464
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.
Meeting ID: 813 6353 1262
Passcode: 915464
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.