Logic Seminar
Online Event
Σ12 -completeness results in Borel combinatorics via gadget reductions
Alex Kastner,
Department of Mathematics,
UCLA,
Please note that the time is PST
In 2021, Todorčević and Vidnyánszky proved that the problem of deciding whether a locally finite Borel graph has a proper Borel 3-coloring is Σ12-complete. Building off of an argument of Thornton, we discuss how the polynomial-time gadget reductions used to establish NP-completeness can often be turned into Borel reductions to establish Σ12-completeness results in Borel combinatorics.
For more information, please contact Math Dept. by phone at 626-395-4335 or by email at kechris@caltech.edu.
Event Series
Logic Seminar Series
Event Sponsors